力扣第 471 场周赛

876
Contest
LeetCode
本文最后更新于 3 分钟前，文中所描述的信息可能已发生改变。

3712. 出现次数能被 K 整除的元素总和 - 力扣（LeetCode） ​

题目类型 ​

#哈希 #计数 #枚举

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def sumDivisibleByK(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        ans = 0
        for key, v in cnt.items():
            if v % k == 0:
                ans += key * v
        return ans

3713. 最长的平衡子串 I - 力扣（LeetCode） ​

题目类型 ​

#前缀和 #哈希 #枚举

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
fmax = lambda x, y: x if x > y else y


class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        pre = [[0] * (n + 1) for _ in range(26)]
        for i, c in enumerate(s):
            for j in range(26):
                pre[j][i + 1] = pre[j][i] + int(ord(c) - 97 == j)

        ans = 1
        for i in range(n):
            for j in range(n, i + 1, -1):
                s = set()
                for k in range(26):
                    t = pre[k][j] - pre[k][i]
                    if t:
                        s.add(t)
                if len(s) == 1:
                    ans = fmax(ans, j - i)
                    break
        return ans
python
class Solution:
    def longestBalanced(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(n):
            cnt = defaultdict(int)
            for j in range(i, n):
                cnt[s[j]] += 1
                if len(set(cnt.values())) == 1:
                    ans = max(ans, j - i + 1)
        return ans

3714. 最长的平衡子串 II - 力扣（LeetCode） ​

题目类型 ​

#前缀和 #哈希 #枚举 #分类讨论

解题思路 ​

分三种情况讨论：

  1. 子串只包含一种字母。
  2. 子串只包含两种字母。
  3. 子串包含三种字母。

通过建立不同约束，同时使用哈希表维护约束，枚举最大值。

参考：式子变形 + 枚举右维护左（Python/Java/C++/Go）

示例代码 ​

python
fmax = lambda x, y: x if x > y else y


class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        ans = 0
        s = [ord(c) - 97 for c in s]

        def f(a, b):
            res = 0
            cnt = [0] * 3
            vis = {0: -1}
            for i, x in enumerate(s):
                if x != a and x != b:
                    cnt = [0] * 3
                    vis = {0: i}
                else:
                    cnt[x] += 1
                    t = cnt[a] - cnt[b]
                    if t in vis:
                        res = fmax(res, i - vis[t])
                    else:
                        vis[t] = i
            return res

        for _, gs in groupby(s):
            l = len(list(gs))
            ans = fmax(ans, l)

        for a, b in combinations(range(3), 2):
            ans = fmax(ans, f(a, b))

        vis = {(0, 0): -1}
        cnt = [0] * 3
        for i, x in enumerate(s):
            cnt[x] += 1
            ca, cb, cc = cnt
            t = (ca - cc, cb - cc)
            if t not in vis:
                vis[t] = i
            else:
                ans = fmax(ans, i - vis[t])

        return ans

3715. 完全平方数的祖先个数总和 - 力扣（LeetCode） ​

题目类型 ​

#回溯 #数论 #平方剩余核

解题思路 ​

计算每个数的质因子个数，累乘个数为奇数的因子（平方剩余核），用累乘结果记录。后对树进行遍历，对当前祖先进行计数，再匹配平方剩余核，累加个数即可。

参考：平方剩余核 + 枚举右维护左（Python/Java/C++/Go）

示例代码 ​

python
MX = 10**5
core = [0] * (MX + 1)

for i in range(1, MX + 1):
    if core[i]:
        continue
    for j in range(1, MX + 1):
        if i * j * j > MX:
            break
        core[i * j * j] = i


class Solution:
    def sumOfAncestors(self, n: int, edges: List[List[int]], nums: List[int]) -> int:
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)

        ans = 0
        cnt = defaultdict(int)

        def dfs(x):
            nonlocal ans, cnt
            c = core[nums[x]]
            ans += cnt[c]
            cnt[c] += 1
            for y in g[x]:
                dfs(y)
            cnt[c] -= 1
            return

        dfs(0)
        return ans
力扣第 167 场双周赛
力扣第 470 场周赛