LeetCode 第168场周赛

这次题目都做的挺顺的,就是今天考研学校没有WiFi,整网花了半天,第四题没来得及交😭。

排名 238 / 1552

第一题:统计位数为偶数的数字

  输入:nums = [12,345,2,6,7896]
  输出:2
  解释:
  12 是 2 位数字(位数为偶数) 
  345 是 3 位数字(位数为奇数)  
  2 是 1 位数字(位数为奇数) 
  6 是 1 位数字 位数为奇数) 
  7896 是 4 位数字(位数为偶数)  
  因此只有 12 和 7896 是位数为偶数的数字

思路:反复整除10统计次数即可

第二题:划分数组为连续数字的集合

  给你一个整数数组 nums 和一个正整数 k,请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
  如果可以,请返回 True;否则,返回 False。
  
  示例 1:
  
  输入:nums = [1,2,3,3,4,4,5,6], k = 4
  输出:true
  解释:数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

思路:将集合nums划分成 k×n 的子集和,首先要保证nums的元素个数是k的倍数。使用从小到大的取值方式,从nums中最小的数开始取起。例如k=4,nums中最小的是1,则取子集1=[1, 2, 3, 4];然后在nums剩余数字中从最小的开始取起,连续取k个,如果nums中已经无法取到某个元素,则返回False。

第三题:子串的最大出现次数

  给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
  
  子串中不同字母的数目必须小于等于 maxLetters 。
  子串的长度必须大于等于 minSize 且小于等于 maxSize 。
  
  示例 1:
  
  输入:s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4
  输出:2
  解释:子串 “aab” 在原字符串中出现了 2 次。
  它满足所有的要求:2 个不同的字母,长度为 3 (在 minSize 和 maxSize 范围内)。

思路:有点像统计词频,经观察可以得到如果有长度>minSize的子串x出现次数为n,一定有长度为minSize的子串x_sub(x_sub是x的子串)的出现次数(至少)为n。所以用minSize查找即可,maxSize不需要。

在原字符串中逐个查找长度为minSize的子串,如果不同字母数大于maxLetters则放弃,否则用一个字典来记录这个子串出现的次数。然后按出现次数降序排序,取第一个即可。

第四题:你能从盒子里获得的最大糖果数

  给你 n 个盒子,每个盒子的格式为 [status, candies, keys, containedBoxes] ,其中:
  
  状态字 status[i]:整数,如果 box[i] 是开的,那么是 1 ,否则是 0 。
  糖果数 candies[i]: 整数,表示 box[i] 中糖果的数目。
  钥匙 keys[i]:数组,表示你打开 box[i] 后,可以得到一些盒子的钥匙,每个元素分别为该钥匙对应盒子的下标。
  内含的盒子 containedBoxes[i]:整数,表示放在 box[i] 里的盒子所对应的下标。
  给你一个 initialBoxes 数组,表示你现在得到的盒子,你可以获得里面的糖果,也可以用盒子里的钥匙打开新的盒子,还可以继续探索从这个盒子里找到的其他盒子。
  
  请你按照上述规则,返回可以获得糖果的 最大数目 。
  
  示例 1:
  
  输入:status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
  输出:16
  解释:
  一开始你有盒子 0 。你将获得它里面的 7 个糖果和盒子 1 和 2。
  盒子 1 目前状态是关闭的,而且你还没有对应它的钥匙。所以你将会打开盒子 2 ,并得到里面的 4 个糖果和盒子 1 的钥匙。
  在盒子 1 中,你会获得 5 个糖果和盒子 3 ,但是你没法获得盒子 3 的钥匙所以盒子 3 会保持关闭状态。
  你总共可以获得的糖果数目 = 7 + 4 + 5 = 16 个。
  示例 2:
  
  输入:status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
  输出:6
  解释:
  你一开始拥有盒子 0 。打开它你可以找到盒子 1,2,3,4,5 和它们对应的钥匙。
  打开这些盒子,你将获得所有盒子的糖果,所以总糖果数为 6 个。

思路:题目描述很复杂,仔细看的话其实不难。刚开始有一些盒子,有的是打开的有的是关闭的。每个盒子里可以有一些糖果,或者另外的盒子,或者另外一些盒子的钥匙。

从已有的盒子开始轮流遍历盒子,有糖果就拿糖果,有钥匙则拿钥匙。注意有的盒子暂时打不开,但是之后能打开的盒子中可能有它的钥匙🔑。如果所有能打开的盒子里都没有钥匙则结束循环。

发表评论

电子邮件地址不会被公开。 必填项已用*标注