【新手友好】力扣451:从积木到字符排序的思维跃迁_第1页
【新手友好】力扣451:从积木到字符排序的思维跃迁_第2页
【新手友好】力扣451:从积木到字符排序的思维跃迁_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

【新手友好】力扣451:从积木整理到字符排序的思维跃迁题目深度解读题目要求将字符串中的字符按出现频率降序排列,相同频率的字符无需保持原顺序。例如:输入"tree"→输出"eert"(e出现2次,t和r各1次)输入"cccaaa"→输出"cccaaa"或"aaaccc"关键点说明:ASCII字符共128个(0-127),因此使用长度为128的数组足够不需要保持同频字符的原顺序,简化了排序逻辑生活场景类比想象整理一箱彩色积木:1.统计阶段:把不同颜色的积木分类堆放(类似统计字符频率)2.排序阶段:先搬数量最多的积木堆(如红色积木20个),再搬次多的(蓝色15个)...3.组装阶段:按数量顺序把积木排成新队列解题步骤拆解频率统计:创建大小为128的数组,统计每个ASCII字符出现次数最大值查找:每次遍历数组找到当前最大频率的字符字符串构建:将该字符重复其频率次数追加到结果消除已处理:将该字符频率置零防止重复处理循环终止:当结果字符串长度等于原字符串时停止注意事项数组初始化必须清零,否则会有随机值内层循环的终止条件是i<128(覆盖所有ASCII字符)时间复杂度O(n+k²),其中k是字符集大小(本题k=128)代码实现(含注释)classSolution{public:intbocket[128]={0};//ASCII码频率统计桶stringfrequencySort(strings){//统计阶段for(inti=0;i<s.size();i++){bocket[s[i]]++;//每个字符对应ASCII码位置的计数+1}strings1="";//结果字符串//构建阶段while(s1.size()<s.size()){intmaxidx=0;//当前最大频率字符的ASCII码//查找阶段for(inti=1;i<128;i++){if(bocket[i]>bocket[maxidx]){maxidx=i;//更新最大值下标}}//拼接阶段for(inti=0;i<bocket[maxidx];i++){s1+=maxidx;//按频率追加字符}bocket[maxidx]=0;//已处理标记}

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论