LeetCode 第168场周赛

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

排名 238 / 1552

Contents

1 第一题：统计位数为偶数的数字
2 第二题：划分数组为连续数字的集合
3 第三题：子串的最大出现次数
4 第四题：你能从盒子里获得的最大糖果数

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

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

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

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;
}

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。

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

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则放弃，否则用一个字典来记录这个子串出现的次数。然后按出现次数降序排序，取第一个即可。

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]  # 返回次数最多的

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 个。

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

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

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

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