讨论/题目交流/🏆 第 168 场力扣周赛/
🏆 第 168 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 统计位数为偶数的数字
4 分 - 划分数组为连续数字的集合
6 分 - 子串的最大出现次数
7 分 - 你能从盒子里获得的最大糖果数

展开讨论

今天的比赛整体比较简单,但是第三题少了个 break TLE 了 7 次,尴尬。 ̄□ ̄||


5291. 统计位数为偶数的数字

数字转字符串,统计一下长度出答案

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            nn = str(n)
            if len(nn) % 2 == 0:
                res += 1
        return res        

5292. 划分数组为连续数字的集合

先做一次计数,然后用一个小顶堆依次遍历,一次拿出 k 个。如果计数仍然 > 0 就再放回去。

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k != 0:
            return False
        cnt = dict(collections.Counter(nums))
        cnts = sorted(cnt.items(), key=lambda item: item[0])
        from queue import PriorityQueue as PQ
        pq = PQ()
        for kkk in cnt.keys():
            pq.put(kkk)    
        #print(pq.queue)    
        while len(pq.queue):
            curs = []
            for _ in range(k):
                if len(pq.queue) == 0:
                    return False
                x = pq.get()
                if len(curs) != 0 and curs[-1] != x - 1:
                    return False
                curs.append(x)
            for cc in curs:
                cnt_cc = cnt.get(cc, 0)
                cnt[cc] = cnt_cc - 1
                if cnt_cc - 1 > 0:
                    pq.put(cc)
            #print("curs", curs)        
            #print("pq", pq.queue)        
        return True      

5293. 子串的最大出现次数

看很多人用的滑窗,其实都可以。我直接遍历起始点和长度,然后直接插入字典做计数就可以了。注意两个减枝:

  1. 某个起点具有最小长度时就不需要再往下统计了,一个可能子串越少,数量越多;
  2. 根据题意,计数种类 > maxLetters,也就不用再统计了;
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        ctt = {}
        for i in range(len(s) - minSize + 1):
            for ll in range(minSize, maxSize + 1):
                sub = s[i: i + ll]
                cnt = collections.Counter(sub)
                if len(cnt) > maxLetters:
                    break
                ctt[sub] = ctt.get(sub, 0) + 1    
                break
        return max([val for k, val in ctt.items()]) if len(ctt) > 0 else 0

5294. 你能从盒子里获得的最大糖果数

这道题目,其实就是一道简单 BFS,根本算不上 Hard!!hasBoxhasKey 看成两个条件,已经打开的其实就等价于有钥匙的。然后做一个任务队列,每开一个盒子,查一下最新状态,继续追加到队列里循环处理即可。没有什么坑。

搜索的题目我一率用 cpp 写,别问我为什么! 👀

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        map<int, int> hasKey;
        map<int, int> hasBox;
        int res = 0;
        for (int i = 0; i < status.size(); ++ i) {
            if (status[i] == 1) {
                hasKey[i] = 1;
            }
        }
        for (int i = 0; i < initialBoxes.size(); ++ i) {
            int b = initialBoxes[i];
            hasBox[b] = 1;
        }
        queue<int> que;
        map<int, int> isFinished;
        map<int, int> :: iterator it = hasKey.begin();
        for(; it != hasKey.end(); it ++) {
            if (hasBox[it -> first]) {
                que.push(it -> first);
            }
        }
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            if (isFinished[cur]) continue;
            if (hasKey[cur] && hasBox[cur]) {
                res += candies[cur];
                isFinished[cur] = 1;
                for (int i = 0; i < keys[cur].size(); ++ i) {
                    hasKey[keys[cur][i]] = 1;
                }
                for (int i = 0; i < containedBoxes[cur].size(); ++ i) {
                    hasBox[containedBoxes[cur][i]] = 1;
                }
                for (it = hasKey.begin(); it != hasKey.end(); it ++) {
                    if (!isFinished[it -> first] && hasKey[it -> first] && hasBox[it -> first]) {
                        que.push(it -> first);
                    }
                }
            }
            
        }
        return res;
    }
};


最后,如果大家对移动端和刷算法题感兴趣,可以微信关注我的技术公众号。

image.png

4
展开全部 16 讨论