解题思路：
首先要统计元素出现的次数，然后对出现的次数进行排序，找出出现最多的前k个数。
可以用map统计元素出现的次数，用优先队列对出现的次数进行排序。
对于优先级队列的排序，可以理解为从小到大排就是小顶堆(堆头是最小元素)，从大到小排就是大顶堆(堆头是最大元素)。
大顶堆每次更新时会弹出最大的元素，
因为要求前k个高频元素，小顶堆每次将最小的元素弹出，最后小顶堆里剩下的即为前k个最大元素。
class Solution {
public:
class comparison { //小顶堆的排序方式
public:
bool operator() (const pair& m, const pair& n) {
return m.second > n.second;
}
};
vectortopKFrequent(vector& nums, int k) {
unordered_mapmap; //统计元素出现的次数，map
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
priority_queue, vector>, comparison>pri_que; //定义小堆顶，大小为k
for (unordered_map::iterator it = map.begin(); it != map.end(); it++) { //用小堆顶遍历统计元素出现的次数的数组
pri_que.push(*it); //如果堆的元素个数小于k，就直接插入堆中
if (pri_que.size() > k) { //如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
题目2：844.比较含退格的字符串
解法：双指针法
#号只会消去左边的一个字符，与右边的字符无关，因此可以从后往前遍历字符串
定义两个指针分别从s和t的末尾开始遍历，定义两个变量counts、countt来计算两个字符串中#号的数量
从后往前遍历，无非三种情况：
1.当前字符为#号，count加1；
2.当前字符不为#号，但count不为0，count减1；
3.当前字符不为#号，count为0，当前字符不变。
注意：这一题看着不难，但是里面的条件语句什么时候用||、什么时候用&&以及最后的if (i >= 0 || j >= 0) {return false;}比较容易写错
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = s.size() - 1; //i指针指向s字符串末尾
int j = t.size() - 1; //j指针指向t字符串末尾
int counts = 0; //计算s字符串中#号数量
int countt = 0; //计算t字符串中#号数量
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (s[i] == '#') {
counts++;
i--;
}
else if (s[i] != '#' && counts != 0) {
counts--;
i--;
}
else {
break;
}
}
while (j >= 0) {
if (t[j] == '#') {
countt++;
j--;
}
else if (t[j] != '#' && countt != 0) {
countt--;
j--;
}
else {
break;
}
}
if (i >= 0 && j >= 0) {
if (s[i] != t[j]) {
return false;
}
}
else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
};
题目3：76.最小覆盖子串
解法：滑动窗口
通常滑动窗口都会有两个指针，i指针表示滑动窗口的左边界、j指针表示右边界，通过改变i、j来扩展和收缩窗口的大小。
在本题中使用滑动窗口遍历字符串，通过不断的扩展滑动窗口的大小来包含t字符串中的所有字符，然后再收缩窗口找到最小窗口。
class Solution {
public:
string minWindow(string s, string t) {
unordered_map counts, countt; //counts记录字符串s中的字符和出现的次数、countt记录字符串t中字符和出现的次数
for (auto c : t) {
countt[c]++; //遍历字符串t，记录t字符串中各个字符出现的次数
}
string result;
int cnt = 0; //在滑动窗口中s字符串满足t字符串的元素个数
for (int left = 0, right = 0; right < s.size(); right++) { //定义左右指针、遍历字符串s，[left,right]表示当前滑动窗口
counts[s[right]] ++; //向右扩展、将s[right]加入滑动窗口，即窗口中的字符数加一
if (counts[s[right]] <= countt[s[right]]) { //当s[right]出现的次数小于等于t字符串中该字符出现的次数，说明这个字符符合要求的
cnt++;
}
while (counts[s[left]] > countt[s[left]]) { //当s[left]出现的次数大于t字符串中该字符出现的次数，需要收缩窗口了
counts[s[left]]--;
left++;
}
if (cnt == t.size()) { //此时滑动窗口包含t的所有字符
if (result.empty() || right - left + 1 < result.size()) //如果结果为空 或 滑动窗口的大小小于结果的大小
result = s.substr(left, right - left + 1); //更新结果
}
}
return result;
}
};
