力扣第 477 场周赛

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

3754. 连接非零数字并乘以其数字和 I - 力扣（LeetCode） ​

题目类型 ​

#数学

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def sumAndMultiply(self, n: int) -> int:
        s = 0
        res = []
        while n:
            div, mod = divmod(n, 10)
            if mod:
                res.append(mod)
                s += mod
            n = div
        ans = "".join(map(str, res[::-1]))
        return s * (int(ans) if ans else 0)

3755. 最大平衡异或子数组的长度 - 力扣（LeetCode） ​

题目类型 ​

#哈希表 #位运算 #前缀和

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def maxBalancedSubarray(self, nums: List[int]) -> int:
        ans = 0
        pos = {(0, 0): -1}
        xor = diff = 0
        for i, x in enumerate(nums):
            xor ^= x
            diff += 1 if x % 2 else -1
            t = (xor, diff)
            if t in pos:
                ans = max(ans, i - pos[t])
            else:
                pos[t] = i
        return ans

3756. 连接非零数字并乘以其数字和 II - 力扣（LeetCode） ​

题目类型 ​

#前缀和

解题思路 ​

用三个前缀和分别统计，前缀和、前缀对应数字和前缀的非零数字个数

参考：三个前缀和（Python/Java/C++/Go）

示例代码 ​

python
MX = 100_001
MOD = 1_000_000_007
pow10 = [1] * MX
for i in range(1, MX):
    pow10[i] = (pow[i - 1] * 10) % MOD

class Solution:
    def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)
        pre = [0] * (n + 1)
        pre_num = [0] * (n + 1)
        pre_non_zero = [0] * (n + 1)
        for i, d in enumerate(map(int, s)):
            pre[i + 1] = pre[i] + d
            pre_num[i + 1] = (pre_num[i] * 10 + d) % MOD if d else pre_num[i]
            pre_non_zero[i + 1] = pre_non_zero[i] + (d > 0)

        ans = []
        for l, r in queries:
            r += 1
            d = pre_non_zero[r] - sum_non_zero[l]
            x = pre_num[r] - pre_num[l] * pow10[d]
            ans.append(x * (pre[r] - pre[l]) % MOD)
        return ans

3757. 有效子序列的数量 - 力扣（LeetCode） ​

题目类型 ​

#DP #SOSDP #数学 #组合数学 #容斥原理

解题思路 ​

参考：正难则反 + 容斥原理 + SOS DP（Python/Java/C++/Go）

示例代码 ​

python
TODO
力扣第 478 场周赛
力扣第 170 场双周赛