Leetcode-3尋找最長(zhǎng)不重復(fù)子串

題目要求必須是子串，也就是必須是連續(xù)的幾個(gè)不重復(fù)字符，而不是單純計(jì)算不重復(fù)字符有多少個(gè)（如果是，直接用set很容易就解決）
此題很容易想到用滑動(dòng)窗口解決

class Solution { public:int lengthOfLongestSubstring(string s) { int start=0,max=0;unordered_set<char> st;for(int i=0;i<s.length();i++){while(st.find(s[i]) != st.end())//find{st.erase(s[start]);start++;}if(i-start+1>max) max=i-start+1;st.insert(s[i]);}return max;} };

• 復(fù)雜度O(n)
• 用unordered_set而不是用set，這里不需要排序，時(shí)間復(fù)雜度可以降低
• while循環(huán)是重點(diǎn)，保證將要插入的這個(gè)字符和set中沒(méi)有任何一個(gè)是重復(fù)的，每次都刪除最左邊那個(gè)（有可能不是那個(gè)重復(fù)元素）。比如abcb,當(dāng)i=3,要插入第四個(gè)元素b的時(shí)候，先刪除了最左邊的a，再刪除b，最后這個(gè)窗口中剩下cb。這樣做是沒(méi)有問(wèn)題的，因?yàn)樽畲笤貍€(gè)數(shù)都已經(jīng)記錄下來(lái)了
• ** st.find(s[i]) != st.end() **兩者都是迭代器，當(dāng)find函數(shù)找不到時(shí)，返回的是st.end()，所以這個(gè)語(yǔ)句指的是在set中找到了s[i],集合中是有這個(gè)元素的。

## Leetcode-76最小覆蓋子串

class Solution { public:unordered_map<char,int> ms,mt;bool check(){for(const auto&p: mt){if(ms[p.first]<p.second) return false;}return true;}string minWindow(string s, string t) {int left=0,right=-1,len=s.length()+1,ansl=-1;for(const auto&c: t)//t中出現(xiàn)的字符以及對(duì)應(yīng)的個(gè)數(shù)存在map mt中{mt[c]++;}while(right<int(s.length())){if(mt.find(s[++right])!=mt.end())//當(dāng)前元素在t中，將對(duì)應(yīng)的map ms個(gè)數(shù)加1，ms的內(nèi)容就是窗口的內(nèi)容{ms[s[right]]++;}while(check()&&left<=right)//窗口包含了t，右指停止移動(dòng)，左指右移{if(right-left+1<len){len=right-left+1;ansl=left;}if(mt.find(s[left])!=mt.end()){ms[s[left]]--;//即將移除的左邊界如果是t中的，對(duì)應(yīng)的個(gè)數(shù)減一}left++;}}return ansl== -1?string():s.substr(ansl,len);} };

思路就是先右指針右移，直到左右指針區(qū)間已經(jīng)包含t的所有元素，然后右指針固定，左指針右移，移動(dòng)到不再能包含t的時(shí)候記錄區(qū)間，右指針右移，以此類推。
一個(gè)難點(diǎn)在于怎么判斷s包含了t中所有元素，由于t中字母?jìng)€(gè)數(shù)是可以重復(fù)的，所以必須要用數(shù)組記錄每個(gè)字符的個(gè)數(shù)，這里用map很方便。check函數(shù)實(shí)現(xiàn)了這個(gè)功能，但是有點(diǎn)暴力

為什么int（s.length()），少了和int就輸出一直是空的？？
后來(lái)查資料得知string類的length（）函數(shù)返回的是無(wú)符號(hào)整數(shù)，以后要用的時(shí)候強(qiáng)制轉(zhuǎn)化一下比較保險(xiǎn)。用在for循環(huán)一般不會(huì)出錯(cuò)，但是用作條件判斷就會(huì)出錯(cuò)
c++ string類length()(size())函數(shù)返回值–無(wú)符號(hào)數(shù)

Leetcode-1004最大連續(xù)1的數(shù)量

這題是先看了題解的思路，然后自己敲的代碼，下面順一下解題思路

右指針右移動(dòng)的情況：0的個(gè)數(shù)還沒(méi)有達(dá)到K，達(dá)到k后的這個(gè)0如果右邊是1就繼續(xù)右移

左指針右移動(dòng)：當(dāng)右邊指針固定下來(lái)之后，左指針就該右移，如果當(dāng)前的左指針（移動(dòng)掉的那個(gè)數(shù)）指向0，則右指針至少可以右移（右指針的下一位一定是0）一位，若這位0之后是1則繼續(xù)移動(dòng)到0為止；若如果當(dāng)前的左指針（移動(dòng)掉的那個(gè)數(shù)）指向1，則右指針不動(dòng)

寫(xiě)代碼出現(xiàn)的bug：當(dāng)right有了新的值之后，沒(méi)有判斷right<int(A.size())就直接使用A[right],報(bào)了下面的錯(cuò)，解決方法就是 每當(dāng)right有了新的值之后，就要判斷right<int(A.size())一次，才能使用A[right]
================================================================= ==45==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6040000000fc at pc 0x00000038ef5d bp 0x7ffdecff7df0 sp 0x7ffdecff7de8 READ of size 4 at 0x6040000000fc thread T0 #3 0x7fd9c384882f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f) 0x6040000000fc is located 0 bytes to the right of 44-byte region [0x6040000000d0,0x6040000000fc) allocated by thread T0 here: #8 0x7fd9c384882f (/lib/x86_64-linux-gnu/libc.so.6+0x2082f) Shadow bytes around the buggy address: 0x0c087fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c087fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c087fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c087fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0c087fff8000: fa fa fd fd fd fd fd fd fa fa 00 00 00 00 00 06 =>0x0c087fff8010: fa fa fd fd fd fd fd fa fa fa 00 00 00 00 00[04] 0x0c087fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c087fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c087fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c087fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x0c087fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb Shadow gap: cc ==45==ABORTING

class Solution { public:int longestOnes(vector<int>& A, int K) {int left=0,right=0,lon=0;while(left<=right&&right<int(A.size())){while(K&&right<int(A.size()))//當(dāng)正好包含了k個(gè)o時(shí)，跳出循環(huán){if(!A[right]) K--;right++;}while(right<int(A.size()) && A[right]) right++;//之后吐過(guò)是0,右指針可以一直右移動(dòng)lon=max(lon,(right-left));if(A[left]);else{//左指針是0，右指針可以至少右移一位right++;while(right<int(A.size()) && A[right])right++;//0之后是1可以一直移動(dòng)}left++;lon=max(lon,(right-left));}return lon;}};

emm,然后發(fā)現(xiàn)別人寫(xiě)的比我簡(jiǎn)潔多了

//天知いのり 2020.5.24 class Solution { public:int longestOnes(vector<int>& A, int K) {int left(0), right(0);int max(0);while (left <= right && right < A.size()) {while (right < A.size() && (A[right] || K != 0)) {if (!A[right]) K--;right++;}max = std::max(right - left, max);if (A[left]) left++;else left++, right++;}return max;} };作者：amachi-inori 鏈接：https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/c-1004-hua-dong-chuang-kou-chao-xiang-xi-jie-shuo-/ 來(lái)源：力扣（LeetCode） 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

Leetcode面試題 滑動(dòng)窗口的最大值

這竟然是簡(jiǎn)單題？？？？？？？？？？？
這也太難了吧，一開(kāi)始覺(jué)得很簡(jiǎn)單，寫(xiě)了發(fā)現(xiàn)事情不對(duì)勁…然后還是沒(méi)有想出來(lái)，去看了思路。本題用了雙端隊(duì)列deque
屬實(shí)沒(méi)有用過(guò)，看了有哪些函數(shù)震驚可以這么方便，butbut,有了思路到具體實(shí)現(xiàn)還是有一定的距離
記一下思路

• 維護(hù)一個(gè)單調(diào)遞減的隊(duì)列，所以每次放到隊(duì)列前都要把隊(duì)列中比nums[i]來(lái)的小的刪掉，用到pop_back()
• 當(dāng)滿足了窗口大小i+1-k>=0才可以將最大值也就是隊(duì)首存入答案ans數(shù)組
• 當(dāng)隊(duì)首元素已經(jīng)不是窗口內(nèi)的數(shù)的時(shí)候要?jiǎng)h除隊(duì)首。

第三點(diǎn)就是我卡了很久的點(diǎn)，要怎么判斷隊(duì)首元素是不是在當(dāng)前窗口內(nèi)部？？？

想了很久不知道怎么辦，看了c++版本，才發(fā)現(xiàn)用隊(duì)列存數(shù)字的下標(biāo)就能完美解決這個(gè)問(wèn)題,用下標(biāo)來(lái)判斷，當(dāng)前窗口是[i+1-k,i],隊(duì)首比i±k小就要pop_front()
所以對(duì)應(yīng)的判斷元素的大小的時(shí)候要記得隊(duì)列中的值是下標(biāo)，要轉(zhuǎn)換成數(shù)值

class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ans;deque<int> que;int max=INT_MIN;if((nums.size())==0) return nums;for(int i=0;i<nums.size();i++){while(!que.empty()&&nums[que.back()]<nums[i]) que.pop_back();//刪除隊(duì)列中所有比j小的數(shù),保證隊(duì)列單調(diào)遞減if(!que.empty()&&que.front()<i+1-k) que.pop_front();//超出窗口范圍的刪除que.push_back(i);//存的是下標(biāo)if(i+1>=k) ans.push_back(nums[que.front()]);}return ans;} };

然后今天看到了這題的動(dòng)態(tài)規(guī)劃解答，不得不說(shuō)，真的nb，為什么我的腦子和人家長(zhǎng)的不太一樣…
先講思路，把數(shù)組劃分為一個(gè)個(gè)k大小的塊，當(dāng)nums.size()%k!=0時(shí)候，最后一塊沒(méi)有填滿。

• 窗口為[i,j],當(dāng)窗口正好在一個(gè)塊內(nèi)的時(shí)候，用left數(shù)組存從塊的最左邊到j(luò)的最大值
• 當(dāng)窗口在兩個(gè)快中間時(shí)，要用left存從當(dāng)前塊的最左邊到當(dāng)前位置的最大值，用right存從當(dāng)前塊的最右邊到當(dāng)前位置的最大值
• 當(dāng)前窗口在左邊塊內(nèi)的最大值是right[i],在右塊內(nèi)的最大值是left[j]
• 當(dāng)前窗口的最大值是max(right[i],left[j])

class Solution { public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> ans,left,right;int ax=INT_MIN;for(int i=0;i<nums.size();i++){if(i%k==0) ax=nums[i];else ax=max(ax,nums[i]);left.push_back(ax);}//構(gòu)造left數(shù)組for(int j=int(nums.size())-1;j>=0;j--){if((j+1)%k==0) ax=nums[j];else ax=max(ax,nums[j]);right.push_back(ax);}//構(gòu)造right數(shù)組.right是倒序 原來(lái)的i現(xiàn)在在size-1-i的位置int len=right.size()-1;for(int i=0;i<nums.size()+1-k;i++){ans.push_back(max(right[len-i],left[i+k-1]));}return ans;} };

這題不用隊(duì)列，只用數(shù)組，竟然比之前的結(jié)果差了點(diǎn)，評(píng)論中的人騙我雙百

總結(jié)

以上是生活随笔為你收集整理的算法之滑动窗口的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。