leetcode第 287 场周赛

本文主要是介绍leetcode第 287 场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说在前面

🎈今天给大家带来的是算法题，常言道：算法一时刷一时爽，时时刷时时爽🤣。保持一定的刷题频率可以在一定程度上提升自己的逻辑思考能力，还能经常学习到新的算法思路，扩展自己的解题思考库💻~
这周的周赛题目比较简单，所以在这里简单的总结一番。

周赛题目

6055. 转化时间需要的最少操作数

题目描述

给你两个字符串 current 和 correct ，表示两个 24 小时制时间。
24 小时制时间按 “HH:MM” 进行格式化，其中 HH 在 00 和 23 之间，而 MM 在 00 和 59 之间。最早的 24 小时制时间为 00:00 ，最晚的是 23:59 。
在一步操作中，你可以将 current 这个时间增加 1、5、15 或 60 分钟。你可以执行这一操作任意次数。
返回将 current 转化为 correct 需要的最少操作数。

示例 1：

输入：current = "02:30", correct = "04:35"
输出：3
解释：
可以按下述 3 步操作将 current 转换为 correct ：
- 为 current 加 60 分钟，current 变为 "03:30" 。
- 为 current 加 60 分钟，current 变为 "04:30" 。 
- 为 current 加 5 分钟，current 变为 "04:35" 。
可以证明，无法用少于 3 步操作将 current 转化为 correct 。

示例 2：

输入：current = "11:00", correct = "11:01"
输出：1
解释：只需要为 current 加一分钟，所以最小操作数是 1 。

提示：

current 和 correct 都符合 "HH:MM" 格式
current <= correct

思路分析

题目是需要我们计算将时间current转换到correct需要进行的操作数，每一次进行的操作只能将 current 这个时间增加 1、5、15 或 60 分钟,我们可以先将两个时间都转换成分钟的形式再进行计算。

模拟

我们可以根据题目模拟操作，当current与correct相差分钟数大于60分钟时，则current加上60分钟；如果current和correct相差大于15分钟小于60分钟，则current加上15分钟；如果current和correct相差大于5分钟小于15分钟,则current加上5分钟；如果current和correct相差小于5分钟，则current加上1分钟。

/*** @param {string} current* @param {string} correct* @return {number}*/
var convertTime = function (current, correct) {current = current.split(":");current = parseInt(current[0] * 60) + parseInt(current[1]);correct = correct.split(":");correct = parseInt(correct[0] * 60) + parseInt(correct[1]);let res = 0;while (current < correct) {if (correct - current >= 60) current += 60;else if (correct - current >= 15) current += 15;else if (correct - current >= 5) current += 5;else if (correct - current >= 1) current += 1;res++;}return res;
};

直接计算

当然，我们也可以直接计算，先求出两个时间的分钟差，然后求出可以被60整除的部分，减去可以被60整除的部分之后再求出可以被15整除的部分……按从大大小的顺序依次求值即可。

/*** @param {string} current* @param {string} correct* @return {number}*/
var convertTime = function(current, correct) {current = current.split(":");current = parseInt(current[0] * 60) + parseInt(current[1]);correct = correct.split(":");correct = parseInt(correct[0] * 60) + parseInt(correct[1]);let res = 0;let dif = correct - current;let op = [60,15,5,1];for(let i = 0; i < op.length; i++){res += Math.floor(dif / op[i]);dif %= op[i];}return res;
};

5235. 找出输掉零场或一场比赛的玩家

题目描述

给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 answer ：
answer[0] 是所有没有输掉任何比赛的玩家列表。
answer[1] 是所有恰好输掉一场比赛的玩家列表。
两个列表中的值都应该按递增顺序返回。

注意：

只考虑那些参与 至少一场 比赛的玩家。
生成的测试用例保证 不存在 两场比赛结果 相同 。

示例 1：

输入：matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。

示例 2：

输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。

提示：

1 <= matches.length <= 105
matches[i].length == 2
1 <= winneri, loseri <= 105
winneri != loseri
所有 matches[i] 互不相同

思路分析

可以使用哈希表来进行解题，使用哈希表分别记录玩家赢得比赛和输掉比赛的次数，然后将输过比赛的玩家从赢家哈希表中删除，再将输掉比赛次数大于1的玩家从输家哈希表中删除即可。

/*** @param {number[][]} matches* @return {number[][]}*/
var findWinners = function (matches) {let winner = {},loser = {};for (let i = 0; i < matches.length; i++) {let m = matches[i];winner[m[0]] = 1;loser[m[1]] = (loser[m[1]] || 0) + 1;}let temp = [];for (let k in loser) {delete winner[k];if (loser[k] == 1) temp.push(k);}let res = [];res.push([...Object.keys(winner)]);res.push(temp);return res;
};

5219. 每个小孩最多能分到多少糖果

题目描述

给你一个下标从 0 开始的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的子堆，但无法再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到相同数量的糖果。每个小孩可以拿走至多一堆糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的最大糖果数目。
示例 1：

输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。

示例 2：

输入：candies = [2,5], k = 11
输出：0
解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。

提示：

1 <= candies.length <= 10^5
1 <= candies[i] <= 10^7
1 <= k <= 10^12

