给你一个 正整数 数组 nums。
Alice 和 Bob 正在玩游戏。在游戏中，Alice 可以从 nums 中选择所有个位数 或 所有两位数，剩余的数字归 Bob 所有。如果 Alice 所选数字之和 严格大于 Bob 的数字之和，则 Alice 获胜。
如果 Alice 能赢得这场游戏，返回 true；否则，返回 false。
示例 1：
输入：nums = [1,2,3,4,10]
输出：false
解释：
Alice 不管选个位数还是两位数都无法赢得比赛。
示例 2：
输入：nums = [1,2,3,4,5,14]
输出：true
解释：
Alice 选择个位数可以赢得比赛，所选数字之和为 15。
示例 3：
输入：nums = [5,5,5,25]
输出：true
解释：
Alice 选择两位数可以赢得比赛，所选数字之和为 25。
提示：
登录1 <= nums.length <= 1001 <= nums[i] <= 99由题意可知，$Alice$ 在一位数之和以及两位数之和中拥有选择较大者的权利，因此，只要一位数之和与两位数之和不相等，那么 $Alice$ 即可获胜。
具体来说，我们可以选择遍历数组，当此时的数字为一位数，即 $num<10$ 时，我们将 $num$ 直接加入结果中；否则，我们将 $-num$ 加入结果中。最终我们返回结果是否为 $0$ 即可。
###C#
public class Solution {
public bool CanAliceWin(int[] nums) {
return nums.Sum(i => i < 10 ? i : -i) != 0;
}
}
###C++
class Solution {
public:
static bool canAliceWin(const std::vector<int>& nums) {
return std::accumulate(nums.begin(), nums.end(), 0, [](int last, int i) {
return last + (i < 10 ? i : -i);
}) != 0;
}
};
###Java
class Solution {
public boolean canAliceWin(int[] nums) {
return Arrays.stream(nums).map(i -> i < 10 ? i : -i).sum() != 0;
}
}
###Python
class Solution:
def canAliceWin(self, nums: List[int]) -> bool:
return sum(i if i < 10 else -i for i in nums) != 0
###Kotlin
class Solution {
fun canAliceWin(nums: IntArray): Boolean {
return nums.sumOf { if (it < 10) it else -it } != 0
}
}
设 $s_1$ 为 $\textit{nums}$ 中的所有个位数之和，$s_2$ 为 $\textit{nums}$ 中的所有两位数之和。注意题目保证只有个位数和两位数。
小红若要获胜，必须满足 $s_1 > s_2$ 或者 $s_2 > s_1$，即
$$
s_1 \ne s_2
$$
代码实现时，可以令 $s = s_1 - s_2$，即累加 $\textit{nums}$ 的所有元素，把其中的两位数变成相反数累加。这样最后只需判断 $s\ne 0$ 即可。
具体请看 视频讲解，欢迎点赞关注~
###py
class Solution:
def canAliceWin(self, nums: List[int]) -> bool:
return sum(x if x < 10 else -x for x in nums) != 0
###java
class Solution {
public boolean canAliceWin(int[] nums) {
int s = 0;
for (int x : nums) {
s += x < 10 ? x : -x;
}
return s != 0;
}
}
###cpp
class Solution {
public:
bool canAliceWin(vector<int>& nums) {
int s = 0;
for (int x : nums) {
s += x < 10 ? x : -x;
}
return s != 0;
}
};
###c
bool canAliceWin(int* nums, int numsSize) {
int s = 0;
for (int i = 0; i < numsSize; i++) {
s += nums[i] < 10 ? nums[i] : -nums[i];
}
return s != 0;
}
###go
func canAliceWin(nums []int) bool {
s := 0
for _, x := range nums {
if x < 10 {
s += x
} else {
s -= x
}
}
return s != 0
}
###js
var canAliceWin = function(nums) {
let s = 0;
for (const x of nums) {
s += x < 10 ? x : -x;
}
return s !== 0;
};
###rust
impl Solution {
pub fn can_alice_win(nums: Vec<i32>) -> bool {
nums.iter().map(|&x| if x < 10 { x } else { -x }).sum::<i32>() != 0
}
}
欢迎关注 B站@灵茶山艾府
按题意模拟即可。复杂度 $\mathcal{O}(n)$。
###cpp
class Solution {
public:
bool canAliceWin(vector<int>& nums) {
int sm = 0, a = 0, b = 0;
for (int x : nums) {
sm += x;
if (x < 10) a += x;
else b += x;
}
return a > sm - a || b > sm - b;
}
};
我们定义 $f[i][j]$ 表示下标 $[0,..i]$ 的单调数组对的数目，且 $arr1[i] = j$。初始时 $[i][j] = 0$，答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。
当 $i = 0$ 时，有 $[0][j] = 1$，其中 $0 \leq j \leq \textit{nums}[0]$。
当 $i > 0$ 时，我们可以根据 $f[i-1][j']$ 计算 $f[i][j]$。由于 $\textit{arr1}$ 是单调非递减的，因此 $j' \leq j$。又由于 $\textit{arr2}$ 是单调非递增的，因此 $\textit{nums}[i] - j \leq \textit{nums}[i - 1] - j'$。即 $j' \leq \min(j, j + \textit{nums}[i - 1] - \textit{nums}[i])$。
答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。
###python
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
mod = 10**9 + 7
n, m = len(nums), max(nums)
f = [[0] * (m + 1) for _ in range(n)]
for j in range(nums[0] + 1):
f[0][j] = 1
for i in range(1, n):
s = list(accumulate(f[i - 1]))
for j in range(nums[i] + 1):
k = min(j, j + nums[i - 1] - nums[i])
if k >= 0:
f[i][j] = s[k] % mod
return sum(f[-1][: nums[-1] + 1]) % mod
###java
class Solution {
public int countOfPairs(int[] nums) {
final int mod = (int) 1e9 + 7;
int n = nums.length;
int m = Arrays.stream(nums).max().getAsInt();
int[][] f = new int[n][m + 1];
for (int j = 0; j <= nums[0]; ++j) {
f[0][j] = 1;
}
int[] g = new int[m + 1];
for (int i = 1; i < n; ++i) {
g[0] = f[i - 1][0];
for (int j = 1; j <= m; ++j) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (int j = 0; j <= nums[i]; ++j) {
int k = Math.min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
int ans = 0;
for (int j = 0; j <= nums[n - 1]; ++j) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
}
###cpp
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int mod = 1e9 + 7;
int n = nums.size();
int m = *max_element(nums.begin(), nums.end());
vector<vector<int>> f(n, vector<int>(m + 1));
for (int j = 0; j <= nums[0]; ++j) {
f[0][j] = 1;
}
vector<int> g(m + 1);
for (int i = 1; i < n; ++i) {
g[0] = f[i - 1][0];
for (int j = 1; j <= m; ++j) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (int j = 0; j <= nums[i]; ++j) {
int k = min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
int ans = 0;
for (int j = 0; j <= nums[n - 1]; ++j) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
};
###go
func countOfPairs(nums []int) (ans int) {
const mod int = 1e9 + 7
n := len(nums)
m := slices.Max(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 0; j <= nums[0]; j++ {
f[0][j] = 1
}
g := make([]int, m+1)
for i := 1; i < n; i++ {
g[0] = f[i-1][0]
for j := 1; j <= m; j++ {
g[j] = (g[j-1] + f[i-1][j]) % mod
}
for j := 0; j <= nums[i]; j++ {
k := min(j, j+nums[i-1]-nums[i])
if k >= 0 {
f[i][j] = g[k]
}
}
}
for j := 0; j <= nums[n-1]; j++ {
ans = (ans + f[n-1][j]) % mod
}
return
}
###ts
function countOfPairs(nums: number[]): number {
const mod = 1e9 + 7;
const n = nums.length;
const m = Math.max(...nums);
const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
for (let j = 0; j <= nums[0]; j++) {
f[0][j] = 1;
}
const g: number[] = Array(m + 1).fill(0);
for (let i = 1; i < n; i++) {
g[0] = f[i - 1][0];
for (let j = 1; j <= m; j++) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (let j = 0; j <= nums[i]; j++) {
const k = Math.min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
let ans = 0;
for (let j = 0; j <= nums[n - 1]; j++) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 表示数组 $\textit{nums}$ 的长度，而 $m$ 表示数组 $\textit{nums}$ 中的最大值。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
n 。arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 20001 <= nums[i] <= 1000本题解没讲太多细节，需要读者有 DP 基础。
记 $i$ 为数组下标（从 0 开始），$j = arr1[i]$, $k = arr1[i-1]$
根据题意
arr1 非递减，所以限制 $k \leq j$arr2 非递增，所以限制 $nums[i-1] - k \geq nums[i] - j$所以 $0 \leq k \leq min(j, nums[i-1] - nums[i] + j)$
记 $ceil = min(j,\ nums[i-1] - nums[i] + j)$
可得状态转移方程 $f(i, j) = \sum\limits_{k=0}^{ceil} f(i-1, k)$
初始状态为
$$
f(0, j) =
\begin{cases}
1 & if\ j \in [0, nums[0]]\
0 & 其他
\end{cases}
$$
在多维的实现中，计算每行的每个元素时都要取上一行的某段前缀和。
###C++
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int MOD = 1e9 + 7;
int m = nums.size();
int n = *max_element(nums.begin(), nums.end());
vector<int> f(n + 1);
// 初始状态
for (int v = 0; v <= nums[0]; ++v)
f[v] = 1;
vector<int> preSums;
// 多执行一轮
for (int i = 1; i <= m; ++i) {
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear();
int preSum = 0;
for(int v : f){
preSum += v;
preSum %= MOD;
preSums.push_back(preSum);
}
// 最后一轮提前返回结尾处的方案数总和
if (i == m) return preSums.back();
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for (int j = 0; j <= nums[i]; ++j) {
int ceil = min(j, nums[i-1] - nums[i] + j);
if (ceil >= 0)
f[j] = preSums[ceil];
else // ceil < 0 说明不存在
f[j] = 0;
}
for (int j = nums[i] + 1; j < f.size(); ++j) {
f[j] = 0;
}
}
// 不会执行
return 0;
}
};
###Python3
class Solution:
def countOfPairs(self, nums):
MOD = 1_000_000_007
m = len(nums)
n = max(nums)
f = [0] * (n + 1)
# 初始状态
for v in range(nums[0] + 1):
f[v] = 1
preSums = []
# 多执行一轮
for i in range(1, m + 1):
# 前缀和，此处不重复开辟空间以提升性能。
preSums.clear()
preSum = 0
for v in f:
preSum += v
preSum %= MOD
preSums.append(preSum)
# 最后一轮提前返回结尾处的方案数总和
if i == m:
return preSums[-1]
# 优化空间，二维变一维，没用到的格子都要使元素归 0
for j in range(nums[i] + 1):
ceil = min(j, nums[i-1] - nums[i] + j)
if ceil >= 0:
f[j] = preSums[ceil]
else: # ceil < 0 说明不存在
f[j] = 0
for j in range(nums[i] + 1, len(f)):
f[j] = 0
# 不会执行
return 0
###Java
class Solution {
public int countOfPairs(int[] nums) {
final int MOD = (int)(1e9 + 7);
int m = nums.length;
int n = Arrays.stream(nums).max().getAsInt();
int[] f = new int[n + 1];
// 初始状态
for (int v = 0; v <= nums[0]; ++v) f[v] = 1;
List<Integer> preSums = new ArrayList<>();
// 多执行一轮
for (int i = 1; i <= m; ++i) {
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear();
int preSum = 0;
for(int v : f){
preSum += v;
preSum %= MOD;
preSums.add(preSum);
}
// 最后一轮提前返回结尾处的方案数总和
if (i == m) return preSums.get(preSums.size() - 1);
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for (int j = 0; j <= nums[i]; ++j) {
int ceil = Math.min(j, nums[i-1] - nums[i] + j);
if (ceil >= 0)
f[j] = preSums.get(ceil);
else // ceil < 0 说明不存在
f[j] = 0;
}
for (int j = nums[i] + 1; j < f.length; ++j) {
f[j] = 0;
}
}
// 不会执行
return 0;
}
}
###Kotlin
class Solution {
fun countOfPairs(nums: IntArray): Int {
val MOD = 1_000_000_007
val m = nums.size
val n = nums.max()
val f = IntArray(n+1)
// 初始状态
for(v in 0..nums[0]) f[v] = 1
val preSums = mutableListOf<Int>()
// 多执行一轮
for(i in 1..m){
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear()
for(v in f){
val lastPreSum = preSums.lastOrNull() ?: 0
preSums += (lastPreSum + v) % MOD
}
// 最后一轮提前返回结尾处的方案数总和
if(i == m) return preSums.last()
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for(j in 0..nums[i]){
val ceil = min(j, nums[i-1] - nums[i] + j)
if(ceil >= 0)
f[j] = preSums[ceil]
else // ceil < 0 说明不存在
f[j] = 0
}
for(j in (nums[i] + 1)..f.lastIndex){
f[j] = 0
}
}
// 不会执行
return 0
}
}
记 $m$ 为 nums 长度，$n$ 为 nums 元素最大值。
f 的长度限制为 nums 最后一个元素的大小 + 1。我就偷懒不写这么详细了。
以下皆为个人所著，兼顾了职场面试和本硕阶段的学术考试。
点赞关注不迷路。祝君早日上岸，飞黄腾达！
看示例 1，$\textit{nums}=[2,3,2]$。
单调数组对有 $4$ 个：
从右往左思考。假设 $\textit{arr}_1[2]=2$，那么 $\textit{arr}_2[2]=\textit{nums}[2] - \textit{arr}_1[2]=2-2= 0$。考虑枚举 $\textit{arr}_1[1]$ 是多少：
累加这些个数，我们就得到了在 $\textit{arr}_1[2]=2$ 的情况下，下标 $0$ 到 $2$ 中的单调数组对的个数。（有 $3$ 个）
此外，在 $\textit{arr}_1[2]=1$ 的情况下，下标 $0$ 到 $2$ 中的单调数组对的个数是 $1$；在 $\textit{arr}_1[2]=0$ 的情况下，下标 $0$ 到 $2$ 中的单调数组对的个数是 $0$。所以 $\textit{nums}=[2,3,2]$ 一共有 $4$ 个单调数组对。
上面的讨论说明：
考虑枚举 $\textit{arr}_1[i-1] = k$，那么必须满足 $\textit{arr}_1[i-1]\le \textit{arr}_1[i]$ 且 $\textit{arr}_2[i-1]\ge \textit{arr}_2[i]$，即 $k\le j$ 且 $\textit{nums}[i-1]-k\ge \textit{nums}[i] - j$。
整理得
$$
k \le \min(j,\textit{nums}[i-1] - \textit{nums}[i] + j) = j + \min(\textit{nums}[i-1] - \textit{nums}[i], 0)
$$
⚠注意：无需判断 $k\le \textit{nums}[i-1]$，因为 $\textit{nums}[i-1] - \textit{nums}[i] + j = \textit{nums}[i-1] - (\textit{nums}[i] - j)\le \textit{nums}[i-1]$，由数学归纳法可以证明 $k\le \textit{nums}[i-1]$。
记 $\textit{maxK} = j + \min(\textit{nums}[i-1] - \textit{nums}[i], 0)$，那么有
$$
f[i][j] =
\begin{cases}
0, & \textit{maxK} < 0 \
\sum\limits_{k=0}^{\textit{maxK}} f[i-1][k], & \textit{maxK} \ge 0 \
\end{cases}
$$
其中和式可以用 前缀和 优化。
设 $f[i-1]$ 的前缀和 $s[j] = \sum\limits_{k=0}^{j} f[i-1][k]$，状态转移方程化简为
$$
f[i][j] =
\begin{cases}
0, & \textit{maxK} < 0 \
s[\textit{maxK}], & \textit{maxK} \ge 0 \
\end{cases}
$$
初始值：$f[0][j] = 1$，其中 $j=0,1,2,\ldots,\textit{nums}[0]$。
答案：枚举 $\textit{arr}1[n-1] = 0,1,2,\ldots,\textit{nums}[n-1]$，累加得 $\sum\limits{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。
具体请看 视频讲解，欢迎点赞关注！
###py
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
n = len(nums)
m = max(nums)
f = [[0] * (m + 1) for _ in range(n)]
for j in range(nums[0] + 1):
f[0][j] = 1
for i in range(1, n):
s = list(accumulate(f[i - 1])) # f[i-1] 的前缀和
for j in range(nums[i] + 1):
max_k = j + min(nums[i - 1] - nums[i], 0)
f[i][j] = s[max_k] % MOD if max_k >= 0 else 0
return sum(f[-1][:nums[-1] + 1]) % MOD
###java
class Solution {
public int countOfPairs(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = Arrays.stream(nums).max().getAsInt();
long[][] f = new long[n][m + 1];
long[] s = new long[m + 1];
Arrays.fill(f[0], 0, nums[0] + 1, 1);
for (int i = 1; i < n; i++) {
s[0] = f[i - 1][0];
for (int k = 1; k <= m; k++) {
s[k] = (s[k - 1] + f[i - 1][k]) % MOD; // f[i-1] 的前缀和
}
for (int j = 0; j <= nums[i]; j++) {
int maxK = j + Math.min(nums[i - 1] - nums[i], 0);
f[i][j] = maxK >= 0 ? s[maxK] % MOD : 0;
}
}
return (int) (Arrays.stream(f[n - 1], 0, nums[n - 1] + 1).sum() % MOD);
}
}
###cpp
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size();
int m = ranges::max(nums);
vector f(n, vector<long long>(m + 1));
vector<long long> s(m + 1);
fill(f[0].begin(), f[0].begin() + nums[0] + 1, 1);
for (int i = 1; i < n; i++) {
partial_sum(f[i - 1].begin(), f[i - 1].end(), s.begin()); // f[i-1] 的前缀和
for (int j = 0; j <= nums[i]; j++) {
int max_k = j + min(nums[i - 1] - nums[i], 0);
f[i][j] = max_k >= 0 ? s[max_k] % MOD : 0;
}
}
return reduce(f[n - 1].begin(), f[n - 1].begin() + nums[n - 1] + 1, 0LL) % MOD;
}
};
###go
func countOfPairs(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := slices.Max(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m+1)
}
s := make([]int, m+1)
for j := 0; j <= nums[0]; j++ {
f[0][j] = 1
}
for i := 1; i < n; i++ {
s[0] = f[i-1][0]
for k := 1; k <= m; k++ {
s[k] = s[k-1] + f[i-1][k] // f[i-1] 的前缀和
}
for j := 0; j <= nums[i]; j++ {
maxK := j + min(nums[i-1]-nums[i], 0)
if maxK >= 0 {
f[i][j] = s[maxK] % mod
}
}
}
for _, v := range f[n-1][:nums[n-1]+1] {
ans += v
}
return ans % mod
}
进一步分析，$\textit{maxK} \ge 0$ 即
$$
j + \min(\textit{nums}[i-1] - \textit{nums}[i], 0) \ge 0
$$
变形得
$$
j\ge \max(\textit{nums}[i] - \textit{nums}[i-1], 0)
$$
记 $j_0 = \max(\textit{nums}[i] - \textit{nums}[i-1], 0)$，那么我们只需要计算在 $j$ 区间 $[j_0, \textit{nums}[i]]$ 中的 $f[i][j]$，其余 $f[i][j]$ 均为 $0$。
设 $s[j] = \sum\limits_{k=0}^{j} f[i-1][k]$，状态转移方程化简为
$$
f[i][j] =
\begin{cases}
0, & j < j_0 \
s[j-j_0], & j\ge j_0 \
\end{cases}
$$
代码实现时，$f[i][j]$ 可以用一维数组滚动计算：先把前缀和直接保存在 $f$ 数组中，然后倒序更新 $f[j] = f[j-j_0]$（倒序更新的理由同 0-1 背包）。
此外，由于在计算答案时只考虑 $j\le \textit{nums}[n-1]$ 的状态，所以 $f$ 数组只需要开 $\textit{nums}[n-1]+1$ 的大小。
###py
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
for j in range(1, m + 1):
f[j] += f[j - 1] # 计算前缀和
j0 = max(cur - pre, 0)
for j in range(min(cur, m), j0 - 1, -1):
f[j] = f[j - j0] % MOD
for j in range(min(j0, m + 1)):
f[j] = 0
return sum(f) % MOD
###java
class Solution {
public int countOfPairs(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = nums[n - 1];
int[] f = new int[m + 1];
Arrays.fill(f, 0, Math.min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
int j0 = Math.max(nums[i] - nums[i - 1], 0);
for (int j = Math.min(nums[i], m); j >= j0; j--) {
f[j] = f[j - j0];
}
Arrays.fill(f, 0, Math.min(j0, m + 1), 0);
}
long ans = 0;
for (int v : f) {
ans += v;
}
return (int) (ans % MOD);
}
}
###cpp
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size(), m = nums.back();
vector<int> f(m + 1);
fill(f.begin(), f.begin() + min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
int j0 = max(nums[i] - nums[i - 1], 0);
for (int j = min(nums[i], m); j >= j0; j--) {
f[j] = f[j - j0];
}
fill(f.begin(), f.begin() + min(j0, m + 1), 0);
}
return reduce(f.begin(), f.end(), 0LL) % MOD;
}
};
###go
func countOfPairs(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := nums[n-1]
f := make([]int, m+1)
for j := range f[:min(nums[0], m)+1] {
f[j] = 1
}
for i := 1; i < n; i++ {
for j := 1; j <= m; j++ {
f[j] += f[j-1] // 计算前缀和
}
j0 := max(nums[i]-nums[i-1], 0)
for j := min(nums[i], m); j >= j0; j-- {
f[j] = f[j-j0] % mod
}
clear(f[:min(j0, m+1)])
}
for _, v := range f {
ans += v
}
return ans % mod
}
如果 $j_0 > \min(\textit{nums}[i],m)$，那么后面计算出的 $f[j]$ 均为 $0$，我们可以直接返回 $0$。
此外，前缀和只需要计算到 $j=\min(\textit{nums}[i],m) - j_0$ 为止。
###py
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
f = [0] * (m + 1)
for j in range(min(nums[0], m) + 1):
f[j] = 1
for pre, cur in pairwise(nums):
j0 = max(cur - pre, 0)
m2 = min(cur, m)
if j0 > m2:
return 0
for j in range(1, m2 - j0 + 1):
f[j] = (f[j] + f[j - 1]) % MOD # 计算前缀和
f[j0: m2 + 1] = f[:m2 - j0 + 1]
f[:j0] = [0] * j0
return sum(f) % MOD
###java
class Solution {
public int countOfPairs(int[] nums) {
final int MOD = 1_000_000_007;
int n = nums.length;
int m = nums[n - 1];
int[] f = new int[m + 1];
Arrays.fill(f, 0, Math.min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
int j0 = Math.max(nums[i] - nums[i - 1], 0);
int m2 = Math.min(nums[i], m);
if (j0 > m2) {
return 0;
}
for (int j = 1; j <= m2 - j0; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
System.arraycopy(f, 0, f, j0, m2 - j0 + 1);
Arrays.fill(f, 0, j0, 0);
}
long ans = 0;
for (int v : f) {
ans += v;
}
return (int) (ans % MOD);
}
}
###cpp
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int MOD = 1'000'000'007;
int n = nums.size(), m = nums[n - 1];
vector<int> f(m + 1);
fill(f.begin(), f.begin() + min(nums[0], m) + 1, 1);
for (int i = 1; i < n; i++) {
int j0 = max(nums[i] - nums[i - 1], 0);
int m2 = min(nums[i], m);
if (j0 > m2) {
return 0;
}
for (int j = 1; j <= m2 - j0; j++) {
f[j] = (f[j] + f[j - 1]) % MOD; // 计算前缀和
}
copy(f.begin(), f.begin() + m2 - j0 + 1, f.begin() + j0);
fill(f.begin(), f.begin() + j0, 0);
}
return reduce(f.begin(), f.end(), 0LL) % MOD;
}
};
###go
func countOfPairs(nums []int) (ans int) {
const mod = 1_000_000_007
n := len(nums)
m := nums[n-1]
f := make([]int, m+1)
for j := range f[:min(nums[0], m)+1] {
f[j] = 1
}
for i := 1; i < n; i++ {
j0 := max(nums[i]-nums[i-1], 0)
m2 := min(nums[i], m)
if j0 > m2 {
return 0
}
for j := 1; j <= m2-j0; j++ {
f[j] = (f[j] + f[j-1]) % mod // 计算前缀和
}
copy(f[j0:m2+1], f)
clear(f[:j0])
}
for _, v := range f {
ans += v
}
return ans % mod
}
首先来看一个特殊的情况：所有 $\textit{nums}[i]$ 都相同。
例如示例 2，$\textit{nums}=[5,5,5,5]$，在所有元素都相同的情况下，只要 $\textit{arr}_1$ 是单调非递减的，那么 $\textit{arr}_2$ 就一定是单调非递增的。
问题变成：
考虑一条从左下角走到右上角的路径，每次只能向右或向上走。向右走时，把之前向上走的次数（或者说当前高度）作为数组元素值。如上图，对应的数组为 $[2,3,3,4]$。
由于路径与单调非递减数组是一一对应的，所以问题变成路径个数是多少。
要向上走 $5$ 步，向右走 $4$ 步，一共走 $5+4=9$ 步。选择其中 $4$ 步向右走，于是问题变成从 $9$ 步中选 $4$ 步的方案数，即
$$
C(9,4) = 126
$$
以 $m=\textit{nums}[n-1]$ 为基准，如果所有元素都等于 $m$，那么问题等价于从 $m+n$ 步中选 $n$ 步的方案数，即
$$
C(m+n,n)
$$
回到原问题，来看看 $\textit{nums}[i]$ 会如何影响路径个数。
为方便描述，下文把 $\textit{arr}_1$ 记作 $a$。
如果 $a[i-1] = x,\ a[i] = y$，那么必须满足 $x\le y$ 且 $\textit{nums}[i-1]-x\ge \textit{nums}[i]-y$，即
$$
y \ge \max(x, x+ \textit{nums}[i]-\textit{nums}[i-1])
$$
分类讨论：
剩下的 $m+n-d$ 步可以随意安排向右走还是向上走。于是问题变成从 $m+n-d$ 步中选 $n$ 步向右走的方案数，即
$$
C(m+n-d,n)
$$
一般地，设 $d_i=\max(\textit{nums}[i]-\textit{nums}[i-1],0)$，计算
$$
m = \textit{nums}[n-1] - d_1 - d_2 - \cdots - d_{n-1}
$$
那么答案为
$$
\begin{cases}
0, & m < 0 \
C(m+n,n), & m \ge 0 \
\end{cases}
$$
由于 $C(m+n,n) = C(m+n,m)$，答案也可以是 $C(m+n,m)$。
问：为什么要以 $\textit{nums}[n-1]$ 为基准？
答：从路径的角度上看，$\textit{nums}[n-1]$ 与 $n$ 一起，决定了我们总共要走多少步。至于 $\textit{nums}$ 中的其他元素，影响的是 $a[i]$ 与 $a[i-1]$ 的差值，相当于在某些位置强行向上走若干步，这不会改变「总共要走 $\textit{nums}[n-1]+n$ 步」的事实。此外，如果以 $\textit{arr}_2$，也就是「单调非递增的数组个数」计算答案，也可以以 $\textit{nums}[0]$ 为基准，计算方法是类似的，感兴趣的读者可以自行推导，从而加深对方法二的理解。
###py
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
MOD = 1_000_000_007
m = nums[-1]
for x, y in pairwise(nums):
m -= max(y - x, 0)
return comb(m + len(nums), m) % MOD if m >= 0 else 0
###py
MOD = 1_000_000_007
MX = 3001 # MAX_N + MAX_M = 2000 + 1000 = 3000
fac = [0] * MX # f[i] = i!
fac[0] = 1
for i in range(1, MX):
fac[i] = fac[i - 1] * i % MOD
inv_f = [0] * MX # inv_f[i] = i!^-1
inv_f[-1] = pow(fac[-1], -1, MOD)
for i in range(MX - 1, 0, -1):
inv_f[i - 1] = inv_f[i] * i % MOD
def comb(n: int, m: int) -> int:
return fac[n] * inv_f[m] * inv_f[n - m] % MOD
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
m = nums[-1]
for x, y in pairwise(nums):
if y > x: # 更快的写法：手写 max
m -= y - x
if m < 0: # 更快的写法：提前返回 0
return 0
return comb(m + len(nums), m) if m >= 0 else 0
###java
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 3001; // MAX_N + MAX_M = 2000 + 1000 = 3000
private static final long[] F = new long[MX]; // f[i] = i!
private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1
static {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i > 0; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
}
public int countOfPairs(int[] nums) {
int n = nums.length;
int m = nums[n - 1];
for (int i = 1; i < n; i++) {
m -= Math.max(nums[i] - nums[i - 1], 0);
if (m < 0) {
return 0;
}
}
return (int) comb(m + n, n);
}
private long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
private static long pow(long x, int n) {
long res = 1;
for (; n > 0; n /= 2) {
if (n % 2 > 0) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
}
###cpp
const int MOD = 1'000'000'007;
const int MX = 3001; // MAX_N + MAX_M = 2000 + 1000 = 3000
long long F[MX]; // F[i] = i!
long long INV_F[MX]; // INV_F[i] = i!^-1
long long pow(long long x, int n) {
long long res = 1;
for (; n; n /= 2) {
if (n % 2) {
res = res * x % MOD;
}
x = x * x % MOD;
}
return res;
}
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);
for (int i = MX - 1; i; i--) {
INV_F[i - 1] = INV_F[i] * i % MOD;
}
return 0;
}();
long long comb(int n, int m) {
return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}
class Solution {
public:
int countOfPairs(vector<int>& nums) {
int n = nums.size(), m = nums.back();
for (int i = 1; i < n; i++) {
m -= max(nums[i] - nums[i - 1], 0);
if (m < 0) {
return 0;
}
}
return comb(m + n, n);
}
};
###go
const mod = 1_000_000_007
const mx = 3001 // MAX_N + MAX_M = 2000 + 1000 = 3000
var f [mx]int // f[i] = i!
var invF [mx]int // invF[i] = i!^-1
func init() {
f[0] = 1
for i := 1; i < mx; i++ {
f[i] = f[i-1] * i % mod
}
invF[mx-1] = pow(f[mx-1], mod-2)
for i := mx - 1; i > 0; i-- {
invF[i-1] = invF[i] * i % mod
}
}
func comb(n, m int) int {
return f[n] * invF[m] % mod * invF[n-m] % mod
}
func countOfPairs(nums []int) int {
n := len(nums)
m := nums[n-1]
for i := 1; i < n; i++ {
m -= max(nums[i]-nums[i-1], 0)
if m < 0 {
return 0
}
}
return comb(m+n, n)
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
更多相似题目，见下面动态规划题单中的「§11.1 前缀和优化 DP」。
欢迎关注 B站@灵茶山艾府
我们定义 $f[i][j]$ 表示下标 $[0,..i]$ 的单调数组对的数目，且 $arr1[i] = j$。初始时 $[i][j] = 0$，答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。
当 $i = 0$ 时，有 $[0][j] = 1$，其中 $0 \leq j \leq \textit{nums}[0]$。
当 $i > 0$ 时，我们可以根据 $f[i-1][j']$ 计算 $f[i][j]$。由于 $\textit{arr1}$ 是单调非递减的，因此 $j' \leq j$。又由于 $\textit{arr2}$ 是单调非递增的，因此 $\textit{nums}[i] - j \leq \textit{nums}[i - 1] - j'$。即 $j' \leq \min(j, j + \textit{nums}[i - 1] - \textit{nums}[i])$。
答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。
###python
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
mod = 10**9 + 7
n, m = len(nums), max(nums)
f = [[0] * (m + 1) for _ in range(n)]
for j in range(nums[0] + 1):
f[0][j] = 1
for i in range(1, n):
s = list(accumulate(f[i - 1]))
for j in range(nums[i] + 1):
k = min(j, j + nums[i - 1] - nums[i])
if k >= 0:
f[i][j] = s[k] % mod
return sum(f[-1][: nums[-1] + 1]) % mod
###java
class Solution {
public int countOfPairs(int[] nums) {
final int mod = (int) 1e9 + 7;
int n = nums.length;
int m = Arrays.stream(nums).max().getAsInt();
int[][] f = new int[n][m + 1];
for (int j = 0; j <= nums[0]; ++j) {
f[0][j] = 1;
}
int[] g = new int[m + 1];
for (int i = 1; i < n; ++i) {
g[0] = f[i - 1][0];
for (int j = 1; j <= m; ++j) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (int j = 0; j <= nums[i]; ++j) {
int k = Math.min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
int ans = 0;
for (int j = 0; j <= nums[n - 1]; ++j) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
}
###cpp
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int mod = 1e9 + 7;
int n = nums.size();
int m = *max_element(nums.begin(), nums.end());
vector<vector<int>> f(n, vector<int>(m + 1));
for (int j = 0; j <= nums[0]; ++j) {
f[0][j] = 1;
}
vector<int> g(m + 1);
for (int i = 1; i < n; ++i) {
g[0] = f[i - 1][0];
for (int j = 1; j <= m; ++j) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (int j = 0; j <= nums[i]; ++j) {
int k = min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
int ans = 0;
for (int j = 0; j <= nums[n - 1]; ++j) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
};
###go
func countOfPairs(nums []int) (ans int) {
const mod int = 1e9 + 7
n := len(nums)
m := slices.Max(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 0; j <= nums[0]; j++ {
f[0][j] = 1
}
g := make([]int, m+1)
for i := 1; i < n; i++ {
g[0] = f[i-1][0]
for j := 1; j <= m; j++ {
g[j] = (g[j-1] + f[i-1][j]) % mod
}
for j := 0; j <= nums[i]; j++ {
k := min(j, j+nums[i-1]-nums[i])
if k >= 0 {
f[i][j] = g[k]
}
}
}
for j := 0; j <= nums[n-1]; j++ {
ans = (ans + f[n-1][j]) % mod
}
return
}
###ts
function countOfPairs(nums: number[]): number {
const mod = 1e9 + 7;
const n = nums.length;
const m = Math.max(...nums);
const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
for (let j = 0; j <= nums[0]; j++) {
f[0][j] = 1;
}
const g: number[] = Array(m + 1).fill(0);
for (let i = 1; i < n; i++) {
g[0] = f[i - 1][0];
for (let j = 1; j <= m; j++) {
g[j] = (g[j - 1] + f[i - 1][j]) % mod;
}
for (let j = 0; j <= nums[i]; j++) {
const k = Math.min(j, j + nums[i - 1] - nums[i]);
if (k >= 0) {
f[i][j] = g[k];
}
}
}
let ans = 0;
for (let j = 0; j <= nums[n - 1]; j++) {
ans = (ans + f[n - 1][j]) % mod;
}
return ans;
}
时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 表示数组 $\textit{nums}$ 的长度，而 $m$ 表示数组 $\textit{nums}$ 中的最大值。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
n 。arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 20001 <= nums[i] <= 50思路与算法
我们使用动态规划来解决本题目，定义 $\textit{dp}[i][j]$ 表示当 $\textit{arr}_1[i] = j$ 时，前 $i + 1$ 个元素组成的单调数组的数目。
因为 $\textit{arr}_1[0]$ 可以为 $0$ 到 $\textit{nums}[0]$ 之间的任意数，初始化 $\textit{dp}[0][j] = 1$，其中 $j$ 小于等于 $\textit{nums}[0]$，其它初始化为零。
我们遍历数据，并且枚举 $\textit{arr}1$ 中之前和现在的值，按照题目要求的检查单调性，可得到转移方程 $\textit{dp}[i][v_2] = \sum\limits{v_1}\textit{dp}[i - 1][v_1]$。
其中满足 $v_1 \le v_2$ 和 $\textit{nums}[i - 1] - v_1 \ge \textit{nums}[i] - v_2 \ge 0$。
最后，我们返回 $\textit{dp}[n - 1]$ 的和即为结果。
代码
###C++
class Solution {
public:
int countOfPairs(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(51, 0));
int mod = 1e9 + 7;
for (int v = 0; v <= nums[0]; ++v) {
dp[0][v] = 1;
}
for (int i = 1; i < n; ++i) {
for (int v2 = 0; v2 <= nums[i]; ++v2) {
for (int v1 = 0; v1 <= v2; ++v1) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod;
}
}
}
}
int res = 0;
for (int v : dp[n - 1]) {
res = (res + v) % mod;
}
return res;
}
};
###Java
class Solution {
public int countOfPairs(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][51];
int mod = 1000000007;
for (int v = 0; v <= nums[0]; v++) {
dp[0][v] = 1;
}
for (int i = 1; i < n; i++) {
for (int v2 = 0; v2 <= nums[i]; v2++) {
for (int v1 = 0; v1 <= v2; v1++) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod;
}
}
}
}
int res = 0;
for (int v : dp[n - 1]) {
res = (res + v) % mod;
}
return res;
}
}
###Python
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 51 for i in range(n)]
mod = 10 ** 9 + 7
for v in range(nums[0] + 1):
dp[0][v] = 1
for i in range(1, n):
for v2 in range(nums[i] + 1):
for v1 in range(v2 + 1):
if nums[i - 1] - v1 >= nums[i] - v2:
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod
return sum(dp[n - 1]) % mod
###JavaScript
var countOfPairs = function(nums) {
const n = nums.length;
const dp = Array(n).fill(0).map(() => Array(51).fill(0));
const mod = 10 ** 9 + 7;
for (let v = 0; v <= nums[0]; v++) {
dp[0][v] = 1;
}
for (let i = 1; i < n; i++) {
for (let v2 = 0; v2 <= nums[i]; v2++) {
for (let v1 = 0; v1 <= v2; v1++) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod;
}
}
}
}
return dp[n - 1].reduce((sum, v) => (sum + v) % mod, 0);
};
###TypeScript
function countOfPairs(nums: number[]): number {
const n = nums.length;
const dp = Array(n).fill(0).map(() => Array(51).fill(0));
const mod = 10 ** 9 + 7;
for (let v = 0; v <= nums[0]; v++) {
dp[0][v] = 1;
}
for (let i = 1; i < n; i++) {
for (let v2 = 0; v2 <= nums[i]; v2++) {
for (let v1 = 0; v1 <= v2; v1++) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod;
}
}
}
}
return dp[n - 1].reduce((sum, v) => (sum + v) % mod, 0);
};
###Go
func countOfPairs(nums []int) int {
n := len(nums)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, 51)
}
mod := 1000000007
for v := 0; v <= nums[0]; v++ {
dp[0][v] = 1
}
for i := 1; i < n; i++ {
for v2 := 0; v2 <= nums[i]; v2++ {
for v1 := 0; v1 <= v2; v1++ {
if nums[i-1]-v1 >= nums[i]-v2 {
dp[i][v2] = (dp[i][v2] + dp[i-1][v1]) % mod
}
}
}
}
res := 0
for _, v := range dp[n-1] {
res = (res + v) % mod
}
return res
}
###C#
public class Solution {
public int CountOfPairs(int[] nums) {
int n = nums.Length;
int[,] dp = new int[n, 51];
int mod = 1000000007;
for (int v = 0; v <= nums[0]; v++) {
dp[0, v] = 1;
}
for (int i = 1; i < n; i++) {
for (int v2 = 0; v2 <= nums[i]; v2++) {
for (int v1 = 0; v1 <= v2; v1++) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i, v2] = (dp[i, v2] + dp[i - 1, v1]) % mod;
}
}
}
}
int res = 0;
for (int v = 0; v < 51; v++) {
res = (res + dp[n - 1, v]) % mod;
}
return res;
}
}
###C
int countOfPairs(int* nums, int numsSize) {
int n = numsSize, mod = 1000000007;
int **dp = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = (int *)malloc(51 * sizeof(int));
for (int j = 0; j < 51; j++) {
dp[i][j] = 0;
}
}
for (int v = 0; v <= nums[0]; v++) {
dp[0][v] = 1;
}
for (int i = 1; i < n; i++) {
for (int v2 = 0; v2 <= nums[i]; v2++) {
for (int v1 = 0; v1 <= v2; v1++) {
if (nums[i - 1] - v1 >= nums[i] - v2) {
dp[i][v2] = (dp[i][v2] + dp[i - 1][v1]) % mod;
}
}
}
}
int res = 0;
for (int v = 0; v < 51; v++) {
res = (res + dp[n - 1][v]) % mod;
}
for (int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
###Rust
impl Solution {
pub fn count_of_pairs(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut dp = vec![vec![0; 51]; n];
let modulo = 1000000007;
for v in 0..=nums[0] {
dp[0][v as usize] = 1;
}
for i in 1..n {
for v2 in 0..=nums[i] {
for v1 in 0..=v2 {
if nums[i - 1] - v1 >= nums[i] - v2 {
dp[i][v2 as usize] = (dp[i][v2 as usize] + dp[i - 1][v1 as usize]) % modulo;
}
}
}
}
dp[n - 1].iter().fold(0, |res, &v| (res + v) % modulo)
}
}
复杂度分析
时间复杂度：$O(nm^2)$，其中 $n$ 是数组的长度，$m$ 是数组的最大值。
空间复杂度：$O(nm)$，其中 $n$ 是数组的长度，$m$ 是数组的最大值，可以优化到一维空间 $O(m)$。
思路与算法
在动态规划的转移方程中，我们观察 $\textit{dp}[i][j]$ 的公式，可以发现它是 $\textit{dp}[i - 1]$ 的子数组的和。其中 $\textit{dp}[i][j]$ 和 $\textit{dp}[i][j - 1]$，类似于前缀和数组中相邻的两项，并且由 $\textit{nums}[i - 1] - v_1 \ge \textit{nums}[i] - v_2 \ge 0$ 的限制条件，我们可以推导出 $v_2 \ge \textit{nums}[i] - \textit{nums}[i - 1] + v_1$。
再结合 $v_2 \ge v_1$，我们可以得到 $v_2 \ge v_1 + d$，其中 $d = \max(0, \textit{nums}[i] - \textit{nums}[i - 1])$。
通过上面的观察和推导，我们可以得到 $\textit{dp}[i][j]$ 和 $\textit{dp}[i][j - 1]$ 的关系：$\textit{dp}[i][j] = \textit{dp}[i][j - 1] + \textit{dp}[i - 1][j - d]$。
由此我们得到新的动态转移方程，优化之前算法的复杂度。最后，我们返回 $\textit{dp}[n - 1]$ 的和即为结果。
代码
###C++
class Solution {
public:
int countOfPairs(vector<int>& nums) {
int n = nums.size(), m = 0, mod = 1e9 + 7;
for (int num : nums) {
m = max(m, num);
}
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
for (int a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (int i = 1; i < n; i++) {
int d = max(0, nums[i] - nums[i - 1]);
for (int j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
int res = 0;
for (int num : dp[n - 1]) {
res = (res + num) % mod;
}
return res;
}
};
###Java
class Solution {
public int countOfPairs(int[] nums) {
int n = nums.length, m = 0, mod = 1000000007;
for (int num : nums) {
m = Math.max(m, num);
}
int[][] dp = new int[n][m + 1];
for (int a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (int i = 1; i < n; i++) {
int d = Math.max(0, nums[i] - nums[i - 1]);
for (int j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
int res = 0;
for (int num : dp[n - 1]) {
res = (res + num) % mod;
}
return res;
}
}
###Python
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
mod = 10 ** 9 + 7
n, m = len(nums), max(nums)
dp = [[0] * (m + 1) for _ in range(n)]
for a in range(nums[0] + 1):
dp[0][a] = 1
for i in range(1, n):
d = max(0, nums[i] - nums[i - 1])
for j in range(d, nums[i] + 1):
if j == 0:
dp[i][j] = dp[i - 1][j - d]
else:
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod
return sum(dp[n - 1]) % mod
###JavaScript
var countOfPairs = function(nums) {
const n = nums.length;
const m = Math.max(...nums);
const mod = 1e9 + 7;
const dp = Array(n).fill(0).map(() => Array(m + 1).fill(0));
for (let a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (let i = 1; i < n; i++) {
const d = Math.max(0, nums[i] - nums[i - 1]);
for (let j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
let res = 0;
for (let num of dp[n - 1]) {
res = (res + num) % mod;
}
return res;
};
###TypeScript
function countOfPairs(nums: number[]): number {
const n = nums.length;
const m = Math.max(...nums);
const mod = 1e9 + 7;
const dp = Array(n).fill(0).map(() => Array(m + 1).fill(0));
for (let a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (let i = 1; i < n; i++) {
const d = Math.max(0, nums[i] - nums[i - 1]);
for (let j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
let res = 0;
for (let num of dp[n - 1]) {
res = (res + num) % mod;
}
return res;
};
###Go
func countOfPairs(nums []int) int {
n := len(nums)
m := 0
for _, num := range nums {
if num > m {
m = num
}
}
mod := int(1e9 + 7)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, m+1)
}
for a := 0; a <= nums[0]; a++ {
dp[0][a] = 1
}
for i := 1; i < n; i++ {
d := max(0, nums[i]-nums[i-1])
for j := d; j <= nums[i]; j++ {
if j == 0 {
dp[i][j] = dp[i-1][j-d]
} else {
dp[i][j] = (dp[i][j-1] + dp[i-1][j-d]) % mod
}
}
}
res := 0
for _, num := range dp[n-1] {
res = (res + num) % mod
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
###C#
public class Solution {
public int CountOfPairs(int[] nums) {
int n = nums.Length;
int m = nums.Max();
int mod = (int)(1e9 + 7);
int[][] dp = new int[n][];
for (int i = 0; i < n; i++) {
dp[i] = new int[m + 1];
}
for (int a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (int i = 1; i < n; i++) {
int d = Math.Max(0, nums[i] - nums[i - 1]);
for (int j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
int res = 0;
for (int num in dp[n - 1]) {
res = (res + num) % mod;
}
return res;
}
}
###C
int countOfPairs(int* nums, int numsSize) {
int n = numsSize, m = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > m) {
m = nums[i];
}
}
int mod = 1e9 + 7;
int **dp = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = (int *)malloc((m + 1) * sizeof(int));
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
for (int a = 0; a <= nums[0]; a++) {
dp[0][a] = 1;
}
for (int i = 1; i < n; i++) {
int d = (nums[i] - nums[i - 1]) > 0 ? (nums[i] - nums[i - 1]) : 0;
for (int j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][j - d];
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod;
}
}
}
int res = 0;
for (int j = 0; j <= m; j++) {
res = (res + dp[n - 1][j]) % mod;
}
for (int i = 0; i < n; i++) {
free(dp[i]);
}
free(dp);
return res;
}
###Rust
impl Solution {
pub fn count_of_pairs(nums: Vec<i32>) -> i32 {
let n = nums.len();
let m = *nums.iter().max().unwrap();
let mod_val = 1000000007;
let mut dp = vec![vec![0; (m + 1) as usize]; n];
for a in 0..=nums[0] {
dp[0][a as usize] = 1;
}
for i in 1..n {
let d = std::cmp::max(0, nums[i] - nums[i - 1]);
for j in d..=nums[i] {
if j == 0 {
dp[i][j as usize] = dp[i - 1][(j - d) as usize];
} else {
dp[i][j as usize] = (dp[i][(j - 1) as usize] + dp[i - 1][(j - d) as usize]) % mod_val;
}
}
}
dp[n - 1].iter().fold(0, |acc, &x| (acc + x) % mod_val)
}
}
复杂度分析
时间复杂度：$O(nm)$，其中 $n$ 是数组的长度，$m$ 是数组的最大值。
空间复杂度：$O(nm)$，其中 $n$ 是数组的长度，$m$ 是数组的最大值，可以优化到一维空间 $O(m)$。
本题解没讲太多细节，需要读者有 DP 基础。
记 $i$ 为数组下标（从 0 开始），$j = arr1[i]$, $k = arr1[i-1]$
根据题意
arr1 非递减，所以限制 $k \leq j$arr2 非递增，所以限制 $nums[i-1] - k \geq nums[i] - j$所以 $0 \leq k \leq min(j, nums[i-1] - nums[i] + j)$
记 $ceil = min(j,\ nums[i-1] - nums[i] + j)$
可得状态转移方程 $f(i, j) = \sum\limits_{k=0}^{ceil} f(i-1, k)$
初始状态为
$$
f(0, j) =
\begin{cases}
1 & if\ j \in [0, nums[0]]\
0 & 其他
\end{cases}
$$
在多维的实现中，计算每行的每个元素时都要取上一行的某段前缀和。
###C++
class Solution {
public:
int countOfPairs(vector<int>& nums) {
const int MOD = 1e9 + 7;
int m = nums.size();
int n = *max_element(nums.begin(), nums.end());
vector<int> f(n + 1);
// 初始状态
for (int v = 0; v <= nums[0]; ++v)
f[v] = 1;
vector<int> preSums;
// 多执行一轮
for (int i = 1; i <= m; ++i) {
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear();
int preSum = 0;
for(int v : f){
preSum += v;
preSum %= MOD;
preSums.push_back(preSum);
}
// 最后一轮提前返回结尾处的方案数总和
if (i == m) return preSums.back();
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for (int j = 0; j <= nums[i]; ++j) {
int ceil = min(j, nums[i-1] - nums[i] + j);
if (ceil >= 0)
f[j] = preSums[ceil];
else // ceil < 0 说明不存在
f[j] = 0;
}
for (int j = nums[i] + 1; j < f.size(); ++j) {
f[j] = 0;
}
}
// 不会执行
return 0;
}
};
###Python3
class Solution:
def countOfPairs(self, nums):
MOD = 1_000_000_007
m = len(nums)
n = max(nums)
f = [0] * (n + 1)
# 初始状态
for v in range(nums[0] + 1):
f[v] = 1
preSums = []
# 多执行一轮
for i in range(1, m + 1):
# 前缀和，此处不重复开辟空间以提升性能。
preSums.clear()
preSum = 0
for v in f:
preSum += v
preSum %= MOD
preSums.append(preSum)
# 最后一轮提前返回结尾处的方案数总和
if i == m:
return preSums[-1]
# 优化空间，二维变一维，没用到的格子都要使元素归 0
for j in range(nums[i] + 1):
ceil = min(j, nums[i-1] - nums[i] + j)
if ceil >= 0:
f[j] = preSums[ceil]
else: # ceil < 0 说明不存在
f[j] = 0
for j in range(nums[i] + 1, len(f)):
f[j] = 0
# 不会执行
return 0
###Java
class Solution {
public int countOfPairs(int[] nums) {
final int MOD = (int)(1e9 + 7);
int m = nums.length;
int n = Arrays.stream(nums).max().getAsInt();
int[] f = new int[n + 1];
// 初始状态
for (int v = 0; v <= nums[0]; ++v) f[v] = 1;
List<Integer> preSums = new ArrayList<>();
// 多执行一轮
for (int i = 1; i <= m; ++i) {
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear();
int preSum = 0;
for(int v : f){
preSum += v;
preSum %= MOD;
preSums.add(preSum);
}
// 最后一轮提前返回结尾处的方案数总和
if (i == m) return preSums.get(preSums.size() - 1);
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for (int j = 0; j <= nums[i]; ++j) {
int ceil = Math.min(j, nums[i-1] - nums[i] + j);
if (ceil >= 0)
f[j] = preSums.get(ceil);
else // ceil < 0 说明不存在
f[j] = 0;
}
for (int j = nums[i] + 1; j < f.length; ++j) {
f[j] = 0;
}
}
// 不会执行
return 0;
}
}
###Kotlin
class Solution {
fun countOfPairs(nums: IntArray): Int {
val MOD = 1_000_000_007
val m = nums.size
val n = nums.max()
val f = IntArray(n+1)
// 初始状态
for(v in 0..nums[0]) f[v] = 1
val preSums = mutableListOf<Int>()
// 多执行一轮
for(i in 1..m){
// 前缀和，此处不重复开辟空间以提升性能。
preSums.clear()
for(v in f){
val lastPreSum = preSums.lastOrNull() ?: 0
preSums += (lastPreSum + v) % MOD
}
// 最后一轮提前返回结尾处的方案数总和
if(i == m) return preSums.last()
// 优化空间，二维变一维，没用到的格子都要使元素归 0
for(j in 0..nums[i]){
val ceil = min(j, nums[i-1] - nums[i] + j)
if(ceil >= 0)
f[j] = preSums[ceil]
else // ceil < 0 说明不存在
f[j] = 0
}
for(j in (nums[i] + 1)..f.lastIndex){
f[j] = 0
}
}
// 不会执行
return 0
}
}
记 $m$ 为 nums 长度，$n$ 为 nums 元素最大值。
f 的长度限制为 nums 最后一个元素的大小 + 1。我就偷懒不写这么详细了。
以下皆为个人所著，兼顾了职场面试和本硕阶段的学术考试。
点赞关注不迷路。祝君早日上岸，飞黄腾达！
本题和 3251. 单调数组对的数目 II 是一样的，请看 我的题解。
优化之前的 $\mathcal{O}(nm^2)$ 记忆化搜索和递推的做法，请看 视频讲解 第三题，欢迎点赞关注~
思路
遍历数组 $\textit{colors}$，用一个整数 $\textit{cnt}$ 代表遍历到当前元素时，已经有的连续交替瓷砖的数量。如果当前元素与前一个元素不同，则将 $\textit{cnt}$ 加 $1$，否则将其置为 $1$。 如果当前 $\textit{cnt}$ 大于等于 $k$，则将结果加 $1$。注意到瓷砖是环形的，因此，在遍历到第一个数时，我们就需要知道当前的 $\textit{cnt}$。为了得到初始的 $\textit{cnt}$ 值，我们需要将遍历的起点往前推 $k-2$ 步，这样在遍历到数组的第一个元素时，我们就可以知道当前是否有 $k$ 块连续的交替瓷砖。最后返回结果。
代码
###Python
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
n = len(colors)
res, cnt = 0, 1
for i in range(-k + 2, n, 1):
if colors[i] != colors[i - 1]:
cnt += 1
else:
cnt = 1
if cnt >= k:
res += 1
return res
###Java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int n = colors.length;
int res = 0, cnt = 1;
for (int i = -k + 2; i < n; i++) {
if (colors[(i + n) % n] != colors[(i - 1 + n) % n]) {
cnt += 1;
} else {
cnt = 1;
}
if (cnt >= k) {
res += 1;
}
}
return res;
}
}
###C#
public class Solution {
public int NumberOfAlternatingGroups(int[] colors, int k) {
int n = colors.Length;
int res = 0, cnt = 1;
for (int i = -k + 2; i < n; i++) {
if (colors[(i + n) % n] != colors[(i - 1 + n) % n]) {
cnt += 1;
} else {
cnt = 1;
}
if (cnt >= k) {
res += 1;
}
}
return res;
}
}
###C++
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int n = colors.size();
int res = 0, cnt = 1;
for (int i = -k + 2; i < n; i++) {
if (colors[(i + n) % n] != colors[(i - 1 + n) % n]) {
cnt += 1;
} else {
cnt = 1;
}
if (cnt >= k) {
res += 1;
}
}
return res;
}
};
###Go
func numberOfAlternatingGroups(colors []int, k int) int {
n := len(colors)
res, cnt := 0, 1
for i := -k + 2; i < n; i++ {
if colors[(i + n) % n] != colors[(i - 1 + n) % n] {
cnt++
} else {
cnt = 1
}
if cnt >= k {
res++
}
}
return res
}
###C
int numberOfAlternatingGroups(int* colors, int colorsSize, int k) {
int res = 0, cnt = 1;
for (int i = -k + 2; i < colorsSize; i++) {
if (colors[(i + colorsSize) % colorsSize] != colors[(i - 1 + colorsSize) % colorsSize]) {
cnt += 1;
} else {
cnt = 1;
}
if (cnt >= k) {
res += 1;
}
}
return res;
}
###JavaScript
var numberOfAlternatingGroups = function(colors, k) {
const n = colors.length;
let res = 0, cnt = 1;
for (let i = -k + 2; i < n; i++) {
if (colors[(i + n) % n] !== colors[(i - 1 + n) % n]) {
cnt++;
} else {
cnt = 1;
}
if (cnt >= k) {
res++;
}
}
return res;
};
###TypeScript
function numberOfAlternatingGroups(colors: number[], k: number): number {
const n = colors.length;
let res = 0, cnt = 1;
for (let i = -k + 2; i < n; i++) {
if (colors[(i + n) % n] !== colors[(i - 1 + n) % n]) {
cnt++;
} else {
cnt = 1;
}
if (cnt >= k) {
res++;
}
}
return res;
};
###Rust
impl Solution {
pub fn number_of_alternating_groups(colors: Vec<i32>, k: i32) -> i32 {
let n = colors.len() as i32;
let mut res = 0;
let mut cnt = 1;
for i in (-k + 2)..n {
if colors[((i + n) % n) as usize] != colors[((i - 1 + n) % n) as usize] {
cnt += 1;
} else {
cnt = 1;
}
if cnt >= k {
res += 1;
}
}
res
}
}
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(1)$。
我们可以将环展开成一个长度为 $2n$ 的数组，然后从左到右遍历这个数组，用一个变量 $\textit{cnt}$ 记录当前交替组的长度，如果遇到了相同的颜色，就将 $\textit{cnt}$ 重置为 $1$，否则将 $\textit{cnt}$ 加一。如果 $\textit{cnt} \ge k$，并且当前位置 $i$ 大于等于 $n$，那么就找到了一个交替组，答案加一。
遍历结束后，返回答案即可。
###python
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
n = len(colors)
ans = cnt = 0
for i in range(n << 1):
if i and colors[i % n] == colors[(i - 1) % n]:
cnt = 1
else:
cnt += 1
ans += i >= n and cnt >= k
return ans
###java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int n = colors.length;
int ans = 0, cnt = 0;
for (int i = 0; i < n << 1; ++i) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int n = colors.size();
int ans = 0, cnt = 0;
for (int i = 0; i < n << 1; ++i) {
if (i && colors[i % n] == colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
};
###go
func numberOfAlternatingGroups(colors []int, k int) (ans int) {
n := len(colors)
cnt := 0
for i := 0; i < n<<1; i++ {
if i > 0 && colors[i%n] == colors[(i-1)%n] {
cnt = 1
} else {
cnt++
}
if i >= n && cnt >= k {
ans++
}
}
return
}
###ts
function numberOfAlternatingGroups(colors: number[], k: number): number {
const n = colors.length;
let [ans, cnt] = [0, 0];
for (let i = 0; i < n << 1; ++i) {
if (i && colors[i % n] === colors[(i - 1) % n]) {
cnt = 1;
} else {
++cnt;
}
ans += i >= n && cnt >= k ? 1 : 0;
}
return ans;
}
时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{colors}$ 的长度。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：
colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
示例 1：
输入：colors = [0,1,0,1,0], k = 3
输出：3
解释：
交替组包括：
示例 2：
输入：colors = [0,1,0,0,1,0,1], k = 6
输出：2
解释：
交替组包括：
示例 3：
输入：colors = [1,1,0,1], k = 4
输出：0
解释：
提示：
3 <= colors.length <= 1050 <= colors[i] <= 13 <= k <= colors.length本题是环形数组，请先完成普通数组的版本：3101. 交替子数组计数（我的题解）
把数组复制一份拼接起来，和 3101 题一样，遍历数组的同时，维护以 $i$ 为右端点的交替子数组的长度 $\textit{cnt}$。
如果 $i\ge n$ 且 $\textit{cnt}\ge k$，那么 $i$ 就是一个长为 $k$ 的交替子数组的右端点，答案加一。注意这里要判断 $i\ge n$，从而避免重复统计。
代码实现时，不需要复制数组，而是用 $i\bmod n$ 的方式取到对应的值。
具体请看 视频讲解 第三题，欢迎点赞关注~
###py
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
n = len(colors)
ans = cnt = 0
for i in range(n * 2):
if i > 0 and colors[i % n] == colors[(i - 1) % n]:
cnt = 0
cnt += 1
if i >= n and cnt >= k:
ans += 1
return ans
###java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int n = colors.length;
int ans = 0;
int cnt = 0;
for (int i = 0; i < n * 2; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
if (i >= n && cnt >= k) {
ans++;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int n = colors.size();
int ans = 0, cnt = 0;
for (int i = 0; i < n * 2; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
ans += i >= n && cnt >= k;
}
return ans;
}
};
###c
int numberOfAlternatingGroups(int* colors, int n, int k) {
int ans = 0, cnt = 0;
for (int i = 0; i < n * 2; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
if (i >= n && cnt >= k) {
ans++;
}
}
return ans;
}
###go
func numberOfAlternatingGroups(colors []int, k int) (ans int) {
n := len(colors)
cnt := 0
for i := range n * 2 {
if i > 0 && colors[i%n] == colors[(i-1)%n] {
cnt = 0
}
cnt++
if i >= n && cnt >= k {
ans++
}
}
return
}
###js
var numberOfAlternatingGroups = function(colors, k) {
const n = colors.length;
let ans = 0, cnt = 0;
for (let i = 0; i < n * 2; i++) {
if (i > 0 && colors[i % n] === colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
if (i >= n && cnt >= k) {
ans++;
}
}
return ans;
};
###rust
impl Solution {
pub fn number_of_alternating_groups(colors: Vec<i32>, k: i32) -> i32 {
let n = colors.len();
let mut ans = 0;
let mut cnt = 0;
for i in 0..n * 2 {
if i > 0 && colors[i % n] == colors[(i - 1) % n] {
cnt = 0;
}
cnt += 1;
if i >= n && cnt >= k {
ans += 1;
}
}
ans
}
}
一共有 $n$ 个子数组：
上面的循环可以改成循环到 $n+k-2$ 为止。由于没有重复统计，无需判断 $i\ge n$。
###py
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
n = len(colors)
ans = cnt = 0
for i in range(n + k - 1):
if i > 0 and colors[i % n] == colors[(i - 1) % n]:
cnt = 0
cnt += 1
if cnt >= k:
ans += 1
return ans
###java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int n = colors.length;
int ans = 0;
int cnt = 0;
for (int i = 0; i < n + k - 1; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
if (cnt >= k) {
ans++;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int n = colors.size();
int ans = 0, cnt = 0;
for (int i = 0; i < n + k - 1; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
ans += cnt >= k;
}
return ans;
}
};
###c
int numberOfAlternatingGroups(int* colors, int n, int k) {
int ans = 0, cnt = 0;
for (int i = 0; i < n + k - 1; i++) {
if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
ans += cnt >= k;
}
return ans;
}
###go
func numberOfAlternatingGroups(colors []int, k int) (ans int) {
n := len(colors)
cnt := 0
for i := range n + k - 1 {
if i > 0 && colors[i%n] == colors[(i-1)%n] {
cnt = 0
}
cnt++
if cnt >= k {
ans++
}
}
return
}
###js
var numberOfAlternatingGroups = function(colors, k) {
const n = colors.length;
let ans = 0, cnt = 0;
for (let i = 0; i < n + k - 1; i++) {
if (i > 0 && colors[i % n] === colors[(i - 1) % n]) {
cnt = 0;
}
cnt++;
if (cnt >= k) {
ans++;
}
}
return ans;
};
###rust
impl Solution {
pub fn number_of_alternating_groups(colors: Vec<i32>, k: i32) -> i32 {
let n = colors.len();
let mut ans = 0;
let mut cnt = 0;
for i in 0..n + k as usize - 1 {
if i > 0 && colors[i % n] == colors[(i - 1) % n] {
cnt = 0;
}
cnt += 1;
if cnt >= k {
ans += 1;
}
}
ans
}
}
欢迎关注 B站@灵茶山艾府
