这次题目都做的挺顺的,就是今天考研学校没有WiFi,整网花了半天,第四题没来得及交😭。
排名 238 / 1552
第一题:统计位数为偶数的数字
输入:nums = [12,345,2,6,7896]
输出:2
解释:
12 是 2 位数字(位数为偶数)
345 是 3 位数字(位数为奇数)
2 是 1 位数字(位数为奇数)
6 是 1 位数字 位数为奇数)
7896 是 4 位数字(位数为偶数)
因此只有 12 和 7896 是位数为偶数的数字
思路:反复整除10统计次数即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int findNumbers(vector<int>& nums) { int ans=0; for(int i=0;i<nums.size();i++){ int num = nums[i]; int ws = 0; while (num){ num /= 10; ws ++; } if (ws % 2==0 && nums[i]) ans+=1; } return ans; } |
第二题:划分数组为连续数字的集合
给你一个整数数组 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。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution: def enough(self, d, key): if key not in d: return False return d[key] > 0 def isPossibleDivide(self, nums: List[int], k: int) -> bool: if len(nums) % k != 0: # 无法整除,直接返回False return False d = {} for num in nums: if num in d: d[num] += 1 else: d[num] = 1 # 统计每个数字的出现次数 keys = sorted(d.keys()) # 对出现的数字从小到大排序 start_i = 0 # 开始取的位置 while start_i < len(keys): start = keys[start_i] # 第一个取的数字 for i in range(k): # 连续取k个 if not self.enough(d, start+i): return False d[start+i] -= 1 if d[start+i] == 0: # nums中某个数字已经取完,就从下一个数字取起 start_i += 1 return True |
第三题:子串的最大出现次数
给你一个字符串 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则放弃,否则用一个字典来记录这个子串出现的次数。然后按出现次数降序排序,取第一个即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: d = {} for i in range(len(s)-minSize+1): sub = s[i:i+minSize] # 逐个取长度为minSize的子串 letters = [] length = 0 record = True for l in sub: if l not in letters: letters.append(l) length += 1 if length > maxLetters: # 如果该子串不同字母数大于maxLetters则抛弃 record = False break if record: if sub in d: d[sub] += 1 else: d[sub] = 1 # 按子串出现次数降序排序 results = sorted(d.items(), key=lambda kv: (kv[1], kv[0]), reverse=True) if len(results) == 0: return 0 # 如果出现次数都为0,则返回0(对应maxLetters很小所有子串都被抛弃的情况) return results[0][1] # 返回次数最多的 |
第四题:你能从盒子里获得的最大糖果数
给你 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 个。
思路:题目描述很复杂,仔细看的话其实不难。刚开始有一些盒子,有的是打开的有的是关闭的。每个盒子里可以有一些糖果,或者另外的盒子,或者另外一些盒子的钥匙。
从已有的盒子开始轮流遍历盒子,有糖果就拿糖果,有钥匙则拿钥匙。注意有的盒子暂时打不开,但是之后能打开的盒子中可能有它的钥匙🔑。如果所有能打开的盒子里都没有钥匙则结束循环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution: def __init__(self): self.ans=0 # 初始没有糖果🍬 self.mykeys=[] # 初始没有钥匙 def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int: boxes = [] for i in initialBoxes: if status[i] == 1 or i in self.mykeys: # 盒子是开着的或者有钥匙 # 能打开,则打开盒子 获取糖果和钥匙 self.mykeys.extend(keys[i]) initialBoxes.extend(containedBoxes[i]) self.ans += candies[i] else: # 暂时打不开,放到另一个缓存里 boxes.append(i) for i in boxes: if status[i] == 0 and i in self.mykeys: # 一轮结束后,如果已经拿到了缓存的盒子的钥匙 self.maxCandies(status, candies, keys, containedBoxes, boxes) # 对缓存的盒子递归 break return self.ans |