【新手友好】力扣451：從積木到字符排序的思維躍遷_第1頁
【新手友好】力扣451：從積木到字符排序的思維躍遷_第2頁
【新手友好】力扣451：從積木到字符排序的思維躍遷_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

【新手友好】力扣451：從積木整理到字符排序的思維躍遷題目深度解讀題目要求將字符串中的字符按出現(xiàn)頻率降序排列，相同頻率的字符無需保持原順序。例如：輸入"tree"→輸出"eert"（e出現(xiàn)2次，t和r各1次）輸入"cccaaa"→輸出"cccaaa"或"aaaccc"關(guān)鍵點說明：ASCII字符共128個（0-127），因此使用長度為128的數(shù)組足夠不需要保持同頻字符的原順序，簡化了排序邏輯生活場景類比想象整理一箱彩色積木：1.統(tǒng)計階段：把不同顏色的積木分類堆放（類似統(tǒng)計字符頻率）2.排序階段：先搬數(shù)量最多的積木堆（如紅色積木20個），再搬次多的（藍(lán)色15個）...3.組裝階段：按數(shù)量順序把積木排成新隊列解題步驟拆解頻率統(tǒng)計：創(chuàng)建大小為128的數(shù)組，統(tǒng)計每個ASCII字符出現(xiàn)次數(shù)最大值查找：每次遍歷數(shù)組找到當(dāng)前最大頻率的字符字符串構(gòu)建：將該字符重復(fù)其頻率次數(shù)追加到結(jié)果消除已處理：將該字符頻率置零防止重復(fù)處理循環(huán)終止：當(dāng)結(jié)果字符串長度等于原字符串時停止注意事項數(shù)組初始化必須清零，否則會有隨機(jī)值內(nèi)層循環(huán)的終止條件是i<128（覆蓋所有ASCII字符）時間復(fù)雜度O(n+k2)，其中k是字符集大?。ū绢}k=128）代碼實現(xiàn)（含注釋）classSolution{public:intbocket[128]={0};//ASCII碼頻率統(tǒng)計桶stringfrequencySort(strings){//統(tǒng)計階段for(inti=0;i<s.size();i++){bocket[s[i]]++;//每個字符對應(yīng)ASCII碼位置的計數(shù)+1}strings1="";//結(jié)果字符串//構(gòu)建階段while(s1.size()<s.size()){intmaxidx=0;//當(dāng)前最大頻率字符的ASCII碼//查找階段for(inti=1;i<128;i++){if(bocket[i]>bocket[maxidx]){maxidx=i;//更新最大值下標(biāo)}}//拼接階段for(inti=0;i<bocket[maxidx];i++){s1+=maxidx;//按頻率追加字符}bocket[maxidx]=0;//已處理標(biāo)記}

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論