思路分析

简单来说就是我们要将糖果堆分成k堆或k堆以上，而且无法将两堆合并到一起，我们需要求得是其中最大的k堆中的最小值。
这里我们可以使用二分来求得最大的k堆中的最小值，如以下例子:

candies = [1,2,3,4,10]
k = 5

糖果可以分成这样,将4分为[1,3],将10分为[1,3,3,3],结果如下：

[1,2,3,3,1,3,3,3,1]

这时的最大5堆为[3,3,3,3,3],所以答案应该是3。

/*** @param {number[]} candies* @param {number} k* @return {number}*/
var maximumCandies = function (candies, k) {let l = 0,r = 100000000;const check = function (num) {let t = 0;for (let i = 0; i < candies.length; i++) {t += Math.floor(candies[i] / num);}return t >= k;};while (l < r) {let mid = Math.floor((l + r) / 2);if (check(mid)) l = mid + 1;else r = mid;}return r - 1;
};

5302. 加密解密字符串

题目描述

给你一个字符数组 keys ，由若干互不相同的字符组成。还有一个字符串数组 values ，内含若干长度为 2 的字符串。另给你一个字符串数组 dictionary ，包含解密后所有允许的原字符串。请你设计并实现一个支持加密及解密下标从 0 开始字符串的数据结构。
字符串加密按下述步骤进行：
对字符串中的每个字符 c ，先从 keys 中找出满足 keys[i] == c 的下标 i 。
在字符串中，用 values[i] 替换字符 c 。
字符串解密按下述步骤进行：
将字符串每相邻 2 个字符划分为一个子字符串，对于每个子字符串 s ，找出满足 values[i] == s 的一个下标 i 。如果存在多个有效的 i ，从中选择任意一个。这意味着一个字符串解密可能得到多个解密字符串。
在字符串中，用 keys[i] 替换 s 。
实现 Encrypter 类：
Encrypter(char[] keys, String[] values, String[] dictionary) 用 keys、values 和 dictionary 初始化 Encrypter 类。
String encrypt(String word1) 按上述加密过程完成对 word1 的加密，并返回加密后的字符串。
int decrypt(String word2) 统计并返回可以由 word2 解密得到且出现在 dictionary 中的字符串数目。
示例：

输入：
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
输出：
[null, "eizfeiam", 2]
解释：
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // 返回 "eizfeiam"。 // 'a' 映射为 "ei"，'b' 映射为 "zf"，'c' 映射为 "ei"，'d' 映射为 "am"。
encrypter.decrypt("eizfeiam"); // return 2. // "ei" 可以映射为 'a' 或 'c'，"zf" 映射为 'b'，"am" 映射为 'd'。 // 因此，解密后可以得到的字符串是 "abad"，"cbad"，"abcd" 和 "cbcd"。 // 其中 2 个字符串，"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2 。

提示：

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
所有 keys[i] 和 dictionary[i] 互不相同
1 <= word1.length <= 2000
1 <= word2.length <= 200
所有 word1[i] 都出现在 keys 中
word2.length 是偶数
keys、values[i]、dictionary[i]、word1 和 word2 只含小写英文字母
至多调用 encrypt 和 decrypt 总计 200 次

思路分析

题目需要我们实现一个字符串加密解密的类，加密需要根据定义的key和value进行转换加密，解密的话需要统计输入字符串解密后的结果存在定义的dictionary中的个数，如示例的eizfeiam解密后可以得到四个结果"abad"，"cbad"，"abcd" 和 "cbcd",此时定义的dictionary为 ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"],解密结果中只有"abad" 和 "abcd"，在 dictionary 中出现，所以答案是 2。
我们可以在构建类的时候，先将keys和values对应保存到哈希表中，便于后面加密的时候直接取值。并且将字典中的每个单词先进行加密，统计相同加密结果的单词数量，并将其结果保存起来，后面在解密的时候即可直接得出答案。

/*** @param {character[]} keys* @param {string[]} values* @param {string[]} dictionary*/
var Encrypter = function (keys, values, dictionary) {let dir = {},key = {};for (let i = 0; i < dictionary.length; i++) dir[dictionary[i]] = 1;for (let i = 0; i < keys.length; i++) {key[keys[i]] = values[i];}this.keys = key;this.dir = dir;this.encryptDir(dictionary);
};/*** @param {string} word1* @return {string}*/
Encrypter.prototype.encrypt = function (word1) {let res = "";for (let i = 0; i < word1.length; i++) {res += this.keys[word1[i]];}return res;
};
Encrypter.prototype.encryptDir = function (dir) {let d = {};for (let i = 0; i < dir.length; i++) {let t = this.encrypt(dir[i]);d[t] = (d[t] || 0) + 1;}this.d = d;
};
/*** @param {string} word2* @return {number}*/
Encrypter.prototype.decrypt = function (word2) {return this.d[word2] || 0;
};/*** Your Encrypter object will be instantiated and called as such:* var obj = new Encrypter(keys, values, dictionary)* var param_1 = obj.encrypt(word1)* var param_2 = obj.decrypt(word2)* ["Encrypter", "encrypt", "decrypt"]*/