1.字符串的排列

在滑動窗口總結(jié)文章里面講解過了

二刷debug：首先，縮小窗口的條件是r-l >s1.size()。然后，必須用need.count( c )而不是need[c] >= 1。count( c ) 僅僅檢查鍵 c 是否存在于 unordered_map 中，與鍵對應(yīng)的值無關(guān)！而need[c]>=1是必須need中有其鍵并且數(shù)量大于等于1

class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_map<char, int> window, need;for(char c : s1) need[c] ++;int left = 0, right = 0;int valid = 0;while(right < s2.size()){char c = s2[right];right++;if(need.count(c)){window[c]++;if(need[c] == window[c]) valid++;}while(right - left > s1.size()){char d = s2[left];left ++;if(need.count(d)){if(need[d] == window[d]) valid--;window[d]--;}}if(need.size() == valid && right - left == s1.size()){return true;}}return false;}
};

2.找出字符串中第一個匹配的下標(biāo)

拿到手的第一想法就是，滑動窗口，輸出left
但是這個要求順序完全一樣，不能是排列或者組合
查了一下KMP是專門弄這種的，學(xué)習(xí)新算法了(我只是來做雙指針的…)這篇文章是個純刷題記錄，不貼詳細(xì)講解，最多記錄大致思路，需要講解去秒殺直接部分->傳送門
二刷debug：寫出來了，幾乎是靠背的，注意ne初始化

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size();int m = needle.size();vector<int> ne(m, -1);// ne數(shù)組必須初始化為-1而不是0,只有-1才代表沒有相同的前后綴// 建next數(shù)組for(int i = 1, j = -1; i < m; i ++){while(j != -1 && needle[i] != needle[j + 1]) j = ne[j];if(needle[i] == needle[j + 1]) j ++;ne[i] = j;}// 匹配for(int i = 0, j = -1; i < n; i ++){while(j != -1 && haystack[i] != needle[j + 1]) j = ne[j];if(haystack[i] == needle[j + 1]) j ++;if(j == m - 1){return i - m + 1;}}return -1;}
};

3.最大連續(xù)1的個數(shù)II

不是，家人們，滑動窗口為什么都劃到雙指針標(biāo)簽下了啊
題：
給定一個二進制數(shù)組 nums 和一個整數(shù) k，如果可以翻轉(zhuǎn)最多 k 個 0 ，則返回 數(shù)組中連續(xù) 1 的最大個數(shù) 。
eg：
輸入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
輸出：6
在秒殺系列的滑動窗口秒殺文章里面寫過
用滑動窗口做題需要先明白3個問題

1. 什么時候擴大窗口？更改什么數(shù)據(jù)？
2. 什么時候縮小窗口？更改什么數(shù)據(jù)？
3. 什么時候得到答案？

針對123的答案：

1. 當(dāng)可替換次數(shù)k>=0的時候擴大窗口，更改窗口里面1的個數(shù)，讓窗口里面都是1，等于0的時候也擴，萬一窗口外面不需要改呢。
2. 當(dāng)可替換次數(shù)k<0的時候縮小窗口，可替換次數(shù)++，以便繼續(xù)擴大
3. k>=0的時候，窗口內(nèi)部都是1，len更新

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0;int windowOneCount = 0;int res = 0;while(right < nums.size()){//right是0也++,是1就windowOneCount++,自身也++if(nums[right] == 1){windowOneCount ++;}right ++;//窗口里面0的個數(shù)超過了k,就開始縮小窗口while(right - left - windowOneCount > k){if(nums[left] == 1) windowOneCount --;left ++;}res = max(res, right - left);}return res;}
};

4.數(shù)組中的山脈

先找到可能得山頂，再雙指針兩邊擴展，記錄res
留意l，r，i的邊界
二刷debug：注意雙指針兩邊擴展的手法，還有邊界問題，如果是只能到倒數(shù)第二個元素的話，i<.size()-1即可

class Solution {
public:int longestMountain(vector<int>& arr) {int l = 0, r = 0, res = 0;for(int i = 1; i < arr.size() - 1; i ++){if(arr[i] > arr[i - 1] && arr[i] > arr[i + 1]){l = i - 1;r = i + 1;while(l > 0 && arr[l] > arr[l - 1]) l --;while(r < arr.size() - 1 && arr[r] > arr[r + 1]) r ++;res = max(res, r - l + 1);}}return res;}
};

5.移除元素

移除val，返回新數(shù)組的長度
雙指針里也有這題，秒啦

class Solution {public int removeElement(int[] nums, int val) {int i = 0;for (int n : nums)if (n != val) {nums[i] = n;i++;}return i;}
}

6.兩個數(shù)組的交集II

給nums1和nums2，以數(shù)組的形式返回兩數(shù)組里都存在的數(shù)，并且這個數(shù)的次數(shù)要等于兩個數(shù)組中這個數(shù)出現(xiàn)次數(shù)更少的那個

