目錄

• 978. 最長湍流子數組
• • 題目
  • 思路分析以及代碼
• 1052. 愛生氣的書店老板
• • 題目
  • 思考分析與初步代碼
  • 優化思路以及優化代碼
• 1208. 盡可能使字符串相等
• • 題目
  • 思考分析以及代碼

978. 最長湍流子數組

https://leetcode-cn.com/problems/longest-turbulent-subarray/

題目

當 A 的子數組 A[i], A[i+1], …, A[j] 滿足下列條件時，我們稱其為湍流子數組：

若 i <= k < j，當 k 為奇數時， A[k] > A[k+1]，且當 k 為偶數時，A[k] < A[k+1]；
或 若 i <= k < j，當 k 為偶數時，A[k] > A[k+1] ，且當 k 為奇數時， A[k] < A[k+1]。
也就是說，如果比較符號在子數組中的每個相鄰元素對之間翻轉，則該子數組是湍流子數組。

返回 A 的最大湍流子數組的長度。

示例1：

輸入：[9,4,2,10,7,8,8,1,9]
輸出：5
解釋：(A[1] > A[2] < A[3] > A[4] < A[5])

示例2：

輸入：[4,8,12,16]
輸出：2

示例 3：

輸入：[100]
輸出：1

提示：
1 <= A.length <= 40000
0 <= A[i] <= 10^9

思路分析以及代碼

這一題是典型的滑動窗口問題。
我的大致思路如下：
1、獲取差分數組
2、從左到右比對差分數組，觀察相鄰兩個元素是否異號(一個大于0 ，一個小于0；或者相反)
3、如果異號，說明符合條件；更新窗口值，右邊界繼續擴展
4、否則，說明當前[left,right)中都不符合條件,需要直接將左邊界更新到原有的右邊界。
5、意外情況：下面有幾種意外情況我是特殊處理的

1、原數組小于等于1，直接返回數組大小
2、如果差分數組中全部都是0，此時返回1

class Solution { public:int juge(int a , int b){if((a > 0 && b < 0) || (a < 0 && b >0)) return true;else return false;}int maxTurbulenceSize(vector<int>& arr) {if(arr.size() <= 1) return arr.size();int n = arr.size();vector<int> diff(n - 1);for(int i = 0; i < n - 1; i++){diff[i] = arr[i+1] - arr[i];}int left = 0 ,right = 1;int max_window_size = 1;int zero_diff_times = 0;if(diff[0] == 0) zero_diff_times++;while(right < diff.size()){if(juge(diff[right],diff[right - 1])){max_window_size = max(max_window_size,right - left + 1);}else{if(diff[right] == 0) zero_diff_times++;left = right;}right++;}if(zero_diff_times == diff.size()) return 1;return max_window_size+1;} };

1052. 愛生氣的書店老板

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

題目

今天，書店老板有一家店打算試營業 customers.length 分鐘。每分鐘都有一些顧客（customers[i]）會進入書店，所有這些顧客都會在那一分鐘結束后離開。

在某些時候，書店老板會生氣。 如果書店老板在第 i 分鐘生氣，那么 grumpy[i] = 1，否則 grumpy[i] = 0。 當書店老板生氣時，那一分鐘的顧客就會不滿意，不生氣則他們是滿意的。

書店老板知道一個秘密技巧，能抑制自己的情緒，可以讓自己連續 X 分鐘不生氣，但卻只能使用一次。

請你返回這一天營業下來，最多有多少客戶能夠感到滿意的數量。
示例：

輸入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
輸出：16
解釋：
書店老板在最后 3 分鐘保持冷靜。
感到滿意的最大客戶數量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示：

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

思考分析與初步代碼

初步思路：
1、從第一個時間段開始遍歷，遍歷每個窗口長度為X的時間段，并且計算這個時間段內老板生氣的時間顧客來的人數。
2、依次遍歷完整個時間段，找到時間段內老板生氣的時間顧客來的人數最多的人數。
3、最后再遍歷一遍原數組，記錄下老板不生氣時候來的總人數
4、兩個結果相加，得到最終結果。

