一、本周周赛总结

• T1 模拟。
• T2 贪心。
• T3 滑窗。
• T4 floyd+枚举。

100130. 找到两个数组中的公共元素

100130. 找到两个数组中的公共元素

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        return [sum(1 for num in nums1 if num in s2), sum(1 for num in nums2 if num in s1)]

100152. 消除相邻近似相等字符

100152. 消除相邻近似相等字符

1. 题目描述

2. 思路分析

贴模板。

• 都乘到一起找质因数就是分别找质因数然后去重，因此用set记录并集即可。

3. 代码实现

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        n = len(word)
        s = list(word)
        i = 1
        ans = 0
        while i < n:
            if abs(ord(s[i])-ord(s[i-1])) <= 1:
                ans += 1
                i += 1
            i += 1                
        
        return ans

100147. 最多 K 个重复元素的最长子数组

100147. 最多 K 个重复元素的最长子数组

1. 题目描述

2. 思路分析

• 很板的滑窗。用一个哈希表统计次数即可。

3. 代码实现

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        l = 0
        cnt = Counter()
        ans = 0
        for i, v in enumerate(nums):
            cnt[v] += 1
            while cnt[v] > k:
                cnt[nums[l]] -= 1
                l += 1
            ans = max(ans, i - l + 1)
        return ans

100140. 关闭分部的可行集合数目

100140. 关闭分部的可行集合数目

1. 题目描述

2. 思路分析

• n=10，因此考虑暴力枚举每种方案。也就1024种。
• 每个方案求距离可以floyd。
• roads有1000条，但n=10其实最多55条有效的（最短的）。直接预处理邻接矩阵即可。

3. 代码实现

class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        d = [[inf]*n for _ in range(n)]
        for u,v,w in roads:
            d[u][v] = min(d[u][v], w)
            d[v][u] = min(d[v][u], w)        
                
        def f(t):
            ps = []
            dis = [[inf] * n for _ in range(n)]
            for u in range(n):
                if t >> u & 1:
                    dis[u][u] = 0
                    ps.append(u)
                    for v in range(n):
                        if t >> v & 1:
                            dis[u][v] = min(dis[u][v], d[u][v])

            for k in ps:
                for u in ps:
                    for v in ps:
                        dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v])

            for u in ps:
                for v in ps:
                    if dis[u][v] > maxDistance:
                        return False
            return True

        ans = 1
        for i in range(1,1 << n):
            ans += f(i)
        return ans 

参考链接