[编程题]最长连续子数组
- 热度指数：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
输出
6
说明
可以将输入中的第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
输出
10
说明
可以将输入中的第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
public static int max=0;
public static void process(int[] arr,int index,int k){
if(k==0||index==arr.length){//如果已经将k个0变成1了，或者到达了字符串末尾了
int tmp=0;//开始统计计数连续1的个数
for(int i=0;i<arr.length;i++){
if(arr[i]==1){
tmp++;
max=Math.max(max, tmp);
}
else{//一旦遇到0，之前的计数清零
tmp=0;
}
}
return ;//结束
}
//回溯的思想
for(int j=index;j<arr.length;j++){
if(arr[j]==0){
arr[j]=1;
process(arr,index+1,k-1);
arr[j]=0;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,1,1,0,0,0,1,1,1,1,0};
process(arr,0,2);
System.out.println(max);
} 回溯法；尝试将每个0变成1，一旦将k个0变成1，或者到达字符串的结尾，就开始统计连续的1的子数组的最大长度。
发表于 2021-04-16 15:26:14
回复(1)
// 滑动窗口： 时间O(n), 空间O(1) leetcode 1004. 最大连续1的个数 III
int longestOnes(vector<int>& nums, int k) {
int maxLen = 0;
int start = 0;
int CntOne = 0;
for (int end = 0; end < nums.size(); end++) {
if (nums[end] == 1) {
++CntOne;
}
while (CntOne + k < end - start + 1) {
if (nums[start] == 1) {
--CntOne;
}
++start;
}
maxLen = max(maxLen, end - start + 1);
}
return maxLen;
}
发表于 2022-05-02 09:24:27
回复(0)
public static int GetMaxConsecutiveOnes(int[] arr, int k) {
// 判断数组长度是否小于等于将0变为1的长度 若是 则最长连续为数组的长度
if (arr.length <= k) {
return arr.length;
}
int i = 0;
// 存储最长连续子数组的长度
int max = 0;
// 从索引为0的数组下标开始循环 直到索引大于数组长度减去k的长度
while (i < arr.length - k) {
// 定义将0变为1的次数
int count = 0;
// 从索引为i处开始循环对比
int j = i;
for (; j < arr.length; j++) {
// 如果索引位置处的值不为1 则将count++ 意思为将0变成1了
if (arr[j] != 1) {
count++;
}
// 如果将0变为1的次数 大于最初定义的k次数 则将长度和最大值对比 保留最长的长度
if (count > k) {
max = max > j - i ? max : j - i;
break;
}
}
// 如果循环完毕最终长度和数组长度相同 则再将长度和最大值对比 保留最长的长度
if (j==arr.length){
max = max > j - i ? max : j - i;
}
i++;
}
return max;
}
发表于 2021-11-11 14:30:50
回复(0)
最简单的暴力写法，利用栈，遇到不一样的元素时全部出栈，统记出现的次数添加到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)
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)
直接滑动窗口，left和right之间只能包含k个零，也包括arr[left]和arr[right]
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param arr int整型一维数组
* @param k int整型 允许0变为1的个数
* @return int整型
*/
public int GetMaxConsecutiveOnes (int[] arr, int k) {
// write code here
int left=0;
int right=0;
int count=k;
int res=0;
while (right< arr.length){
if (arr[right]==0){
count--;
}
if (count>=0){
res=Math.max(res,right-left+1);
right++;
}else {
if (arr[left]==0){
count++;
}
left++;
right++;
}
}
return res;
}
}
发表于 2022-08-31 16:56:09
回复(0)
子串子数组就用滑动窗口秒杀啊
import java.util.*;
public class Solution {
// 滑动窗口
public int GetMaxConsecutiveOnes (int[] arr, int k) {
int l = 0, r = 0;
int max = 0;
while (r < arr.length) {
int in = arr[r++];
if (in == 0) k--;
while (k < 0) {
int out = arr[l++];
if (out == 0) k++;
}
max = Math.max(max, r-l);
}
return max;
}
}
发表于 2022-06-16 22:52:52
回复(0)
动态规划
public int GetMaxConsecutiveOnes(int[] arr, int k) {
// write code here
k++;
int[][] dp = new int[arr.length][k];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < k; j++) {
if (arr[i] == 1) {
dp[i][j] = i > 0 ? dp[i - 1][j] + 1 : 1;
} else {
dp[i][j] = j > 0 && i > 0 ? dp[i - 1][j - 1] + 1 : 0;
}
}
}
int max = 0;
for (int i = 0; i < dp.length; i++) {
max = Math.max(dp[i][k - 1], max);
}
return max;
}
编辑于 2022-02-27 14:15:12
回复(0)
import java.util.*;
public class Solution {
public int GetMaxConsecutiveOnes (int[] arr, int k) {
/**
核心思路：以0开头，查找0得数量=k记录下最大值m；开头逐位向后移动，每次都查找0得数量对应的最大值，如果<=m直接跳过，大于m更新m
//start 从0 开始向后位移
for(int start = 0 ;start<=arr.length-1; start++){
int _0count = 0;//计数器 - 0得数量
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;
}
}
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; //计数器- 当前位移 指针
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;
}
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)
GOLang
func GetMaxConsecutiveOnes( arr []int , k int ) int {
// write code here
var maxLen int = 0
curLen := 0
ctZeros := 0
var startIndex int = 0
var oldStartIndex int = 0
i := 0
for i < len(arr) {
if arr[i] == 1{
if i > 0 && arr[i - 1] == 0 && startIndex == oldStartIndex {
startIndex = i;
}
curLen += 1
i += 1
} else {
if i > 0 && startIndex == oldStartIndex {
startIndex = i
}
if ctZeros < k {
curLen += 1
ctZeros += 1
i += 1
} else {
if curLen > maxLen{
maxLen = curLen
}
curLen = 0 // each loop starts a new inner loop. Unvisited indexes are aborted
ctZeros = 0
i = startIndex
oldStartIndex = startIndex
}
}
}
if i == len(arr){
if arr[i - 1] == 1 {
if curLen > maxLen{
maxLen = curLen
}
} else {
if ctZeros <= k {
if curLen > maxLen{
maxLen = curLen
}
}
}
}
return maxLen
}
发表于 2022-01-20 21:31:19
回复(0)
class Solution {
public:
int GetMaxConsecutiveOnes(vector<int>& arr, int k) {
// write code here
int left = 0, right = 0;
int n = arr.size();
int ret = 0;
while (right < n) {
if (arr[right] == 0) {
if (k == 0) {
while (arr[left++] == 1);
} else {
--k;
}
}
++right;
ret = max(ret, right - left);
}
return ret;
}
}; 滑动窗口模板题
发表于 2021-10-13 17:52:55
回复(0)
补个双指针：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param arr int整型vector
* @param k int整型 允许0变为1的个数
* @return int整型
*/
int GetMaxConsecutiveOnes(vector<int>& arr, int k) {
// write code here
int left=0,right=0;
int zeroCnt=0;
int res = 0;
for(right=0;right<arr.size();right++){
if(arr[right]==0){
zeroCnt++;
}
while(zeroCnt>k){
if(arr[left++]==0) zeroCnt--;
}
res = max(res,right-left+1);
}
return res;
}
};
发表于 2021-09-02 15:47:37
回复(0)
// C++ 回溯版本代码
class Solution {
private:
int res = 0;
public:
void backtracking(vector<int>& arr, int k, int index) {
if (k == 0) {
int curr = 0;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == 1) {
curr++;
} else {
res = res < curr ? curr : res;
curr = 0;
}
}
res = res < curr ? curr : res;
return ;
}
for (int i = index; i < arr.size(); i++) {
if (arr[i] == 0) {
arr[i] = 1;
backtracking(arr, k - 1, index + 1);
arr[i] = 0;
}
}
}
int GetMaxConsecutiveOnes(vector<int>& arr, int k) {
backtracking(arr, k, 0);
return res;
}
};
发表于 2021-08-19 22:07:16
回复(0)
双指针go语言解法
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param arr int整型一维数组
* @param k int整型 允许0变为1的个数
* @return int整型
*/
func GetMaxConsecutiveOnes( arr []int , k int ) (ans int) {
// write code here
pre, suf := -1,0
zero, n := 0, len(arr)
for pre = 0; pre < n; pre++ {
if arr[pre] == 0 {
zero++
}
if zero > k {
for ;suf<n;suf++ {
if arr[suf] == 0 {
zero--
suf++
break
}
}
}
ans = max(ans, pre-suf+1)
}
return ans
}
func max(i,j int) int {
if i > j {
return i
}
return j
}
发表于 2021-07-10 15:34:55
回复(0)
golang 递归版本
func GetMaxConsecutiveOnes(arr []int, k int) int { max := 0 for i:=0; i<len(arr);i++ { tmp := getMaxConsecutiveOnes(arr[i:], k) if tmp> max { max = tmp } } return max } func getMaxConsecutiveOnes(arr []int, k int) int { if len(arr) <= 0 { return 0 } if len(arr) == 1 { if arr[0] == 1 || k > 0 { return 1 } return 0 } if arr[0] == 1 { return getMaxConsecutiveOnes(arr[1:], k) + 1 } else { if k > 0 { return getMaxConsecutiveOnes(arr[1:], k-1) + 1 } else { return 0 } } }
编辑于 2021-05-10 13:43:07
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param arr int整型vector
* @param k int整型 允许0变为1的个数
* @return int整型
*/
const vector<int> * v;
int n;
int found_max = 0;
// 开始尝试填第 i 个 bit；
// 现在已经有 current_consec 个连续的 1;
// 还有 k 次填 1 的机会
void solve(int i, int current_consec, int k)
{
const vector<int> & arr = *v;
if (i == n) { // 填完了, 返回
return;
}
if (arr[i]) {
// 输入给定的第 i 位是 1, 则没得选, 这一位只能填 1
// 尝试冲击一下榜单
if (current_consec + 1 > found_max) {
found_max = current_consec + 1;
}
solve(i + 1, current_consec + 1, k);
} else {
if (k == 0) { // k == 0, 说明你把 0 改成 1 的机会用完了
solve(i + 1, 0, 0);
} else {
// arr[i] 为 0, 而且还剩 k 次修改机会
{
// 那我尝试填 1
// 尝试冲击一下榜单
if (current_consec + 1 > found_max) {
found_max = current_consec + 1;
}
solve(i + 1, current_consec + 1, k - 1);
}
{
// 不, 我不填, 把剩下的 k 次机会留到后面
solve(i + 1, 0, k);
}
}
}
}
int GetMaxConsecutiveOnes(vector<int>& arr, int k) {
v = &arr;
n = arr.size();
solve(0, 0, k);
return found_max;
}
}; 尾递归优化版本，更高效：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param arr int整型vector
* @param k int整型 允许0变为1的个数
* @return int整型
*/
const vector<int> * v;
int n;
int found_max = 0;
void solve(int i, int current_consec, int k)
{
const vector<int> & arr = *v;
while (i != n) {
if (arr[i]) {
if (current_consec + 1 > found_max) {
found_max = current_consec + 1;
}
++current_consec;
} else {
if (k != 0) {
if (current_consec + 1 > found_max) {
found_max = current_consec + 1;
}
solve(i + 1, current_consec + 1, k - 1);
}
current_consec = 0;
}
++i;
}
}
int GetMaxConsecutiveOnes(vector<int>& arr, int k) {
v = &arr;
n = arr.size();
solve(0, 0, k);
return found_max;
}
};
编辑于 2021-04-26 00:09:10
回复(0)
问题信息
通过挑战的用户
-
2023-03-04 21:13:00 -
2022-12-09 13:46:20
-
2022-11-09 17:35:07
-
2022-10-29 21:40:49
-
2022-10-12 16:08:12
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
