最长连续子数组

[编程题]最长连续子数组

热度指数：922 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 ，返回仅包含 1 的最长（连续）子数组的长度

示例1

输入

[1,1,1,0,0,0,1,1,1,1,0],2

输出

说明

可以将输入中的第3个0和第4个0变成1，新数组为[1,1,1,0,0,1,1,1,1,1,1]，因此最长连续1的子数组长度为6

示例2

输入

[0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1],3

输出

说明

可以将输入中的第3个0、第4个0，第5个0都变成1，新数组为[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]，因此最长连续1的子数组长度为10

算法知识视频讲解

Java

贴心的勇士要发财

最简单的暴力写法，利用栈，遇到不一样的元素时全部出栈，统记出现的次数添加到list里即可
import java.util.*;
public class Solution {
    public int GetFragment (String str) {
        Queue<Integer> list=new LinkedList<>();
        Stack<Character> s=new Stack<>();
        int i=0,sum=0,out;
        for(char c:str.toCharArray()){
                if(s.isEmpty()){
                    s.push(c);
                    i++;
                }else if(!s.isEmpty()&&s.peek()==c){
                    s.push(c);
                    i++;
                }else if(!s.isEmpty()&&s.peek()!=c){
                    while(!s.isEmpty()){
                        s.pop();
                    }
                    list.add(i);
                    s.push(c);
                    i=1;
                }
                 }
             if(!s.isEmpty()){
                    while(!s.isEmpty()){
                        s.pop();
                    }
                    list.add(i);
                }   
                int l=list.size(); //不能直接除以list.size()因为每次出队列，队列大小都会变小
            for(int j=0;j<l;j++){
                sum+=list.poll();
           
                }
                System.out.println(!str.isEmpty()?sum/l:0);
                
        return out=!str.isEmpty()?sum/l:0;
    }
}

编辑于 2023-08-28 21:40:21 回复(0)

Java

喜欢后仰跳投的椰子说又不是不能用

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param arr int整型一维数组
     * @param k int整型 允许0变为1的个数
     * @return int整型
     */
    int max = 0;
    int count = 0;
     public int GetMaxConsecutiveOnes (int[] arr, int k) {
        //滑动窗口
        int left = 0;
        int right = 0;
        Map<Integer, Integer> map = new HashMap<>();
        while(right < arr.length){
            if (arr[right] == 0 && map.getOrDefault(0,0) <= k){
                map.put(0,map.getOrDefault(0,0)+1);
            }
            if (arr[right] == 0 && map.getOrDefault(0,0) > k){
                while(map.get(0) > k){
                    if (arr[left] == 0){
                        map.put(0,map.getOrDefault(0,0)-1);
                    }
                    left++;
                    count--;
                }
            }
            count++;
            right++;
            max = Math.max(max,count);
        }
        return max;
    }
}

经典滑动窗口题目,就是多了个0替换1嘛

发表于 2023-08-28 19:54:28 回复(0)

Java

牛客662885399号

import java.util.*;

public class Solution {

public int GetMaxConsecutiveOnes (int[] arr, int k) {
/**
核心思路：以0开头，查找0得数量=k记录下最大值m；开头逐位向后移动，每次都查找0得数量对应的最大值，如果<=m直接跳过，大于m更新m

**/

//记录最大值

int max = 0;
//start 从0 开始向后位移
for(int start = 0 ;start<=arr.length-1; start++){
int _0count = 0;//计数器 - 0得数量

int pointer = start; //计数器- 当前位移指针

while(_0count<k){//0得数量小于k ,继续执行
if(pointer>=arr.length){
break; //最大临界值判断，防止越界
}
if(arr[pointer]==0){
_0count++;//0 得数量+1
}
pointer++;//指针位移
}
//从指针处向后数连续1得数量，赋值给最大值
int newMax= (pointer-start)+getNum(arr, pointer);
max = max<newMax?newMax:max;
}
return max;

}

//从找到得最后一位向后看还有多少个连续1
public int getNum(int[] arr, int pointer){
int num = 0;
for(int i = pointer; i<=arr.length-1;i++){
if(arr[i]==0){
break;
}
num++;
}
return num;
}
}

发表于 2022-02-24 15:56:12 回复(0)