讨论/《算法与面试技巧精讲》 - 最大连续 1 的个数 III/
《算法与面试技巧精讲》 - 最大连续 1 的个数 III
共 19 个回复

参考昨天的每日一题的写法,觉得这类问题这么写也很简单,只要维护返回right-left即可

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        zerocount = left = right = 0
        n = len(A)
        while right < n:
            print(zerocount)
            if A[right] == 0:
                zerocount += 1
            if zerocount > K:
                if A[left] == 0:
                    zerocount -= 1
                left += 1
            right += 1
        return right - left

5
// 滑动窗口求:最大连续1的个数
public int longestOnes(int[] A, int K) {
    int i = 0, j = 0;
    int zeros = 0;
    int ans = 0;

    while(j < A.length) {
        if(A[j] == 0) {
            zeros++;
            while (zeros > K) {
                if(A[i]==0) {
                    zeros--;
                }
                i++;
            }
        }
        j++;
        ans = Math.max(ans, j - i);
    }
    return ans;
}
2

Java 滑动窗口

class Solution {
    public int longestOnes(int[] A, int K) {
        int left = 0;
        int right = 0;
        int res = 0;
        int count = 0;
        while(right<A.length){
            if(A[right]==1){
                count++;
            }
            right++;
            while(right-left>K+count){
                if(A[left]==1){
                    count--;
                }
                left++;
            }
            res = Math.max(res,right-left);
        }
        return res;
    }
}
2
class Solution {
    public int longestOnes(int[] A, int K) {
        int res = 0, count = 0, left = 0, right = 0;
        while (right < A.length) {
            count += A[right++] == 0 ? 1 : 0;
            while (count > K) {
                count -= A[left++] == 0 ? 1 : 0;
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}
1

java打卡

class Solution {
    public int longestOnes(int[] A, int K) {
        int i=0,j=0;
        int zero = 0;
        int len = A.length;
        int max = 0;
        while(j<len){
            if(A[j]==1){
                j++;
            }else{
                zero++;
                j++;
            }
            while(zero>K){
                if(A[i]==1){
                    i++;
                }else{
                    zero--;
                    i++;
                }
            }

            max=Math.max(max,j-i);
        }
        return max;
    }
}

1

C++

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int left=0,right=0,num0=0,n=A.size(),ans=0;
        while(right<n)
        {
            if(A[right]==0)
                ++num0;
            while(num0>K)
            {
                if(A[left]==0)
                    --num0;
                ++left;
            }
            ans=max(ans,right-left+1);
            ++right;
        }
        return ans;
    }
};

来个cpp的

class Solution {
public:
int longestOnes(vector<int>& A, int K) {
		int left=0,right=0,size=A.size(),Max=0;
		int num=0;
		while(right<size){
			if(A[right]==1)num++;
			if((right-left-num+1)>K){
				if(A[left]==1)num--;
				left++;
			}
			right++;
		}
		return right-left;
}
};

用424替换后的最长重复字符的简化后方法得到的
C++

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        vector<int> nums(2);
        int n = A.size();
        int maxn = 0;
        int left = 0,right = 0;
        while(right < n){
            //限制条件,否则会变成计算最长0……0、1……1.
            if(A[right]==1) nums[A[right]]++;
            maxn = max(maxn,nums[A[right]]);
            if(right - left + 1 - maxn > K){
                nums[A[left]]--;
                left++;
            }
            right++;
        }
        if(nums[1]){
            return right-left;
        }else{
            return K;
        }

1.jpg

424. 替换后的最长重复字符

套用昨日每日一题的模板

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int ans = 0;
        int n = A.size();
        int maxn = 0;
        int left = 0, right = 0;
        int one = 0;
        while (right < n) {
            one += A[right] == 1;
            if (right - left + 1 - one > K) {
                one -= A[left] == 1;
                left++;
            }
            right++;
            ans = max(ans, right - left);
        }
        return ans;
    }
};