力扣第 469 场周赛

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

3697. 计算十进制表示 - 力扣（LeetCode） ​

题目类型 ​

#遍历 #数学

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def decimalRepresentation(self, n: int) -> List[int]:
        base = 1
        ans = []
        while n:
            d = n % 10 * base
            if d:
                ans.append(d)
            n //= 10
            base *= 10
        return ans[::-1]

3698. 分割数组得到最小绝对差 - 力扣（LeetCode） ​

题目类型 ​

#前后缀

解题思路 ​

参考：这道题很简单！

示例代码 ​

python
class Solution:
    def splitArray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [False] * n
        right = [False] * n
        left[0] = True
        right[-1] = True
        pre = list(accumulate(nums, initial=0))
        for i in range(n - 1):
            left[i + 1] = left[i] and nums[i] < nums[i + 1]
        for i in range(n - 1, 0, -1):
            right[i - 1] = right[i] and nums[i] < nums[i - 1]
        ans = inf
        for i in range(1, n):
            if left[i - 1] and right[i]:
                ans = min(ans, abs(pre[i] - (pre[-1] - pre[i])))
        return ans if ans < inf else -1

3699. ZigZag 数组的总数 I - 力扣（LeetCode） ​

题目类型 ​

#DP #前缀和优化 #对称性优化

解题思路 ​

构造之字形数组，有如下两种方法：

方法一

使用对称性优化，先递增或先递减，只用计算一种情况，结果翻倍即可，转移方程如下：

nf[n−i−1]=∑k=0i−1f[k]nf[n - i - 1] = \sum_{k=0}^{i - 1}{f[k]}

方法二

同时计算递增和递减，方程转移时，需要从递增向递减转移，如此交替，转移方程如下：

f0[i][j]=∑k=0j−1f1[i−1][k]f_0[i][j] = \sum_{k=0}^{j-1}{f_1[i - 1][k]}

f1[i][j]=∑k=j+1r−lf0[i−1][k]f_1[i][j] = \sum_{k=j+1}^{r-l}{f_0[i - 1][k]}

参考：前缀和优化 DP + 利用对称性优化（Python/Java/C++/Go）

示例代码 ​

python
class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1_000_000_007
        m = r - l + 1

        f = [1] * m
        for i in range(1, n):
            if i % 2:
                pre = 0
                for j in range(m):
                    f[j], pre = pre, pre + f[j]
            else:
                suf = 0
                for j in range(m - 1, -1, -1):
                    f[j], suf = suf, suf + f[j]
        return 2 * sum(f) % MOD
python
class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1_000_000_007
        m = r - l + 1

        f = [1] * m
        for _ in range(n - 1):
            nf = [0] * m
            pre = 0
            for j, v in enumerate(f):
                nf[m - j - 1] = pre % MOD
                pre += v
            f = nf
        return 2 * sum(f) % MOD
python
class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1_000_000_007
        k = r - l + 1

        f0 = [1] * k
        f1 = [1] * k
        for _ in range(n - 1):
            pre = 0
            for i, v in enumerate(f1):
                f1[i] = pre % MOD
                pre += v
            suf = 0
            for i in range(k - 1, -1, -1):
                v = f0[i]
                f0[i] = suf % MOD
                suf += v
            f0, f1 = f1, f0

        return (sum(f0) + sum(f1)) % MOD

3700. ZigZag 数组的总数 II - 力扣（LeetCode） ​

题目类型 ​

#DP #矩阵快速幂优化

解题思路 ​

利用矩阵实现状态转移，矩阵快速幂优化计算。方法一转移方程如下，转移矩阵反对角线的左上全为 1：

[f[i]f[i−1]f[i−2]⋮f[i−m+1]]=[111⋯10111⋯00111⋯00⋮⋮⋮⋱⋮⋮000⋯00]⏞m×m⋅[f[i−1]f[i−2]f[i−3]⋮f[i−m]]\begin{bmatrix} f[i]\\f[i-1]\\f[i-2]\\\vdots\\f[i-m+1] \end{bmatrix} = \overbrace{ \begin{bmatrix} 1&1&1&\cdots&1&0\\ 1&1&1&\cdots&0&0\\ 1&1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&0&0\\ \end{bmatrix} }^{m \times m} \cdot \begin{bmatrix} f[i-1]\\f[i-2]\\f[i-3]\\\vdots\\f[i-m] \end{bmatrix}

参考：矩阵快速幂优化 DP + 利用对称性优化（Python/NumPy/Java/C++/Go）

示例代码 ​

python
class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        m = r - l + 1
        mat = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(m - i - 1):
                mat[i][j] = 1

        f0 = [[1] for _ in range(m)]
        res = MatrixPower.matrix_power(mat, n - 1, f0)
        ans = sum(sum(row) for row in res)
        return 2 * ans % 1_000_000_007
python
class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        m = r - l + 1
        mat = [[0] * (2 * m) for _ in range(2 * m)]
        for i in range(m):
            for j in range(m):
                if i == j:
                    continue
                if i > j:
                    mat[i][j + m] = 1
                else:
                    mat[i + m][j] = 1

        f0 = [[1] for _ in range(2 * m)]
        res = MatrixPower.matrix_power(mat, n - 1, f0)
        ans = sum(sum(row) for row in res)
        return ans % 1_000_000_007
py
from typing import List


class MatrixPower:

    @staticmethod
    def matrix_multiply(
        a: List[List[int]], b: List[List[int]], mod: int = 1_000_000_007
    ) -> List[List[int]]:
        """Multiply two matrices a and b under modulo, a @ b."""
        return [
            [sum(x * y % mod for x, y in zip(a_row, b_col)) % mod for b_col in zip(*b)]
            for a_row in a
        ]

    @staticmethod
    def matrix_power(
        base: List[List[int]], n: int, f0: List[List[int]], mod: int = 1_000_000_007
    ) -> List[List[int]]:
        """Raise matrix base to the power of n under modulo, base ^ n @ f0."""
        mul = lambda a, b: [
            [sum(x * y % mod for x, y in zip(a_row, b_col)) % mod for b_col in zip(*b)]
            for a_row in a
        ]
        res = f0
        while n:
            if n & 1:
                res = mul(base, res)
            base = mul(base, base)
            n >>= 1
        return res
力扣第 470 场周赛
力扣第 166 场双周赛