class Solution { public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {int max_sum_start = 0;int max_sum = 0;for(int start = 0; start < customers.size() - X + 1; start++){int sum = 0;for(int i = start; i < start + X ; i ++){if(grumpy[i] == 1) sum += customers[i];}if(sum >= max_sum){max_sum = sum;max_sum_start = start;}}//cout << "max_sum= " << max_sum << endl;int result = 0;for(int i = 0; i < customers.size(); i++){if(grumpy[i] == 0) result+=customers[i];}return result+max_sum;} };

很顯然時間復雜度是O(N * X)

優化思路以及優化代碼

關于長度固定的滑動窗口，有一點我們要熟悉的是，窗口每次滑動時，變化的只有頭尾兩個元素，所以我們只針對這兩個元素進行處理就行。
不過對于第一個窗口需要特殊對待，需要先進行填充。
接下來的窗口中，如果新進來的時間是生氣的，加上顧客量。如果新出去的時間是生氣的，那么減去顧客量。每次滑動都需要更新最大值。

class Solution { public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {int sum = 0;//計算不生氣時來的顧客總數for(int i = 0; i < customers.size(); i++){if(grumpy[i] == 0) sum+=customers[i];}int left = 0, right = 0;//第一個區域while(right < X){if(grumpy[right] == 1) sum += customers[right];right++;}int max_sum = sum;while(right < customers.size()){//生氣的時間段被移除窗口，總顧客減少if(grumpy[left] == 1) sum -= customers[left];//生氣的時間段被移入窗口，總顧客增加if(grumpy[right] == 1) sum += customers[right];max_sum = max(max_sum,sum);left++;right++;}return max_sum;} };

1208. 盡可能使字符串相等

題目

給你兩個長度相同的字符串，s 和 t。

將 s 中的第 i 個字符變到 t 中的第 i 個字符需要 |s[i] - t[i]| 的開銷（開銷可能為 0），也就是兩個字符的 ASCII 碼值的差的絕對值。

用于變更字符串的最大預算是 maxCost。在轉化字符串時，總開銷應當小于等于該預算，這也意味著字符串的轉化可能是不完全的。

如果你可以將 s 的子字符串轉化為它在 t 中對應的子字符串，則返回可以轉化的最大長度。

如果 s 中沒有子字符串可以轉化成 t 中對應的子字符串，則返回 0。

示例 1：

輸入：s = “abcd”, t = “bcdf”, cost = 3
輸出：3
解釋：s 中的 “abc” 可以變為 “bcd”。開銷為 3，所以最大長度為 3。

示例 2：

輸入：s = “abcd”, t = “cdef”, cost = 3
輸出：1
解釋：s 中的任一字符要想變成 t 中對應的字符，其開銷都是 2。因此，最大長度為 1。

示例 3：

輸入：s = “abcd”, t = “acde”, cost = 0
輸出：1
解釋：你無法作出任何改動，所以最大長度為 1。

提示：

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s 和 t 都只含小寫英文字母。

思考分析以及代碼

這一題是一個非常典型的滑動窗口題。
1、首先我們構建差分絕對值數組：

vector<int> diff(s.size()); for(int i = 0; i < diff.size(); i++) {diff[i] = abs(s[i] - t[i]); }

2、然后，我們建立滑動窗口的左右邊界，在差分數組上移動
3、什么時候擴展窗口？
當我們現在存有的cost - 右邊新納入的cost >= 0 的時候，我們可以繼續擴展窗口
4、反之，如果小于0，說明不能繼續擴展了。但是由于我們求的是最大窗口長度，所以此時也不需要縮小窗口，只需要將整個窗口平移即可。記住平移的時候，要將新移除的cost加到當前cost上，算是彌補損失。
5、更新窗口最大長度的操作必然是在擴展窗口的時候啦
這一題思路應該還是比較清晰的。當然也有個地方有點不好搞，那就是第三點是>0 還是 >=0.如果有時間的話，可以自己手動推導一下，如果沒有就兩個都試一下，選擇答案正確的即可.

class Solution { public:int equalSubstring(string s, string t, int maxCost) {//構建相差數組vector<int> diff(s.size());for(int i = 0; i < diff.size(); i++){diff[i] = abs(s[i] - t[i]);}int left = 0, right = 0;int max_length = 0;while(right < diff.size()){//擴大窗口int new_In = diff[right];maxCost = maxCost - new_In;if(maxCost >= 0){max_length = max(max_length,right -left + 1);}else{int new_Out = diff[left];maxCost += new_Out;left++;}right++;}return max_length;} };

總結

以上是生活随笔為你收集整理的leetcode 滑动窗口小结 (三)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。