🦄個人主頁:修修修也
🎏所屬專欄:刷題
??操作環境:牛客網
目錄
一.NC41 最長無重復子數組
題目詳情:
題目思路:
解題代碼:
二.NC379 重排字符串
題目詳情:
題目思路:
解題代碼:
結語
一.NC41 最長無重復子數組
牛客網題目鏈接(點擊即可跳轉):NC41 最長無重復子數組
題目詳情:
本題詳情如下圖:
題目思路:
本題解題思路如下:
??????? 哈希雙指針滑動窗口, 圖解如下:
解題代碼:
本題解題代碼如下:
class Solution { public:int hash[100010]={0};int maxLength(vector<int>& arr) {int left=0,right=0;int ret=0;while(right<arr.size()){hash[arr[right]]++;//進窗口while(hash[arr[right]]>1)//判斷出窗口{hash[arr[left++]]--;//出窗口}right++;ret=max(ret,right-left);//更新結果}return ret;} };
二.NC379 重排字符串
牛客網題目鏈接(點擊即可跳轉):NC379 重排字符串
題目詳情:
本題詳情如下圖:
題目思路:
本題解題思路如下:
??????? 首先先統計所有字母出現的次數,如果有字母出現的次數大于(總數+1)/2,那么說明這個根本沒法重排,所以直接返回"".統計好字母后,先排數量多的,把它們在雙數下標間隔一個排列,然后雙數下標排滿了再把剩下的排在單數位置上,這樣就可以保證不會出現相同的字母相鄰的情況啦.解法算是一個小貪心,然后統計字母用到了數組存pair鍵值對的形式.(此處發現一個小tips:sort排pair數組的話會默認按first的值排升序,如果懶得現場手搓排序函數的可以把待排序的數據類型作為pair的first,這樣可以省一點事).
解題代碼:
本題解題代碼如下:
class Solution { public:string rearrangestring(string str) {vector<pair<int,char>> vp;string ret;ret.resize(str.size());for(int i=0;i<26;i++)vp.push_back(pair<int,char>{0,'a'+i});for(auto e:str)if(++vp[e-'a'].first > (str.size()/2))return ""; sort(vp.begin(),vp.end());int i=vp.size()-1, sin=0, even=1;while(sin<ret.size()){while(vp[i].first==0)i--;ret[sin]=vp[i].second;vp[i].first--;sin+=2;}while(even<ret.size()){while(vp[i].first==0)i--;ret[even]=vp[i].second;vp[i].first--;even+=2;}return ret;} };
結語
??????? 說點啥好呢..."有志者事竟成!沉淀復盤!" -> "人生哪有一帆風順!這次聊的很好~" -> "沒事噠沒事噠~先去學點東西也好" -> "OUT"
)
