LeetCode周报
LCP 07. 传递信息 (2021.7.1) 1833. 雪糕的最大数量 (2021.7.2) 451. 根据字符出现频率排序 (2021.7.3) 645. 错误的集合 (2021.7.4)
LCP 07. 传递信息 (2021.7.1)
小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：
有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。每轮信息必须需要传递给另一个人，且信息可重复经过同一个人 给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chuan-di-xin-xi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 1：
输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。
示例 2：
输入：n = 3, relation = [[0,2],[2,1]], k = 2
输出：0
解释：信息不能从小 A 处经过 2 轮传递到编号 2
限制：
2 <= n <= 101 <= k <= 51 <= relation.length <= 90
, 且relation[i].length == 20 <= relation[i][0]
,relation[i][1] < n
且relation[i][0] != relation[i][1]
Answer
动态规划。定义动态规划的状态 dp[i][j]
为经过 i
轮传递到编号 j
的玩家的方案数，其中 0≤i≤k
，0≤j<n
。由于从编号 0
的玩家开始传递，当 i=0
时，一定位于编号 0 的玩家，不会传递到其他玩家，因此动态规划的边界情况如下：
对于传信息的关系[src, dst]
，如果第 i
轮传递到编号 src
的玩家，则第 i+1
轮可以从编号 src
的玩家传递到编号 dst
的玩家。因此在计算 dp[i+1][dst]
时，需要考虑可以传递到编号 dst
的所有玩家。由此可以得到动态规划的状态转移方程，其中 0≤i<k
：
最终得到 dp[k][n−1]
即为总的方案数。由于当 i>0
时，dp[i][]
的值只和 dp[i−1][]
的值有关，因此可以将二维数组变成一维数组，将空间复杂度优化到 O(n)。
class Solution {
public int numWays(int n, int[][] relation, int k) {
int[] dp = new int[n];
dp[0] = 1;
for (int i = 0; i < k; i++) {
int[] next = new int[n];
for (int[] edge : relation) {
int src = edge[0], dst = edge[1];
next[dst] += dp[src];
}
dp = next;
}
return dp[n - 1];
}
}
1833. 雪糕的最大数量 (2021.7.2)
夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
注意：Tony 可以按任意顺序购买雪糕。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-ice-cream-bars
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 1：
输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7
示例 2：
输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。
示例 3：
输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18。
提示：
costs.length == n1 <= n <= 10^51 <= costs[i] <= 10^51 <= coins <= 10^8
Answer
由于数组 costs
中的元素不会超过 10^5
，因此可以使用计数排序，将时间复杂度降低到线性。
使用数组 count
记录数组 costs
中的每个元素出现的次数，其中 count[i]
表示元素 i
在数组 costs
中出现的次数。使用贪心的思想，买最便宜的雪糕，因此按照下标从小到大的顺序遍历数组 count
，对于每个下标，如果该下标不超过剩余的硬币数，则根据下标值和该下标处的元素值计算价格为该下标的雪糕的可以购买的最大数量，然后将硬币数减去购买当前雪糕的花费，当遇到一个下标超过剩余的硬币数时，结束遍历，此时购买的雪糕数量即为可以购买雪糕的最大数量。
class Solution {
public int maxIceCream(int[] costs, int coins) {
// 计数排序 + 贪心
// 计数
int MAX_VALUE = Integer.MIN_VALUE;
for(int i = 0; i < costs.length; ++i){
if(MAX_VALUE < costs[i]){
MAX_VALUE = costs[i];
}
}
// 统计元素出现的情况
int[] count = new int[MAX_VALUE+1];
for(int i = 0; i < costs.length; ++i){
count[costs[i]]++;
}
// 对上述计数数组 count 进行贪心求解
int ans = 0;
for(int i = 1; i < count.length; ++i){
if(coins >= i){
// 核心：当前剩下的钱至多可以买多少个当前价位的雪糕
int curCount = Math.min(count[i], coins / i);
ans += curCount;
coins -= curCount * i;
}else{
// 剩下的钱不足以再买雪糕
break;
}
}
return ans;
}
}
451. 根据字符出现频率排序 (2021.7.3)
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 1：
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2：
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3：
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。
Answer
首先通过 HashMap
统计字符串中字符及其出现的次数的情况，根据字符出现的次数情况进行排序，最终得到一个新的字符串返回即可。其中统计和排序都可以使用数组来操作，这里采用的是 HashMap + ArrayList
的方式。
class Solution {
public String frequencySort(String s) {
// 遍历字符串S, map存储出现的字符及其出现的次数
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
}
// 将map的key,也即出现的字符存储到list中
List<Character> list = new ArrayList<Character>(map.keySet());
// 根据字符出现的次数对list进行排序，得到的list为字符出现的频率由高到低的结果
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
// 根据list和map返回结果即可
StringBuffer sb = new StringBuffer();
int size = list.size();
for (int i = 0; i < size; i++) {
char c = list.get(i);
int frequency = map.get(c);
for (int j = 0; j < frequency; j++) {
sb.append(c);
}
}
return sb.toString();
}
}
645. 错误的集合 (2021.7.4)
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 1：
输入：nums = [1,2,2,4]
输出：[2,3]
解释：重复出现的数字是2，丢失的数字是3
示例 2：
输入：nums = [1,1]
输出：[1,2]
解释：重复出现的数字是1，丢失的数字是2
提示：
2 <= nums.length <= 10^41 <= nums[i] <= 10^4
Answer
先用数组 count
记录 nums
中出现的数字及出现的次数情况，从下标 1
开始遍历 count
数组，如果该下标位置值为 0
，则为丢失的数字，如果该下标值为 2
，则为重复出现的数字。如果要求降低空间复杂度等，可以考虑位运算相关的操作。
class Solution {
public int[] findErrorNums(int[] nums) {
int[] ans = new int[2];
// count为计数数组，统计 nums 中元素出现的次数
int[] count = new int[nums.length + 1];
for(int i : nums){
count[i]++;
}
for(int i = 1 ; i < count.length; i++){
if(count[i] == 0){
// 缺失的数字
ans[1] = i;
}else if(count[i] == 2){
// 重复出现的数字
ans[0] = i;
}
}
return ans;
}
}
