跳转至

3179. K 秒后第 N 个元素的值

题目描述

给你两个整数 n 和 k。

最初，你有一个长度为 n 的整数数组 a，对所有 0 <= i <= n - 1，都有 a[i] = 1 。每过一秒，你会同时更新每个元素为其前面所有元素的和加上该元素本身。例如，一秒后，a[0] 保持不变，a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，以此类推。

返回 k 秒后 a[n - 1] 的值。

由于答案可能非常大，返回其对 109 + 7 取余 后的结果。

 

示例 1：

输入：n = 4, k = 5

输出：56

解释：

时间（秒） 数组状态
0 [1,1,1,1]
1 [1,2,3,4]
2 [1,3,6,10]
3 [1,4,10,20]
4 [1,5,15,35]
5 [1,6,21,56]

示例 2：

输入：n = 5, k = 3

输出：35

解释：

时间（秒） 数组状态
0 [1,1,1,1,1]
1 [1,2,3,4,5]
2 [1,3,6,10,15]
3 [1,4,10,20,35]

 

提示：

  • 1 <= n, k <= 1000

解法

方法一：模拟

思考

每秒每个位置变成其前缀和。闭式是组合数 \(\binom{n+k-1}{n-1}\)，但 \(n,k\le 1000\) 时直接模拟更直观且取模方便。

数组长度固定为 \(n\)，从左更新即可原地做前缀和。

初始化全 \(1\)，重复 \(k\) 次 \(a[i]+=a[i-1]\) 并取模，返回 \(a[n-1]\)。

我们注意到，整数 \(n\) 的范围是 \(1 \leq n \leq 1000\)，因此我们可以直接模拟这个过程。

我们定义一个长度为 \(n\) 的数组 \(a\)，并初始化所有元素为 \(1\)。然后我们模拟 \(k\) 秒的过程，每一秒我们都更新数组 \(a\) 的元素，直到 \(k\) 秒结束。

最后，我们返回 \(a[n - 1]\) 即可。

时间复杂度 \(O(n \times k)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(a\) 的长度。

1
2
3
4
5
6
7
8
class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        a = [1] * n
        mod = 10**9 + 7
        for _ in range(k):
            for i in range(1, n):
                a[i] = (a[i] + a[i - 1]) % mod
        return a[n - 1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int valueAfterKSeconds(int n, int k) {
        final int mod = (int) 1e9 + 7;
        int[] a = new int[n];
        Arrays.fill(a, 1);
        while (k-- > 0) {
            for (int i = 1; i < n; ++i) {
                a[i] = (a[i] + a[i - 1]) % mod;
            }
        }
        return a[n - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        const int mod = 1e9 + 7;
        vector<int> a(n, 1);
        while (k-- > 0) {
            for (int i = 1; i < n; ++i) {
                a[i] = (a[i] + a[i - 1]) % mod;
            }
        }
        return a[n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func valueAfterKSeconds(n int, k int) int {
    const mod int = 1e9 + 7
    a := make([]int, n)
    for i := range a {
        a[i] = 1
    }
    for ; k > 0; k-- {
        for i := 1; i < n; i++ {
            a[i] = (a[i] + a[i-1]) % mod
        }
    }
    return a[n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function valueAfterKSeconds(n: number, k: number): number {
    const a: number[] = Array(n).fill(1);
    const mod: number = 10 ** 9 + 7;
    while (k--) {
        for (let i = 1; i < n; ++i) {
            a[i] = (a[i] + a[i - 1]) % mod;
        }
    }
    return a[n - 1];
}

评论