正文

leetcode刷题笔记-数据结构-day21(代码片段)

ΘLLΘ  ΘLLΘ  2022-12-19  517

关键词：

文章目录

LeetCode刷题笔记-数据结构-day21

LeetCode刷题笔记-数据结构-day21

451. 根据字符出现频率排序

1.题目

原题链接：451. 根据字符出现频率排序

2.解题思路

算法：小根堆

具体步骤：

我们建立一个以pair<int,int>存储的小根堆，会以pair的第一个位置元素从小到大排序
pair的第一个位置存储所有点距离原点的距离（这里为了方便直接用距离的平方代替）
pair的第二个位置存储每个点所在数组的下标
将所有点存入堆后，取出堆中前k个小的元素即可，得到他们的数组坐标，将其放入最终答案

3.代码

typedef pair<int,int> PII;
class Solution 
public:
    vector<vector<int>> kClosest(vector<vector<int>>& p, int k) 
        vector<vector<int>> res;
        priority_queue<PII, vector<PII>,greater<PII>> q;
        for(int i=0;i<p.size();i++)
            int t=p[i][0]*p[i][0]+p[i][1]*p[i][1];
            q.push(t,i);
        
        while(k-->0)
            auto t=q.top();
            q.pop();
            res.push_back(p[t.second]);
        
        return res;
    
;

973. 最接近原点的 K 个点

1.题目

原题链接：973. 最接近原点的 K 个点

2.解题思路

算法：大根堆

具体步骤：

我们建立一个以pair<int,int>存储的大根堆，会以pair的第一个位置元素从大到小排序
pair的第一个位置存储每个字符出现的次数
pair的第二个位置存储字符本身
先用哈希表统计所有字符出现的次数，在加入大根堆中
最后取出大根堆元素拼接字符串即可

3.代码

法一：

typedef pair<int,int> PII;
class Solution 
public:
    string frequencySort(string s) 
        map<char,int> hash;
        for(auto x:s) hash[x]++;
        priority_queue<PII, vector<PII>> q;
        for(auto [a,b]:hash) q.push(b,a);
        string res;
        while(q.size())
            auto t=q.top();
            q.pop();
            res+=string(t.first,t.second);
        
        return res;
    
;

法二：

class Solution 
public:
    string frequencySort(string s) 
        unordered_map<char,int> cnt;
        for(auto x:s) cnt[x]++;
        sort(s.begin(),s.end(),[&](char a,char b)
           if (cnt[a] != cnt[b]) return cnt[a] > cnt[b];
            return a < b;
        );
        return s;
    
;

leetcode刷题笔记-数据结构-day19(代码片段)

文章目录LeetCode刷题笔记-数据结构-day19997.找到小镇的法官1.题目描述2.解题思路3.代码1557.可以到达所有点的最少点数目1.题目描述2.解题思路3.代码841.钥匙和房间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day19997.找到小... 查看详情

leetcode刷题笔记-数据结构-day19(代码片段)

leetcode刷题笔记-数据结构-day14(代码片段)

文章目录LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述2.解题思路3.代码1249.移除无效的括号1.题目描述2.解题思路3.代码1823.找出游戏的获胜者1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day14155.最小栈1.题目描述原题... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

文章目录LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目2.解题思路3.代码347.前K个高频元素1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day20215.数组中的第K个最大元素1.题目原题链接：215.数组中的第K个... 查看详情

leetcode刷题笔记-数据结构-day12(代码片段)

文章目录LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述2.解题思路3.代码707.设计链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1224.两两交换链表中的节点1.题目描述原题链接：24.两两交换链表... 查看详情

leetcode刷题笔记-数据结构-day20(代码片段)

leetcode刷题笔记-数据结构-day16(代码片段)

文章目录LeetCode刷题笔记-数据结构-day16199.二叉树的右视图1.题目描述2.解题思路3.代码113.路径总和II1.题目描述2.解题思路3.代码450.删除二叉搜索树中的节点1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day16199.二叉树的右视... 查看详情

leetcode刷题笔记-数据结构-day15(代码片段)

文章目录LeetCode刷题笔记-数据结构-day15108.将有序数组转换为二叉搜索树1.题目描述2.解题思路3.代码105.从前序与中序遍历序列构造二叉树1.题目描述2.解题思路3.代码103.二叉树的锯齿形层序遍历1.题目描述2.解题思路3.代码LeetCode刷... 查看详情

leetcode刷题笔记-数据结构-day6(代码片段)

文章目录LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述2.解题思路3.代码409.最长回文串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day6415.字符串相加1.题目描述原题链接：415.字符串相加2.解题思路直接套用大... 查看详情

leetcode刷题笔记-数据结构-day11(代码片段)

文章目录LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述2.解题思路3.代码82.删除排序链表中的重复元素II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day11160.相交链表1.题目描述原题链接：160.相交链表2.解题思路... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

文章目录LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述2.解题思路3.代码297.二叉树的序列化与反序列化1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day18236.二叉树的最近公共祖先1.题目描述原题链接... 查看详情

leetcode刷题笔记-数据结构-day18(代码片段)

leetcode刷题笔记-数据结构-day5(代码片段)

文章目录LeetCode刷题笔记-数据结构-day5334.递增的三元子序列1.题目描述2.解题思路3.代码238.除自身以外数组的乘积1.题目描述2.解题思路3.代码560.和为K的子数组1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day5334.递增的三元... 查看详情

leetcode刷题笔记-数据结构-day7(代码片段)

文章目录LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述2.解题思路3.代码763.划分字母区间1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day790.单词规律1.题目描述原题链接：90.单词规律2.解题思路算法：哈希表... 查看详情

leetcode刷题笔记-数据结构-day9(代码片段)

文章目录LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述2.解题思路3.代码5.最长回文子串1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day9187.重复的DNA序列1.题目描述原题链接：87.重复的DNA序列2.解题思路算法&... 查看详情

leetcode刷题笔记-数据结构-day10(代码片段)

文章目录LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述2.解题思路3.代码142.环形链表II1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day102.两数相加1.题目描述原题链接：2.两数相加2.解题思路直接模拟即可：从... 查看详情

leetcode刷题笔记-数据结构-day13(代码片段)

文章目录LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述2.解题思路3.代码143.重排链表1.题目描述2.解题思路3.代码LeetCode刷题笔记-数据结构-day1325.K个一组翻转链表1.题目描述原题链接：25.K个一组翻转链表2.解题思... 查看详情