1.題目
題目分析:
給一個數字k,可以把數組里的0改成1,但是只能改k次,然后該變得到的數組能找到最長的子串且都是1。
2.算法原理
這里不用真的把0變成1,因為改了比較麻煩,下次用就要改回成1,這里用滑動窗口來,先進窗口,遇到1就無視,遇到0就進窗口,雖然1和0都在一個窗口中在畫圖里,但是要把1看出空氣,理會0的個數,然后更k比較,滿了就開始出窗口了,要排除0直到窗口內的0個數小于k。for循環來移動right,遇到1是無視,就走for循環來,遇到0就特殊處理,每次循環都更新長度值。
3.代碼實現
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size();int len=0;for(int left=0,right=0,zero=0;right<n;right++){//等于1不用管,for循環會自動right++if(nums[right]==0) zero++;while(zero>k){if(nums[left++]==0) zero--;}len=max(len,right-left+1);}return len;}
};