【算法题解】 Day16 排序
1046. 最后一块石头的重量
题目
1046. 最后一块石头的重量 难度：easy
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果
x == y，那么两块石头都会被完全粉碎； - 如果
x != y，那么重量为x的石头将会完全粉碎，而重量为y的石头新重量为y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。提示：
1 <= stones.length <= 301 <= stones[i] <= 1000
方法一：最大堆
思路
将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 a 和 b，必有 a≥b。如果 a>b，则将新石头 a-b 放回到最大堆中；如果 a=b，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 2 块。
最终可能剩下 1 块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 0。
解题
Python：
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
# 初始化
heap = [-stone for stone in stones]
heapq.heapify(heap)
# 模拟
while len(heap) > 1:
x,y = heapq.heappop(heap),heapq.heappop(heap)
if x != y:
heapq.heappush(heap,x-y)
if heap: return -heap[0]
return 0Java：
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
for (int stone : stones) {
pq.offer(stone);
}
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
if (a > b) {
pq.offer(a - b);
}
}
return pq.isEmpty() ? 0 : pq.poll();
}
}692. 前K个高频单词
题目
692. 前K个高频单词 难度：medium
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。注意：
1 <= words.length <= 5001 <= words[i] <= 10words[i]由小写英文字母组成。k的取值范围是[1, 不同 words[i] 的数量]
方法一：哈希表
思路
我们可以预处理出每一个单词出现的频率，然后依据每个单词出现的频率降序排序，最后返回前 k 个字符串即可。
具体地，我们利用哈希表记录每一个字符串出现的频率，然后将哈希表中所有字符串进行排序，排序时，如果两个字符串出现频率相同，那么我们让两字符串中字典序较小的排在前面，否则我们让出现频率较高的排在前面。最后我们只需要保留序列中的前 k 个字符串即可。
解题
Java：
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> cnt = new HashMap<String, Integer>();
for (String word : words) {
cnt.put(word, cnt.getOrDefault(word, 0) + 1);
}
List<String> rec = new ArrayList<String>();
for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
rec.add(entry.getKey());
}
Collections.sort(rec, new Comparator<String>() {
public int compare(String word1, String word2) {
return cnt.get(word1) == cnt.get(word2) ? word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
}
});
return rec.subList(0, k);
}
}方法二：优先队列
思路
对于前 k 大或前 k 小这类问题，有一个通用的解法：优先队列。优先队列可以在 O(logn) 的时间内完成插入或删除元素的操作（其中 n 为优先队列的大小），并可以 O(1) 地查询优先队列顶端元素。
在本题中，我们可以创建一个小根优先队列（顾名思义，就是优先队列顶端元素是最小元素的优先队列）。我们将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。
解题
Java：
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> cnt = new HashMap<String, Integer>();
for (String word : words) {
cnt.put(word, cnt.getOrDefault(word, 0) + 1);
}
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
}
});
for (Map.Entry<String, Integer> entry : cnt.entrySet()) {
pq.offer(entry);
if (pq.size() > k) {
pq.poll();
}
}
List<String> ret = new ArrayList<String>();
while (!pq.isEmpty()) {
ret.add(pq.poll().getKey());
}
Collections.reverse(ret);
return ret;
}
}腾讯云开发者