別人的代碼是真的優(yōu)雅
這個代碼先記錄了nums1中每個元素出現(xiàn)的次數(shù)到umap中
再在nums2中for每個元素
如果元素在umap中有記錄則將其push進res，并且umap記錄數(shù)–

假如nums1中才是數(shù)字出現(xiàn)少的那個，那么umap[nums1]會先到0，以至于res不了nums2的元素，假如nums2才是數(shù)字出現(xiàn)少的那個，那么if(nums2)會先空

太優(yōu)雅了o(╥﹏╥)o

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> umap;vector<int> res;for(int i = 0; i < nums1.size(); i ++) umap[nums1[i]]++;for(int i = 0; i < nums2.size(); i ++){if(umap[nums2[i]]){res.push_back(nums2[i]);umap[nums2[i]] --;}}return res;}
};

7.有序數(shù)組的平方

給一個非遞減的數(shù)組，現(xiàn)在需要你將每個元素都平方，然后遞增排序，返回nums。注意，需要時間復(fù)雜度是O(n)

sort的家伙，以后面試也排人后面！！！！

sort的復(fù)雜度是O(nlogn)，所以不能用sort，只能用雙指針

這里有個十分關(guān)鍵的點，就是：原本的數(shù)組本身就是有序的，是一個非遞減的數(shù)組，那么即使數(shù)組中元素有正有負(fù)，絕對值最大的元素肯定是在數(shù)組的兩端的，即數(shù)組平方的最大值是在數(shù)組的兩端的。

所以我們可以使用兩個雙指針i,j一個指向起始位置，一個指向數(shù)組的末尾。
定義一個新的數(shù)組result用于儲存新的有序平方后的元素。

class Solution {
public://雙指針vector<int> sortedSquares(vector<int>& A) {int k = A.size() - 1; //指向新數(shù)組的末尾，從后往前賦值vector<int> result(A.size(), 0);for (int i = 0, j = A.size() - 1; i <= j;) { // 注意這里要i <= j，因為最后要處理兩個元素if (A[i] * A[i] < A[j] * A[j]) { //判斷條件1：尾部元素更大result[k--] = A[j] * A[j];j--;}else {result[k--] = A[i] * A[i]; //判斷條件2：頭部元素更大i++;}}return result;}
};

8.刪除有序數(shù)組中的重復(fù)項II

給你一個有序數(shù)組 nums ，請你 原地 刪除重復(fù)出現(xiàn)的元素，使得出現(xiàn)次數(shù)超過兩次的元素只出現(xiàn)兩次 ，返回刪除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。

前2個肯定不用刪，所以可以跳過，從j = 2開始比
還是太優(yōu)雅了這代碼

二刷debug：不會，很難理解

class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size() <= 2) return nums.size();int i = 2;for(int j = 2; j < nums.size(); j ++){if(nums[j] != nums[i - 2]){nums[i] = nums[j];i ++;}}return i;}
};

9.尋找重復(fù)數(shù)

不可以用sort也不可以用額外數(shù)組
這個要求真的是把我路都堵死了…
二刷debug：不會…
數(shù)組小技巧：數(shù)組也可以看做鏈表來做
以圖為例，天然就有數(shù)組鏈表0->1->3->2->4
fast = nums[nums[fast]]相當(dāng)于fast = fast->next->next
slow = nums[slow]相當(dāng)于slow = slow->next

幾刷？：容易寫成return nums[slow]，實際上最后一個是slow = nums[slow]，所以直接寫成return slow就可以了

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;while(true){fast = nums[nums[fast]];slow = nums[slow];if(fast == slow) break;}slow = 0;while(fast != slow){fast = nums[fast];slow = nums[slow];}return slow;}
};

10.水果成籃

fruits數(shù)組，fruits[i]代表一種水果，比如fruits[2] = 1，,代表香蕉
現(xiàn)在有fruits.size()棵水果樹，每次只能摘一顆樹
現(xiàn)在有2個籃子，每個籃子裝一種水果，問最多能摘多少棵數(shù)

fruit = [1,2,1]，有兩種水果樹，所以能摘三棵，都能摘，籃子裝得下

滑動窗口。要注意不需要window.size() == need，也要計算len，因為有while(window.size() > need)在，窗口不是小了就是剛剛好，不可能大，如果fruit的水果樹種類本來就不足2個，就可以返回
另外，當(dāng)縮小窗口，導(dǎo)致其中一個蘋果樹沒了，window應(yīng)該erase掉。否則還占用一個size

二刷debug：小于等于2的水果樹種類也可以，另外unordered_map類型可以使用erase

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> window;int need = 2;int len = 0;int left = 0, right = 0;while(right < fruits.size()){int c = fruits[right];right++;window[c]++;;while(window.size() > need){int d = fruits[left];left++;window[d]--;if(window[d] == 0) window.erase(d);}len = max(len, right - left);}return len;}
};