力扣第 470 场周赛

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

3701. 计算交替和 - 力扣（LeetCode） ​

题目类型 ​

#遍历

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def alternatingSum(self, nums: List[int]) -> int:
        return sum(nums[::2]) - sum(nums[1::2])

3702. 按位异或非零的最长子序列 - 力扣（LeetCode） ​

题目类型 ​

#位运算 #贪心

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)
        v = reduce(xor, nums)
        if sum(nums) == 0:
            return 0
        return n if v else n - 1

3703. 移除 K-平衡子字符串 - 力扣（LeetCode） ​

题目类型 ​

#栈

解题思路 ​

用栈记录不同括号数量，当出现右括号时，尝试批量移除栈顶括号。

参考：邻项消除问题的套路：栈（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def removeSubstring(self, s: str, k: int) -> str:
        st = []
        for c in s:
            if st and st[-1][0] == c:
                st[-1][1] += 1
            else:
                st.append([c, 1])
            if c == ")" and len(st) > 1 and st[-1][1] == k and st[-2][1] >= k:
                st.pop()
                st[-1][1] -= k
                if st[-1][1] == 0:
                    st.pop()
        return "".join(c * x for c, x in st)

3704. 统计和为 N 的无零数对 - 力扣（LeetCode） ​

题目类型 ​

#数位DP

解题思路 ​

从高往低数位 DP，x 表示第一个数是否填了数字，y 表示第二个数是否填了数字，carry 表示前一个数位是否借位。

从低往高数位 DP 见参考。

参考：从低往高的数位 DP（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def countNoZeroPairs(self, n: int) -> int:
        nums = list(map(int, str(n)))
        m = len(nums)

        @cache
        def dfs(i, x, y, carry):
            if i == m:
                return int(x == y > carry)
            res = 0
            s = nums[i] + carry * 10
            for nx in range(x, 10):
                for b in range(2):
                    ny = s - nx - b
                    if y <= ny < 10:
                        res += dfs(i + 1, int(nx > 0), int(ny > 0), b)
            return res

        ans = dfs(0, 0, 0, 0)
        dfs.cache_clear()
        return ans
python
class Solution:
    def countNoZeroPairs(self, n: int) -> int:
        nums = list(map(int, str(n)))
        m = len(nums)

        def cal(x):
            return max(0, min(x - 1, 19 - x))

        @cache
        def dfs(i, b, is_num):
            if i < 0:
                return 1 - b

            h = nums[i] - b
            if not is_num:
                if i > 0 and h == 0:
                    return 0
                return dfs(i - 1, h < 0, False)

            res = 0
            if i < m - 1:
                if h != 0:
                    res = dfs(i - 1, h < 0, False) * 2
                elif i == 0:
                    res = 1

            res += dfs(i - 1, False, True) * cal(h)
            res += dfs(i - 1, True, True) * cal(h + 10)
            return res

        ans = dfs(m - 1, False, True)
        dfs.cache_clear()
        return ans
力扣第 471 场周赛
力扣第 469 场周赛