说在前面
🎈今天给大家带来的是算法题,常言道:算法一时刷一时爽,时时刷时时爽🤣。保持一定的刷题频率可以在一定程度上提升自己的逻辑思考能力,还能经常学习到新的算法思路,扩展自己的解题思考库💻~
这周的周赛题目比较简单,所以在这里简单的总结一番。
周赛题目
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"]
*/
说在后面
🎉这里是JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球🏸 ,平时也喜欢写些东西,既为自己记录📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解🙇,写错的地方望指出,定会认真改进😊,在此谢谢大家的支持,我们下文再见🙌。