1.題目

1. 1004. 最大連續1的個數 III - 力扣（LeetCode）
2. 1658. 將 x 減到 0 的最小操作數 - 力扣（LeetCode）

2.題目解答

1.最大連續1的個數

題目及題目解析

算法學習

思路一:暴力解法

我們可以通過直接遍歷將數組,將所以可能全部找出來,然后將最長的數組返回即可

解法如下:

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int maxLen = 0;for (int start = 0; start < nums.size(); ++start) {int zeroCount = 0;int end = start;while (end < nums.size()) {if (nums[end] == 0) {zeroCount++;}if (zeroCount <= k) {maxLen = max(maxLen, end - start + 1);} else {break;}end++;}}return maxLen;}
};

當然這是過不了的需要我們優化

思路二:滑動窗口

但是其實發現right指針并不用每次都回到left的右邊

我們可以通過計數讓left向后走,而right可以保持在原有位置

也就是說可以用滑動窗口解決這個問題:

1.進窗口

將k加上right能移動到的最大位置就是窗口的初始化

2.出窗口

當零的個數大于k時,就要將left向右移動,然后對left進行判斷,

將零的個數減到等于k此時就完成了出窗口

每次出窗口對長度進行判斷求最大的長度即可

這部分的代碼如下:

int ret = 0;
for(int right = 0,left = 0,zero = 0;right<nums.size();right++){if(nums[right]==0)//進窗口{zero++;}while(zero>k)//出窗口{if(nums[left++]==0){zero--;}}ret = max(ret,right-left+1);//判斷}

代碼提交

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0,right =0,zero = 0;int ret = 0;for(;right<nums.size();right++){if(nums[right]==0){zero++;}while(zero>k){if(nums[left++]==0){zero--;}}ret = max(ret,right-left+1);}return ret;}
};

2.將x減到0的最小操作數

題目及題目解析

算法學習

這道題如果直接做會很難,但是如果將思路轉化一下,就會變得簡單了:

要求的數的和為x,我們可以將這個數組的和計算出為sum,那么剩下的數組就為sum-x

又由于要求出最小長度就可以轉化為求最長子數組的長度了

那么這道題就變得簡單了求最長子數組的長度且數組的和為target

滑動窗口解決問題

轉換后的這道題之前寫過:

int right = 0,left = 0,sum = 0,ret = 0;
while(right<nums.size())
{sum+=nums[right];while(sum>target){sum -= nums[left];left++;}if(sum == target){ret = max(ret,right-left+1);}right++;
}

核心代碼寫完后后續將判斷返回的內容加入即可

代碼提交

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0,target = 0,left = 0,right = 0;for(int i = 0;i<nums.size();i++){sum+=nums[i];}target = sum-x;if(target<0){return -1;}sum = 0;int ret = -1;while(right<nums.size()){sum+=nums[right];while(sum>target){sum -= nums[left];left++;}if(sum == target){ret = max(ret,right-left+1);}right++;}if(ret==-1){return ret;}else{return nums.size()-ret;}}
};