【leetcode】451. Sort Characters By Frequency

时间:2021-11-20 10:13:31

   Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.

  

  考察了map的创建,map转存到vector,函数参数传递进去自定义排序(关系仿函数)这题还是比较需要基本功的。
  
class Solution {
public:
// 仿函数
typedef pair<char,int> PAIR;
struct CmpByValue{
bool operator()(const PAIR& lhs,const PAIR& rhs){
return lhs.second>=rhs.second;//
}
};
string frequencySort(string s) {
//按照频率统计字符串 第一件事情就是要提取出字符 计算频率
//哈希表进行排序?
// 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则
map<char,int> dp;
for(char ss:s){
if(dp.find(ss)==dp.end()){
dp[ss]=1;
}
else{
dp[ss]++;
}
}
// 将map元素转存到vector中
vector<PAIR> dp2(dp.begin(),dp.end());
// 对vector排序
sort(dp2.begin(),dp2.end(),CmpByValue());
//根据排序后的元素拼接新的字符串
string res="";
for(auto dd:dp2){
string tmp(dd.second,dd.first);
res+=tmp;
}
return res;
}
}; 
  为了避免map中key键值重复的问题 利用优先队列(默认大顶堆)重建以出现次数为key的优先队列,减少时间复杂度。
class Solution {
public: string frequencySort(string s) {
//按照频率统计字符串 第一件事情就是要提取出字符 计算频率
//哈希表进行排序?
// 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则
map<char,int> dp;
for(char ss:s){
dp[ss]++; }
//利用优先队列 大顶堆直接做
priority_queue<pair<int,char>> q;//这样避免了key不能重复的问题
string res="";
for(auto dd:dp){
q.push({dd.second,dd.first});
}
while(!q.empty()){
auto c=q.top();
string tmp(c.first,c.second);
res+=tmp;
q.pop();
} return res; }
};

  

【leetcode】451. Sort Characters By Frequency的更多相关文章

  1. 【LeetCode】451&period; Sort Characters By Frequency 解题报告(Python & C&plus;&plus;)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客: http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 字典 优先级队列 排序 日期 题目地址:https: ...

  2. 【leetcode】905&period; Sort Array By Parity

    题目如下: 解题思路:本题和[leetcode]75. Sort Colors类似,但是没有要求在输入数组本身修改,所以难度降低了.引入一个新的数组,然后遍历输入数组,如果数组元素是是偶数,插入到新数 ...

  3. 【LeetCode】排序 sort(共20题)

    链接:https://leetcode.com/tag/sort/ [56]Merge Intervals (2019年1月26日,谷歌tag复习) 合并区间 Input: [[1,3],[2,6], ...

  4. &num;Leetcode&num; 451&period; Sort Characters By Frequency

    https://leetcode.com/problems/sort-characters-by-frequency/ Given a string, sort it in decreasing or ...

  5. LeetCode 451&period; Sort Characters By Frequency (根据字符出现频率排序)

    Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: ...

  6. &lbrack;LeetCode&rsqb; 451&period; Sort Characters By Frequency 根据字符出现频率排序

    Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: ...

  7. 451&period; Sort Characters By Frequency

    题目: Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Inp ...

  8. 451&period; Sort Characters By Frequency将单词中的字母按照从高频到低频的顺序输出

    [抄题]: Given a string, sort it in decreasing order based on the frequency of characters. Example 1: I ...

  9. 【LeetCode】75&period; Sort Colors &lpar;3 solutions&rpar;

    Sort Colors Given an array with n objects colored red, white or blue, sort them so that objects of t ...

随机推荐

  1. PHP 进程间通信——消息队列&lpar;msg&lowbar;queue&rpar;

    PHP 进程间通信--消息队列 本文不涉及PHP基础库安装.详细安装说明,请参考官网,或期待后续博客分享. 1.消息队列函数准备 <?php//生成一个消息队列的key$msg_key = ft ...

  2. 加特殊符号星号斜杠反斜杠&sol;&ast; &bsol; &ast;&sol; &excl;important等让css实现兼容各个浏览器的技巧的代码

       在编写css样式表的时候常常会碰到一写浏览器兼容的问题,象是不同内核的浏览器显示就不一定相同,不同版本的的浏览器也会产生上下兼容的问题,如何解决这些问题成了我们苦恼的问题,如果你对css hac ...

  3. 利用git下载skia库

    1.准备好cygwin或者gitbash(github下载) 2.进入进入https://android.googlesource.com/,搜索skia,进入. 3.进入后最上面会显示下载方法:gi ...

  4. RxJava操作符&lpar;03-变换操作&rpar;

    转载请标明出处: http://blog.csdn.net/xmxkf/article/details/51649975 本文出自:[openXu的博客] 目录: Buffer FlatMap fla ...

  5. Java进阶&lpar;十七&rpar;ArrayList与LinkedList的区别

    ArrayList与LinkedList的区别 ArrayList ArrayList其实是包装了一个数组 Object[],当实例化一个ArrayList时,一个数组也被实例化,当向ArrayLis ...

  6. django url分发&comma;视图&comma;模板回顾

    Django基础轮廓 MTV+controller 一 url分发系统: 1 简单使用 url(r'^articles/2003/$', views.special_case_2003), # spe ...

  7. linux下将普通用户加入到docker组,使它可以运行docker命令

    方法特别简单 gpasswd -a ${USER} docker eg: gpasswd -a jenkins docker 然后使用jenkins用户就可以执行docker命令了

  8. 关于oracle设置主键自增的问题

    关于orcale设置主键自增的问题 关于主键Oracle中并没有提供一个直接的语句设置,对于这个oralce一般都是用序列和触发器来实现 一下又两种方法来实现 一 ,不使用触发器 创建序列: crea ...

  9. UVA11019 Matrix Matcher

    思路 AC自动机匹配二维模式串的题目 因为如果矩形匹配,则每一行都必须匹配,考虑对于一个点,设count[i][j]记录以它为左上角的与模式矩形大小相同的矩形中有多少行和模式矩形匹配 然后把模式矩形的 ...

  10. Linux 源码安装 FFmpeg

    加班次数频繁,已经快一年没有写博了.由于此次在项目中使用到了 FFmpeg 来处理音视频,顾记录下在 Linux 系统中源码安装 FFmpeg 以便不时之需. 1. 安装 yasm yasm 是一个汇 ...