给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15.
示例 2：
输入：matrix = [ [1,0,1], [1,1,0], [1,1,0] ] 输出：7 解释： 边长为 1 的正方形有 6 个。 边长为 2 的正方形有 1 个。 正方形的总数 = 6 + 1 = 7.
提示：
登录1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1思路启发：学习 二维前缀和 对于想出本题的转移方程有帮助。
整理上图中的结论。定义 $f_{i,j}$ 为右下角在 $(i,j)$ 的全 $1$ 正方形的最大边长。我们有
$$
f_{i,j} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i-1,j-1},f_{i-1,j},f_{i,j-1}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$
然而，当 $i=0$ 或者 $j=0$ 时，上式会产生负数下标 $-1$。
为避免出现负数下标，可以在 $f$ 矩阵的最上边添加一行 $0$，最左边添加一列 $0$，对应下标出界的状态（正方形的最大边长为 $0$）。
由于修改了 $f$，状态转移方程中的 $f$ 的下标要加一，即
$$
f_{i+1,j+1} =
\begin{cases}
0, & \textit{matrix}{i,j} = 0 \
\min(f{i,j},f_{i,j+1},f_{i+1,j}) + 1, & \textit{matrix}_{i,j} = 1 \
\end{cases}
$$
注意 $\textit{matrix}$ 的下标是不用变的，因为我们只是在 $f$ 矩阵的上边和左边插入了 $0$，所以只有 $f$ 的下标受此影响需要加一。
初始值 $f_{0,j} = f_{i,0} = 0$。
根据图中的结论（个数等于最大边长），答案为整个 $f$ 矩阵的元素和。
###py
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
f = [[0] * (n + 1) for _ in range(m + 1)]
for i, row in enumerate(matrix):
for j, x in enumerate(row):
if x:
f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1
return sum(map(sum, f))
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] f = new int[m + 1][n + 1];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] > 0) {
f[i + 1][j + 1] = Math.min(Math.min(f[i][j], f[i][j + 1]), f[i + 1][j]) + 1;
ans += f[i + 1][j + 1];
}
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector f(m + 1, vector<int>(n + 1));
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j]) {
f[i + 1][j + 1] = min({f[i][j], f[i][j + 1], f[i + 1][j]}) + 1;
ans += f[i + 1][j + 1];
}
}
}
return ans;
}
};
###go
func countSquares(matrix [][]int) (ans int) {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for i, row := range matrix {
for j, x := range row {
if x > 0 {
f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1
ans += f[i+1][j+1]
}
}
}
return
}
直接把 $\textit{matrix}$ 当作 $f$，原地修改。
###py
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
for i, row in enumerate(matrix):
for j, x in enumerate(row):
if x and i and j:
row[j] += min(matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1])
return sum(map(sum, matrix))
###java
class Solution {
public int countSquares(int[][] matrix) {
int ans = 0;
for (int i = 0; i < matrix.length; i++) {
int[] row = matrix[i];
for (int j = 0; j < row.length; j++) {
if (row[j] > 0 && i > 0 && j > 0) {
row[j] += Math.min(Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]), row[j - 1]);
}
ans += row[j];
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int ans = 0;
for (int i = 0; i < matrix.size(); i++) {
auto& row = matrix[i];
for (int j = 0; j < row.size(); j++) {
if (i && j && row[j]) {
row[j] += min({matrix[i - 1][j], matrix[i - 1][j - 1], row[j - 1]});
}
ans += row[j];
}
}
return ans;
}
};
###go
func countSquares(matrix [][]int) (ans int) {
for i, row := range matrix {
for j, x := range row {
if x > 0 && i > 0 && j > 0 {
row[j] += min(matrix[i-1][j], matrix[i-1][j-1], row[j-1])
}
ans += row[j]
}
}
return
}
见下面动态规划题单的「§7.5 子矩形 DP」。
欢迎关注 B站@灵茶山艾府
思路
我们用 $f[i][j]$ 表示以 $(i, j)$ 为右下角的正方形的最大边长，那么除此定义之外，$f[i][j] = x$ 也表示以 $(i, j)$ 为右下角的正方形的数目为 $x$（即边长为 $1, 2, \cdots, x$ 的正方形各一个）。在计算出所有的 $f[i][j]$ 后，我们将它们进行累加，就可以得到矩阵中正方形的数目。
我们尝试挖掘 $f[i][j]$ 与相邻位置的关系来计算出 $f[i][j]$ 的值。
如上图所示，若对于位置 $(i, j)$ 有 $f[i][j] = 4$，我们将以 $(i, j)$ 为右下角、边长为 $4$ 的正方形涂上色，可以发现其左侧位置 $(i, j - 1)$，上方位置 $(i - 1, j)$ 和左上位置 $(i - 1, j - 1)$ 均可以作为一个边长为 $4 - 1 = 3$ 的正方形的右下角。也就是说，这些位置的的 $f$ 值至少为 $3$，即：
将这三个不等式联立，可以得到：
$$\texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])\ge f[i][j]−1$$
这是我们通过固定 $f[i][j]$ 的值，判断其相邻位置与之的关系得到的不等式。同理，我们也可以固定 $f[i][j]$ 相邻位置的值，得到另外的限制条件。
如上图所示，假设 $f[i][j - 1]$，$f[i - 1][j]$ 和 $f[i - 1][j - 1]$ 中的最小值为 $3$，即，$(i, j - 1)$，$(i - 1, j)$ 和 $(i - 1, j - 1)$ 均可以作为一个边长为 $3$ 的正方形的右下角。我们将这些边长为 $3$ 的正方形依次涂上色，可以发现，如果位置 $(i, j)$ 的元素为 $1$，那么它可以作为一个边长为 $4$ 的正方形的右下角，$f$ 值至少为 $4$，即：
$$f[i][j]\geq \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$
将其与上一个不等式联立，可以得到：
$$f[i][j] = \texttt{min}(f[i][j−1],f[i−1][j],f[i−1][j−1])+1$$
再考虑一些边界情况，我们就得到了完整的递推式：
$$
f[i][j] =
\begin{cases}
matrix[i][j] & \texttt{if } i=0 \texttt{ or } j=0 \
0 & \texttt{if } matrix[i][j]=0 \
\min(f[i][j-1], f[i-1][j], f[i-1][j-1]) + 1 & \texttt{otherwise}
\end{cases}
$$
我们按照行优先的顺序依次计算 $f[i][j]$ 的值，累加就可以得到最终的答案。
代码
###Python
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
f = [[0] * n for _ in range(m)]
ans = 0
for i in range(m):
for j in range(n):
if i == 0 or j == 0:
f[i][j] = matrix[i][j]
elif matrix[i][j] == 0:
f[i][j] = 0
else:
f[i][j] = min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1
ans += f[i][j]
return ans
###C++
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> f(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = min({f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]}) + 1;
}
ans += f[i][j];
}
}
return ans;
}
};
###Java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] f = new int[m][n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(Math.min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
}
}
###C#
public class Solution {
public int CountSquares(int[][] matrix) {
int m = matrix.Length, n = matrix[0].Length;
int[,] f = new int[m, n];
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i, j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i, j] = 0;
} else {
f[i, j] = Math.Min(Math.Min(f[i, j - 1], f[i - 1, j]), f[i - 1, j - 1]) + 1;
}
ans += f[i, j];
}
}
return ans;
}
}
###Go
func countSquares(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 || j == 0 {
f[i][j] = matrix[i][j]
} else if matrix[i][j] == 0 {
f[i][j] = 0
} else {
f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1
}
ans += f[i][j]
}
}
return ans
}
###C
int countSquares(int** matrix, int matrixSize, int* matrixColSize) {
int m = matrixSize, n = matrixColSize[0];
int** f = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; ++i) {
f[i] = (int*)malloc(n * sizeof(int));
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] == 0) {
f[i][j] = 0;
} else {
f[i][j] = fmin(f[i][j - 1], fmin(f[i - 1][j], f[i - 1][j - 1])) + 1;
}
ans += f[i][j];
}
}
for (int i = 0; i < m; ++i) {
free(f[i]);
}
free(f);
return ans;
}
###JavaScript
var countSquares = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i === 0 || j === 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] === 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
};
###TypeScript
function countSquares(matrix: number[][]): number {
const m = matrix.length, n = matrix[0].length;
const f: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(0));
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (i === 0 || j === 0) {
f[i][j] = matrix[i][j];
} else if (matrix[i][j] === 0) {
f[i][j] = 0;
} else {
f[i][j] = Math.min(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
return ans;
}
###Rust
impl Solution {
pub fn count_squares(matrix: Vec<Vec<i32>>) -> i32 {
let m = matrix.len();
let n = matrix[0].len();
let mut f = vec![vec![0; n]; m];
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if i == 0 || j == 0 {
f[i][j] = matrix[i][j];
} else if matrix[i][j] == 0 {
f[i][j] = 0;
} else {
f[i][j] = f[i][j - 1].min(f[i - 1][j]).min(f[i - 1][j - 1]) + 1;
}
ans += f[i][j];
}
}
ans
}
}
复杂度分析
时间复杂度：$O(m\times n)$，其中 $m$ 和 $n$ 是输入 $\textit{matrix}$ 的行和列。
空间复杂度：$O(m\times n)$。
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
示例 1：
输入：
matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出： 15
解释：
边长为1的正方形有10个。
边长为2的正方形有4个。
边长为3的正方形有1个。
正方形的总数 =10+4+1=15.
示例 2：
输入：
matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出： 7
解释：
边长为1的正方形有6个。
边长为2的正方形有1个。
正方形的总数 =6+1=7.
首先，暴力解就是以矩阵每一个点为起点，依次判断边长为1，2，3，...，min{m, n}的区域是否是全1正方形(该区域所有点的和等于该区域面积)，显然，这种复杂度是过不了的。
很容易知道，上述过程在判断较大区域是否为正方形的时候，并没有用到前面计算的结果，每一次判断都从头开始。这也是复杂度过高的原因。
那么怎么利用之前判断过的结果呢？举个例子，比如我要判断以(2, 3)为右下角边长为3的正方形区域（红色边框区域）是否是全为1：
(i, j)位置是否为1，如果否，则显然不满足；如果是，进行下一步判断(i - 1, j), (i - 1, j - 1), (i, j - 1)为右下角的区域是否能构成边长为2的正方形，如果能，那就满足条件。
基于上述，我们可以看出思路大致跟最大正方形那题差不多，设dp[i][j][k]表示以(i, j)为右下角，边长为k的正方形区域是否全为1，那么易得出如下状态转移方程：
###java
dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int len = Math.min(m, n);
boolean[][][] dp = new boolean[m][n][len];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j][0] = (matrix[i][j] == 1);
count += dp[i][j][0] ? 1 : 0;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
for (int k = 1; k < len; k++) {
dp[i][j][k] = (matrix[i][j] == 1 && dp[i - 1][j][k - 1] && dp[i][j - 1][k - 1] && dp[i - 1][j - 1] [k - 1]);
if (dp[i][j][k]) {
count++;
}
}
}
}
return count;
}
}
经评论区@da-fei-kai提醒，上述代码可以做进一步优化。
首先，题目并不关心边长为
1,2,...,k的各有多少个，并且我们知道，以(i, j)为右下角边长为k的正方形全为1的话，那么以(i, j)为右下角边长分别为1,2,...,k - 1的正方形区域一定是全为1，如下图：
上图中，如果红色区域是边长为
3的全1正方形区域，那么它一定包含了一个边长为2和边长为1的全1正方形区域。所以，我们只需记录以(i, j)为右下角的区域包含的最大全1正方形边长即可，这个最大边长也即以(i , j)为右下角的全1正方形的个数.
那么基于此，我们就可以将原始的dp降一维度，设dp[i][j]表示以(i, j)为右下角的最大全1正方形区域的边长，则有如下状态转移方程：
###java
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
这就和最大正方形那题的状态转移方程完全一样了。
###java
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int ans = 0;
// 预处理每一行和每一列
for (int i = 0; i < m; i++) {
ans += dp[i][0] = matrix[i][0];
}
for (int j = 0; j < n; j++) {
ans += dp[0][j] = matrix[0][j];
}
// 上述过程(0, 0)判断了两次, 如果matrix[0][0] == 1，说明ans多算了一个
if (matrix[0][0] == 1) {
ans--;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
ans += dp[i][j];
}
}
}
return ans;
}
}
给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。
子数组 是一个数组中一段连续非空元素组成的序列。
示例 1：
输入：nums = [1,3,0,0,2,0,0,4] 输出：6 解释： 子数组 [0] 出现了 4 次。 子数组 [0,0] 出现了 2 次。 不存在长度大于 2 的全 0 子数组，所以我们返回 6 。
示例 2：
输入：nums = [0,0,0,2,0,0] 输出：9 解释： 子数组 [0] 出现了 5 次。 子数组 [0,0] 出现了 3 次。 子数组 [0,0,0] 出现了 1 次。 不存在长度大于 3 的全 0 子数组，所以我们返回 9 。
示例 3：
输入：nums = [2,10,2019] 输出：0 解释：没有全 0 子数组，所以我们返回 0 。
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109本题做法很多，下面讲两个更具一般性的方法。
子数组越长，越可能包含非零元素，不满足题目要求；子数组越短，越可能全为 $0$，满足题目要求。我们枚举子数组的右端点，当右端点变大（子数组变长）的时候，子数组左端点要么不变，要么也变大。
不仅是本题，有这样性质的题目，都可以用滑动窗口解决，见 滑动窗口【基础算法精讲 03】。
本题属于「越短越合法」型滑动窗口。由于题目的特殊性，有更简单的解决方法：
示例 1 的 $\textit{nums} = [1,3,0,0,2,0,0,4]$，当右端点在 $i=3$ 时，$\textit{last}=1$，我们找到了 $i-\textit{last}=2$ 个右端点在 $3$ 的全 $0$ 子数组，加入答案。
为了兼容 $\textit{nums}=[0,0,0,2,0,0]$ 这种一开始就是 $0$ 的情况，初始化 $\textit{last}=-1$。
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
ans = 0
last = -1
for i, x in enumerate(nums):
if x:
last = i # 记录上一个非 0 元素的位置
else:
ans += i - last
return ans
class Solution {
public long zeroFilledSubarray(int[] nums) {
long ans = 0;
int last = -1;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (x != 0) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
}
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long ans = 0;
int last = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i]) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
};
long long zeroFilledSubarray(int* nums, int numsSize) {
long long ans = 0;
int last = -1;
for (int i = 0; i < numsSize; i++) {
if (nums[i]) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
}
func zeroFilledSubarray(nums []int) (ans int64) {
last := -1
for i, x := range nums {
if x != 0 {
last = i // 记录上一个非 0 元素的位置
} else {
ans += int64(i - last)
}
}
return
}
var zeroFilledSubarray = function(nums) {
let ans = 0;
let last = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += i - last;
}
}
return ans;
};
impl Solution {
pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
let mut ans = 0;
let mut last = -1;
for (i, x) in nums.into_iter().enumerate() {
let i = i as i64;
if x != 0 {
last = i; // 记录上一个非 0 元素的位置
} else {
ans += (i - last) as i64;
}
}
ans
}
}
遍历到 $\textit{nums}[i]=0$，现在来计算右端点为 $i$ 的全 $0$ 子数组的个数。
我们可以在右端点为 $i-1$ 的全 $0$ 子数组的末尾添加一个 $0$。比如右端点为 $i-1$ 的全 $0$ 子数组有 $5$ 个，那么在这 $5$ 个子数组的末尾添加 $\textit{nums}[i]=0$，再算上 $\textit{nums}[i]$ 单独组成一个长为 $1$ 的子数组，我们得到了 $5+1=6$ 个右端点为 $i$ 的全 $0$ 子数组，加入答案。
具体来说：
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
ans = cnt0 = 0
for x in nums:
if x:
cnt0 = 0
else:
cnt0 += 1 # 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0
return ans
class Solution {
public long zeroFilledSubarray(int[] nums) {
long ans = 0;
int cnt0 = 0;
for (int x : nums) {
if (x != 0) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
}
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long ans = 0;
int cnt0 = 0;
for (int x : nums) {
if (x) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
};
long long zeroFilledSubarray(int* nums, int numsSize) {
long long ans = 0;
int cnt0 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i]) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
}
func zeroFilledSubarray(nums []int) (ans int64) {
cnt0 := 0
for _, x := range nums {
if x != 0 {
cnt0 = 0
} else {
cnt0++ // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += int64(cnt0)
}
}
return
}
var zeroFilledSubarray = function(nums) {
let ans = 0;
let cnt0 = 0;
for (const x of nums) {
if (x !== 0) {
cnt0 = 0;
} else {
cnt0++; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0;
}
}
return ans;
};
impl Solution {
pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
let mut ans = 0;
let mut cnt0 = 0;
for x in nums {
if x != 0 {
cnt0 = 0;
} else {
cnt0 += 1; // 右端点为 i 的全 0 子数组比右端点为 i-1 的全 0 子数组多一个
ans += cnt0 as i64;
}
}
ans
}
}
注：本题还有其他方法，例如找极大连续 $0$ 的长度，然后用等差数列计算。
方法一：滑动窗口题单的「§2.3.1 越短越合法」。
方法二：动态规划题单「§7.3 子数组 DP」的「思维扩展」。
欢迎关注 B站@灵茶山艾府
###python3
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
groups = [(char, len(list(group))) for char, group in groupby(nums)]
return sum(count * (count + 1) // 2 for char, count in groups if char == 0)
统计连续0出现的次数，即为构成当前子数组的数量：
一个0，构成数组：
[0] //第一个0
两个0，构成数组：
[0] //第一个0
[0,0] //第一个0和第二个0
[0] //第二个0
三个0，构成数组：
三个0包含两个0的所有情况：
[0] //第一个0
[0,0] //第一个0和第二个0
[0] //第二个0
两个0的所有情况+第三个0
[0] //第一个0 和第三个0（以[0]单独构成子数组）
[0,0,0] //第一个0和第二个0 和第三个0
[0,0] //第二个0 和第三个0
状态转移方程：
连续的n个0对答案的贡献 = 连续的n-1个0对答案的贡献 + n
###java
class Solution {
public long zeroFilledSubarray(int[] nums) {
long count = 0;//答案
int zeroCnt = 0;//当前0的个数
for (int x : nums) {
if (x == 0) {
zeroCnt++;
count += zeroCnt;
} else {
zeroCnt = 0;
}
}
return count;
}
}
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。
你须遵守以下规则:
'/' 表示实数除法，而不是整数除法。
4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。“-” 作为一元运算符。
cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。
示例 1:
输入: cards = [4, 1, 8, 7] 输出: true 解释: (8-4) * (7-1) = 24
示例 2:
输入: cards = [1, 2, 1, 2] 输出: false
提示:
cards.length == 41 <= cards[i] <= 9微软一面平行面出了这个题, 比这个还麻烦, 给的输入是 n 个数字
用的 Java 回溯解决的, 第一轮已经通过
提一下需要注意的细节
###Java
class Solution {
private static final double TARGET = 24;
private static final double EPISLON = 1e-6;
public boolean judgePoint24(int[] cards) {
return helper(new double[]{ cards[0], cards[1], cards[2], cards[3] });
}
private boolean helper(double[] nums) {
if (nums.length == 1) return Math.abs(nums[0] - TARGET) < EPISLON;
// 每次选择两个不同的数进行回溯
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
// 将选择出来的两个数的计算结果和原数组剩下的数加入 next 数组
double[] next = new double[nums.length - 1];
for (int k = 0, pos = 0; k < nums.length; k++) if (k != i && k != j) next[pos++] = nums[k];
for (double num : calculate(nums[i], nums[j])) {
next[next.length - 1] = num;
if (helper(next)) return true;
}
}
}
return false;
}
private List<Double> calculate(double a, double b) {
List<Double> list = new ArrayList<>();
list.add(a + b);
list.add(a - b);
list.add(b - a);
list.add(a * b);
if (!(Math.abs(b) < EPISLON)) list.add(a / b);
if (!(Math.abs(a) < EPISLON)) list.add(b / a);
return list;
}
}
Python一行大法好!
###Python
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
return sorted(nums) in [[1, 1, 1, 8], [1, 1, 2, 6], [1, 1, 2, 7], [1, 1, 2, 8], [1, 1, 2, 9], [1, 1, 3, 4], [1, 1, 3, 5], [1, 1, 3, 6], [1, 1, 3, 7], [1, 1, 3, 8], [1, 1, 3, 9], [1, 1, 4, 4], [1, 1, 4, 5], [1, 1, 4, 6], [1, 1, 4, 7], [1, 1, 4, 8], [1, 1, 4, 9], [1, 1, 5, 5], [1, 1, 5, 6], [1, 1, 5, 7], [1, 1, 5, 8], [1, 1, 6, 6], [1, 1, 6, 8], [1, 1, 6, 9], [1, 1, 8, 8], [1, 2, 2, 4], [1, 2, 2, 5], [1, 2, 2, 6], [1, 2, 2, 7], [1, 2, 2, 8], [1, 2, 2, 9], [1, 2, 3, 3], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3, 7], [1, 2, 3, 8], [1, 2, 3, 9], [1, 2, 4, 4], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4, 7], [1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5, 5], [1, 2, 5, 6], [1, 2, 5, 7], [1, 2, 5, 8], [1, 2, 5, 9], [1, 2, 6, 6], [1, 2, 6, 7], [1, 2, 6, 8], [1, 2, 6, 9], [1, 2, 7, 7], [1, 2, 7, 8], [1, 2, 7, 9], [1, 2, 8, 8], [1, 2, 8, 9], [1, 3, 3, 3], [1, 3, 3, 4], [1, 3, 3, 5], [1, 3, 3, 6], [1, 3, 3, 7], [1, 3, 3, 8], [1, 3, 3, 9], [1, 3, 4, 4], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4, 7], [1, 3, 4, 8], [1, 3, 4, 9], [1, 3, 5, 6], [1, 3, 5, 7], [1, 3, 5, 8], [1, 3, 5, 9], [1, 3, 6, 6], [1, 3, 6, 7], [1, 3, 6, 8], [1, 3, 6, 9], [1, 3, 7, 7], [1, 3, 7, 8], [1, 3, 7, 9], [1, 3, 8, 8], [1, 3, 8, 9], [1, 3, 9, 9], [1, 4, 4, 4], [1, 4, 4, 5], [1, 4, 4, 6], [1, 4, 4, 7], [1, 4, 4, 8], [1, 4, 4, 9], [1, 4, 5, 5], [1, 4, 5, 6], [1, 4, 5, 7], [1, 4, 5, 8], [1, 4, 5, 9], [1, 4, 6, 6], [1, 4, 6, 7], [1, 4, 6, 8], [1, 4, 6, 9], [1, 4, 7, 7], [1, 4, 7, 8], [1, 4, 7, 9], [1, 4, 8, 8], [1, 4, 8, 9], [1, 5, 5, 5], [1, 5, 5, 6], [1, 5, 5, 9], [1, 5, 6, 6], [1, 5, 6, 7], [1, 5, 6, 8], [1, 5, 6, 9], [1, 5, 7, 8], [1, 5, 7, 9], [1, 5, 8, 8], [1, 5, 8, 9], [1, 5, 9, 9], [1, 6, 6, 6], [1, 6, 6, 8], [1, 6, 6, 9], [1, 6, 7, 9], [1, 6, 8, 8], [1, 6, 8, 9], [1, 6, 9, 9], [1, 7, 7, 9], [1, 7, 8, 8], [1, 7, 8, 9], [1, 7, 9, 9], [1, 8, 8, 8], [1, 8, 8, 9], [2, 2, 2, 3], [2, 2, 2, 4], [2, 2, 2, 5], [2, 2, 2, 7], [2, 2, 2, 8], [2, 2, 2, 9], [2, 2, 3, 3], [2, 2, 3, 4], [2, 2, 3, 5], [2, 2, 3, 6], [2, 2, 3, 7], [2, 2, 3, 8], [2, 2, 3, 9], [2, 2, 4, 4], [2, 2, 4, 5], [2, 2, 4, 6], [2, 2, 4, 7], [2, 2, 4, 8], [2, 2, 4, 9], [2, 2, 5, 5], [2, 2, 5, 6], [2, 2, 5, 7], [2, 2, 5, 8], [2, 2, 5, 9], [2, 2, 6, 6], [2, 2, 6, 7], [2, 2, 6, 8], [2, 2, 6, 9], [2, 2, 7, 7], [2, 2, 7, 8], [2, 2, 8, 8], [2, 2, 8, 9], [2, 3, 3, 3], [2, 3, 3, 5], [2, 3, 3, 6], [2, 3, 3, 7], [2, 3, 3, 8], [2, 3, 3, 9], [2, 3, 4, 4], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4, 7], [2, 3, 4, 8], [2, 3, 4, 9], [2, 3, 5, 5], [2, 3, 5, 6], [2, 3, 5, 7], [2, 3, 5, 8], [2, 3, 5, 9], [2, 3, 6, 6], [2, 3, 6, 7], [2, 3, 6, 8], [2, 3, 6, 9], [2, 3, 7, 7], [2, 3, 7, 8], [2, 3, 7, 9], [2, 3, 8, 8], [2, 3, 8, 9], [2, 3, 9, 9], [2, 4, 4, 4], [2, 4, 4, 5], [2, 4, 4, 6], [2, 4, 4, 7], [2, 4, 4, 8], [2, 4, 4, 9], [2, 4, 5, 5], [2, 4, 5, 6], [2, 4, 5, 7], [2, 4, 5, 8], [2, 4, 5, 9], [2, 4, 6, 6], [2, 4, 6, 7], [2, 4, 6, 8], [2, 4, 6, 9], [2, 4, 7, 7], [2, 4, 7, 8], [2, 4, 7, 9], [2, 4, 8, 8], [2, 4, 8, 9], [2, 4, 9, 9], [2, 5, 5, 7], [2, 5, 5, 8], [2, 5, 5, 9], [2, 5, 6, 6], [2, 5, 6, 7], [2, 5, 6, 8], [2, 5, 6, 9], [2, 5, 7, 7], [2, 5, 7, 8], [2, 5, 7, 9], [2, 5, 8, 8], [2, 5, 8, 9], [2, 6, 6, 6], [2, 6, 6, 7], [2, 6, 6, 8], [2, 6, 6, 9], [2, 6, 7, 8], [2, 6, 7, 9], [2, 6, 8, 8], [2, 6, 8, 9], [2, 6, 9, 9], [2, 7, 7, 8], [2, 7, 8, 8], [2, 7, 8, 9], [2, 8, 8, 8], [2, 8, 8, 9], [2, 8, 9, 9], [3, 3, 3, 3], [3, 3, 3, 4], [3, 3, 3, 5], [3, 3, 3, 6], [3, 3, 3, 7], [3, 3, 3, 8], [3, 3, 3, 9], [3, 3, 4, 4], [3, 3, 4, 5], [3, 3, 4, 6], [3, 3, 4, 7], [3, 3, 4, 8], [3, 3, 4, 9], [3, 3, 5, 5], [3, 3, 5, 6], [3, 3, 5, 7], [3, 3, 5, 9], [3, 3, 6, 6], [3, 3, 6, 7], [3, 3, 6, 8], [3, 3, 6, 9], [3, 3, 7, 7], [3, 3, 7, 8], [3, 3, 7, 9], [3, 3, 8, 8], [3, 3, 8, 9], [3, 3, 9, 9], [3, 4, 4, 4], [3, 4, 4, 5], [3, 4, 4, 6], [3, 4, 4, 7], [3, 4, 4, 8], [3, 4, 4, 9], [3, 4, 5, 5], [3, 4, 5, 6], [3, 4, 5, 7], [3, 4, 5, 8], [3, 4, 5, 9], [3, 4, 6, 6], [3, 4, 6, 8], [3, 4, 6, 9], [3, 4, 7, 7], [3, 4, 7, 8], [3, 4, 7, 9], [3, 4, 8, 9], [3, 4, 9, 9], [3, 5, 5, 6], [3, 5, 5, 7], [3, 5, 5, 8], [3, 5, 5, 9], [3, 5, 6, 6], [3, 5, 6, 7], [3, 5, 6, 8], [3, 5, 6, 9], [3, 5, 7, 8], [3, 5, 7, 9], [3, 5, 8, 8], [3, 5, 8, 9], [3, 5, 9, 9], [3, 6, 6, 6], [3, 6, 6, 7], [3, 6, 6, 8], [3, 6, 6, 9], [3, 6, 7, 7], [3, 6, 7, 8], [3, 6, 7, 9], [3, 6, 8, 8], [3, 6, 8, 9], [3, 6, 9, 9], [3, 7, 7, 7], [3, 7, 7, 8], [3, 7, 7, 9], [3, 7, 8, 8], [3, 7, 8, 9], [3, 7, 9, 9], [3, 8, 8, 8], [3, 8, 8, 9], [3, 8, 9, 9], [3, 9, 9, 9], [4, 4, 4, 4], [4, 4, 4, 5], [4, 4, 4, 6], [4, 4, 4, 7], [4, 4, 4, 8], [4, 4, 4, 9], [4, 4, 5, 5], [4, 4, 5, 6], [4, 4, 5, 7], [4, 4, 5, 8], [4, 4, 6, 8], [4, 4, 6, 9], [4, 4, 7, 7], [4, 4, 7, 8], [4, 4, 7, 9], [4, 4, 8, 8], [4, 4, 8, 9], [4, 5, 5, 5], [4, 5, 5, 6], [4, 5, 5, 7], [4, 5, 5, 8], [4, 5, 5, 9], [4, 5, 6, 6], [4, 5, 6, 7], [4, 5, 6, 8], [4, 5, 6, 9], [4, 5, 7, 7], [4, 5, 7, 8], [4, 5, 7, 9], [4, 5, 8, 8], [4, 5, 8, 9], [4, 5, 9, 9], [4, 6, 6, 6], [4, 6, 6, 7], [4, 6, 6, 8], [4, 6, 6, 9], [4, 6, 7, 7], [4, 6, 7, 8], [4, 6, 7, 9], [4, 6, 8, 8], [4, 6, 8, 9], [4, 6, 9, 9], [4, 7, 7, 7], [4, 7, 7, 8], [4, 7, 8, 8], [4, 7, 8, 9], [4, 7, 9, 9], [4, 8, 8, 8], [4, 8, 8, 9], [4, 8, 9, 9], [5, 5, 5, 5], [5, 5, 5, 6], [5, 5, 5, 9], [5, 5, 6, 6], [5, 5, 6, 7], [5, 5, 6, 8], [5, 5, 7, 7], [5, 5, 7, 8], [5, 5, 8, 8], [5, 5, 8, 9], [5, 5, 9, 9], [5, 6, 6, 6], [5, 6, 6, 7], [5, 6, 6, 8], [5, 6, 6, 9], [5, 6, 7, 7], [5, 6, 7, 8], [5, 6, 7, 9], [5, 6, 8, 8], [5, 6, 8, 9], [5, 6, 9, 9], [5, 7, 7, 9], [5, 7, 8, 8], [5, 7, 8, 9], [5, 8, 8, 8], [5, 8, 8, 9], [6, 6, 6, 6], [6, 6, 6, 8], [6, 6, 6, 9], [6, 6, 7, 9], [6, 6, 8, 8], [6, 6, 8, 9], [6, 7, 8, 9], [6, 7, 9, 9], [6, 8, 8, 8], [6, 8, 8, 9], [6, 8, 9, 9], [7, 8, 8, 9]]
游戏的第一步是挑出两个数，算出一个新数替代这两个数。
然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。
然后，在两个数中玩 24 点……
很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：
即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。
当递归返回 true，代表游戏成功，不用继续探索了，剩下的搜索分支全部砍掉。怎么做到？
isValid初始为 false，默认会执行||后面的递归。isValid就变为真，由于||的短路特性，后面的递归不会执行。isValid就像一个开关，避免写很多判断语句。###js
isValid = isValid || judgePoint24([...newNums, n1 + n2]);
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
// ...
const judgePoint24 = (nums) => {
const len = nums.length;
if (len == 1) { // 递归的出口
return Math.abs(nums[0] - 24) < 1e-9;
}
let isValid = false; // 用于控制是否进入递归
for (let i = 0; i < len; i++) { // 两层循环，枚举出所有的两数组合
for (let j = i + 1; j < len; j++) {
const n1 = nums[i];
const n2 = nums[j]; // 选出的两个数 n1 n2
const newNums = []; // 存放剩下的两个数
for (let k = 0; k < len; k++) {
if (k != i && k != j) { // 剔除掉选出的两个数
newNums.push(nums[k]);
}
}
// 加
isValid = isValid || judgePoint24([...newNums, n1 + n2]);
// 减与被减
isValid = isValid || judgePoint24([...newNums, n1 - n2]);
isValid = isValid || judgePoint24([...newNums, n2 - n1]);
// 乘
isValid = isValid || judgePoint24([...newNums, n1 * n2]);
if (n2 !== 0) { // 除
isValid = isValid || judgePoint24([...newNums, n1 / n2]);
}
if (n1 !== 0) { // 被除
isValid = isValid || judgePoint24([...newNums, n2 / n1]);
}
if (isValid) {
return true;
}
}
}
return false; // 遍历结束，始终没有返回真，则返回false
};
func judgePoint24(nums []int) bool {
floatNums := make([]float64, len(nums))
for i := range floatNums {
floatNums[i] = float64(nums[i])
}
return dfs(floatNums)
}
func dfs(nums []float64) bool {
if len(nums) == 1 {
return math.Abs(nums[0]-24) < 1e-9
}
flag := false
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
n1, n2 := nums[i], nums[j]
newNums := make([]float64, 0, len(nums))
for k := 0; k < len(nums); k++ {
if k != i && k != j {
newNums = append(newNums, nums[k])
}
}
flag = flag || dfs(append(newNums, n1+n2))
flag = flag || dfs(append(newNums, n1-n2))
flag = flag || dfs(append(newNums, n2-n1))
flag = flag || dfs(append(newNums, n1*n2))
if n1 != 0 {
flag = flag || dfs(append(newNums, n2/n1))
}
if n2 != 0 {
flag = flag || dfs(append(newNums, n1/n2))
}
if flag {
return true
}
}
}
return false
}
Runtime: 68 ms, faster than 100.00% of JavaScript online submissions for 24 Game.
Runtime: 0 ms, faster than 100.00% of Go online submissions for 24 Game.
最后修改于：2022-01-10
一共有 $4$ 个数和 $3$ 个运算操作，因此可能性非常有限。一共有多少种可能性呢？
首先从 $4$ 个数字中有序地选出 $2$ 个数字，共有 $4 \times 3=12$ 种选法，并选择加、减、乘、除 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $3$ 个数字。
然后在剩下的 $3$ 个数字中有序地选出 $2$ 个数字，共有 $3 \times 2=6$ 种选法，并选择 $4$ 种运算操作之一，用得到的结果取代选出的 $2$ 个数字，剩下 $2$ 个数字。
最后剩下 $2$ 个数字，有 $2$ 种不同的顺序，并选择 $4$ 种运算操作之一。
因此，一共有 $12 \times 4 \times 6 \times 4 \times 2 \times 4=9216$ 种不同的可能性。
可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 $2$ 个数字，再选择一种运算操作，用计算得到的结果取代选出的 $2$ 个数字，这样列表中的数字就减少了 $1$ 个。重复上述步骤，直到列表中只剩下 $1$ 个数字，这个数字就是一种可能性的结果，如果结果等于 $24$，则说明可以通过运算得到 $24$。如果所有的可能性的结果都不等于 $24$，则说明无法通过运算得到 $24$。
实现时，有一些细节需要注意。
除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 $24$ 时应考虑精度误差，这道题中，误差小于 $10^{-6}$ 可以认为是相等。
进行除法运算时，除数不能为 $0$，如果遇到除数为 $0$ 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 $0$ 时应考虑精度误差，这道题中，当一个数字的绝对值小于 $10^{-6}$ 时，可以认为该数字等于 $0$。
还有一个可以优化的点。
###Java
class Solution {
static final int TARGET = 24;
static final double EPSILON = 1e-6;
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return solve(list);
}
public boolean solve(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - TARGET) < EPSILON;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) {
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) {
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) {
if (Math.abs(list.get(j)) < EPSILON) {
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (solve(list2)) {
return true;
}
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}
###C++
class Solution {
public:
static constexpr int TARGET = 24;
static constexpr double EPSILON = 1e-6;
static constexpr int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool judgePoint24(vector<int> &nums) {
vector<double> l;
for (const int &num : nums) {
l.emplace_back(static_cast<double>(num));
}
return solve(l);
}
bool solve(vector<double> &l) {
if (l.size() == 0) {
return false;
}
if (l.size() == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
vector<double> list2 = vector<double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2.emplace_back(l[k]);
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2.emplace_back(l[i] + l[j]);
} else if (k == MULTIPLY) {
list2.emplace_back(l[i] * l[j]);
} else if (k == SUBTRACT) {
list2.emplace_back(l[i] - l[j]);
} else if (k == DIVIDE) {
if (fabs(l[j]) < EPSILON) {
continue;
}
list2.emplace_back(l[i] / l[j]);
}
if (solve(list2)) {
return true;
}
list2.pop_back();
}
}
}
}
return false;
}
};
###C
const int TARGET = 24;
const double EPSILON = 1e-6;
const int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
bool solve(double *l, int l_len) {
if (l_len == 0) {
return false;
}
if (l_len == 1) {
return fabs(l[0] - TARGET) < EPSILON;
}
int size = l_len;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) {
double list2[20];
int l2_len = 0;
for (int k = 0; k < size; k++) {
if (k != i && k != j) {
list2[l2_len++] = l[k];
}
}
for (int k = 0; k < 4; k++) {
if (k < 2 && i > j) {
continue;
}
if (k == ADD) {
list2[l2_len++] = l[i] + l[j];
} else if (k == MULTIPLY) {
list2[l2_len++] = l[i] * l[j];
} else if (k == SUBTRACT) {
list2[l2_len++] = l[i] - l[j];
} else if (k == DIVIDE) {
if (fabs(l[j]) < EPSILON) {
continue;
}
list2[l2_len++] = l[i] / l[j];
}
if (solve(list2, l2_len)) {
return true;
}
l2_len--;
}
}
}
}
return false;
}
bool judgePoint24(int *nums, int numsSize) {
double l[20];
int l_len = 0;
for (int i = 0; i < numsSize; i++) {
l[l_len++] = nums[i];
}
return solve(l, l_len);
}
###Python
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
def solve(nums: List[float]) -> bool:
if not nums:
return False
if len(nums) == 1:
return abs(nums[0] - TARGET) < EPSILON
for i, x in enumerate(nums):
for j, y in enumerate(nums):
if i != j:
newNums = list()
for k, z in enumerate(nums):
if k != i and k != j:
newNums.append(z)
for k in range(4):
if k < 2 and i > j:
continue
if k == ADD:
newNums.append(x + y)
elif k == MULTIPLY:
newNums.append(x * y)
elif k == SUBTRACT:
newNums.append(x - y)
elif k == DIVIDE:
if abs(y) < EPSILON:
continue
newNums.append(x / y)
if solve(newNums):
return True
newNums.pop()
return False
return solve(nums)
###golang
const (
TARGET = 24
EPSILON = 1e-6
ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3
)
func judgePoint24(nums []int) bool {
list := []float64{}
for _, num := range nums {
list = append(list, float64(num))
}
return solve(list)
}
func solve(list []float64) bool {
if len(list) == 0 {
return false
}
if len(list) == 1 {
return abs(list[0] - TARGET) < EPSILON
}
size := len(list)
for i := 0; i < size; i++ {
for j := 0; j < size; j++ {
if i != j {
list2 := []float64{}
for k := 0; k < size; k++ {
if k != i && k != j {
list2 = append(list2, list[k])
}
}
for k := 0; k < 4; k++ {
if k < 2 && i < j {
continue
}
switch k {
case ADD:
list2 = append(list2, list[i] + list[j])
case MULTIPLY:
list2 = append(list2, list[i] * list[j])
case SUBTRACT:
list2 = append(list2, list[i] - list[j])
case DIVIDE:
if abs(list[j]) < EPSILON {
continue
} else {
list2 = append(list2, list[i] / list[j])
}
}
if solve(list2) {
return true
}
list2 = list2[:len(list2) - 1]
}
}
}
}
return false
}
func abs(x float64) float64 {
if x < 0 {
return -x
}
return x
}
复杂度分析
时间复杂度：$O(1)$。一共有 $9216$ 种可能性，对于每种可能性，各项操作的时间复杂度都是 $O(1)$，因此总时间复杂度是 $O(1)$。
空间复杂度：$O(1)$。空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 $4$ 个数，所以递归调用的层数最多为 $4$，存储中间状态的列表最多包含 $4$ 个元素，因此空间复杂度为常数。
我们要解决的问题（原问题）是：
用「枚举选哪个」思考，即枚举我们获得多少分：
这些问题都是和原问题相似的、规模更小的子问题。
根据上面的讨论，定义 $f[i]$ 表示从 $i$ 分开始游戏，最终到达闭区间 $[k,n]$ 的概率。
在当前回合，我们等概率地发生以下 $\textit{\textit{maxPts}}$ 种事件：
由于上述 $\textit{\textit{maxPts}}$ 种事件互斥且等概率地被选择，因此最终到达闭区间 $[k,n]$ 的概率为上述 $\textit{\textit{maxPts}}$ 个状态值的平均值，即
$$
f[i] = \dfrac{f[i+1] + f[i+2] + f[i+3] + \dots + f[i+\textit{maxPts}]}{\textit{maxPts}}
$$
由于转移来源比 $i$ 大，所以要倒序枚举 $i$。
由于转移方程中的分子是一个长度固定为 $\textit{maxPts}$ 的连续子数组的元素和，所以可以用定长滑动窗口 $\mathcal{O}(1)$ 计算，原理讲解请看【套路】教你解决定长滑窗！适用于所有定长滑窗题目！
初始值：
答案：$f[0]$，即原问题。
问：为什么滑动窗口的计算顺序不是「入-计算-出」，而是「计算-入-出」？
答：当我们遍历到 $i$ 时，窗口的左端点是 $i+1$ 而不是 $i$。所以 $f[i]$ 并不在窗口中，得先把 $f[i]$ 计算出来，然后下个循环 $f[i]$ 才在窗口中。
注：$n$ 可以与 $k+\textit{maxPts}$ 取 $\min$，但测试发现这个优化不显著。
###py
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
f = [0.0] * (n + 1)
s = 0.0
for i in range(n, -1, -1):
f[i] = 1.0 if i >= k else s / maxPts
# 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
# 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i + maxPts <= n:
s -= f[i + maxPts]
return f[0]
###java
class Solution {
public double new21Game(int n, int k, int maxPts) {
double[] f = new double[n + 1];
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
}
}
###cpp
class Solution {
public:
double new21Game(int n, int k, int maxPts) {
vector<double> f(n + 1);
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
}
};
###c
double new21Game(int n, int k, int maxPts) {
double* f = malloc((n + 1) * sizeof(double));
double s = 0;
for (int i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
double ans = f[0];
free(f);
return ans;
}
###go
func new21Game(n, k, maxPts int) float64 {
f := make([]float64, n+1)
s := 0.0
for i := n; i >= 0; i-- {
if i >= k {
f[i] = 1 // 初始值
} else {
f[i] = s / float64(maxPts)
}
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i]
if i+maxPts <= n {
s -= f[i+maxPts]
}
}
return f[0]
}
###js
var new21Game = function(n, k, maxPts) {
const f = new Array(n + 1).fill(0);
let s = 0;
for (let i = n; i >= 0; i--) {
f[i] = i >= k ? 1 : s / maxPts;
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if (i + maxPts <= n) {
s -= f[i + maxPts];
}
}
return f[0];
};
###rust
impl Solution {
pub fn new21_game(n: i32, k: i32, max_pts: i32) -> f64 {
let n = n as usize;
let k = k as usize;
let max_pts = max_pts as usize;
let mut f = vec![0.0; n + 1];
let mut s = 0.0;
for i in (0..=n).rev() {
f[i] = if i >= k { 1.0 } else { s / max_pts as f64 };
// 当前循环计算的是 f[i+1] + ... + f[i+maxPts]
// 下个循环计算的是 f[i] + ... + f[i+maxPts-1]，多了 f[i]，少了 f[i+maxPts]
s += f[i];
if i + max_pts <= n {
s -= f[i + max_pts];
}
}
f[0]
}
}
见下面动态规划题单的「十五、概率/期望 DP」和「§11.1 前缀和优化 DP」。
爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。 抽取时，她从 [1, maxPts] 的范围中随机获得一个整数作为分数进行累计，其中 maxPts 是一个整数。 每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得 k 分 或更多分 时，她就停止抽取数字。
爱丽丝的分数不超过 n 的概率是多少？
与实际答案误差不超过 10-5 的答案将被视为正确答案。
示例 1：
输入：n = 10, k = 1, maxPts = 10 输出：1.00000 解释：爱丽丝得到一张牌，然后停止。
示例 2：
输入：n = 6, k = 1, maxPts = 10 输出：0.60000 解释：爱丽丝得到一张牌，然后停止。 在 10 种可能性中的 6 种情况下，她的得分不超过 6 分。
示例 3：
输入：n = 21, k = 17, maxPts = 10 输出：0.73278
提示：
0 <= k <= n <= 1041 <= maxPts <= 104老实说，一开始没懂题目意思，后面才知道是求爱丽丝的胜率。
规则是这样：
[1,W] 的牌中选择任意一张，这张牌是可以无限重复的，也就是说无论她取多少次，每次取到 2（假如 2 在 [1,W] 范围内）的概率都是 1/W;K，她就会抽牌，大于等于 K 时，就停止抽牌;N 时，她就获胜了，求她获胜的概率。假设 dp[x] 为她手上牌面为x时，能获胜的概率，那么这个概率应该是：dp[x]=1/w * (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+w])
因为抽取的牌面机会都是均等的，她能抽取的面值在 [1,W] 之间，所以将概率之和平均一下就是 dp[x] 的概率。
强插一段解释：
x代表爱丽丝手上的牌面值，dp[x]代表爱丽丝手上持有的牌面值为x时，她获胜的概率（游戏结束时她所持牌面值小于等于N的概率）。
这个概率是怎么来的？x分2种情况:
- 当x>=K时，爱丽丝会停止抽牌，这个时候游戏已经结束了，她是赢是输也已经确定了，所以此时赢的概率要么1，要么0
- 当x<K时，爱丽丝会继续抽牌，抽牌是有概率的，所以她是赢是输也有概率。
她能抽到的牌面值在[1,W]之间，所以抽完后她的牌面在[x+1,x+w]之间，因为每张牌机率均等，所以抽完后牌面在[x+1,x+w]之间的每个面值概率都是相等的，而假如我们已知当牌面是[x+1,x+w]的胜率(即dp[x+1]...dp[x+w]的值)，那么可以推导：dp[x]=1/w * dp[x+1]+ 1/w * dp[x+2] + 1/w * dp[x+3]...+ 1/w * dp[x+w]
这个实际上就是动态规划的状态转移方程，不过本例是反着来转移的。
x 最多能到 K-1，因为当大于等于 K 时，爱丽丝会停止抽牌，所以当游戏结束时，即爱丽丝停止抽牌时，她可能达到的最大牌面是 K+W-1，而一开始她的牌面是 0，所以我们用一个长度为 K+W 的 dp 数组来保存她在所有面值下的胜率。
最后 dp[0]，也就是最开始爱丽丝还没有抽牌，她的牌面为 0 时的胜率，这个就是我们的答案。
我将这个格子分成了 2 部分 [0,K-1] 和 [K,K+W-1]，区别就是 [0,K-1] 爱丽丝可以抽牌，[K,K+W-1] 时不能抽牌，那么不能抽牌时她获胜的概率是多少呢，此时已不能抽牌，要么赢要么输，很显然牌面小于等于N时，概率就是 1，大于 N 概率就是 0，所以先直接填满图中蓝色的格子。
接下来，从 K-1 开始填图中的橘色部分，这个值根据我们前面提到的计算方式，实际上就相当于它后面 W 个格子的总和除以 W，
这时聪明的你一定会想到不用每轮都累加的方法吧，用一个 s 变量来保存累加结果，而下一轮只是减去右边的格子，加上左边的格子即可。
所以这题你要做的就是，先初始化蓝色格子，然后从最右边的橘色格子开始，填到最左边的格子，就是这么简单，不仅简单，而且你连动态规划的思想都学会了。
相信这么厉害的你，看到这里给我点个赞一定不是件很困难的事吧。
###Python3
class Solution:
def new21Game(self, N: int, K: int, W: int) -> float:
dp=[None]*(K+W)
s=0
for i in range(K,K+W): # 填蓝色的格子
dp[i] = 1 if i<=N else 0
s+=dp[i]
for i in range(K-1,-1,-1): # 填橘黄色格子
dp[i]=s/W
s=s-dp[i+W]+dp[i]
return dp[0]
时间复杂度=格子长度 $O(K+W)$
空间复杂度=格子长度 $O(K+W)$
按照官方题解的说明，$dp[x]$ 表示从得分为$x$的情况开始游戏并且获胜的概率，如果我们引入 $x_t=x$ 表示$t$ 时刻的总分是 $x$，那么 $dp[x]$ 用条件概率可以写作
$$
dp[x] = P(win | x_t = x)
$$
我们怎么利用这个条件概率来得到题解中的状态转移方程呢？从条件概率可以联想到全概率公式。拿总分 $x=K - 1$ 为例，
$$
dp[K - 1] = P(win | x_t = K - 1) \
= \sum_{i=1}^{W} P(win | x_{t+1} = K - 1 + i) P(x_{t + 1} = K - 1 + i | x_t = K - 1)
$$
其中，$P(x_{t + 1} = K - 1 + i | x_t = K - 1)$ 表示，在 $t$ 时刻，一次抽取后，总分从 $K - 1$ 变成 $K - 1 + i$ 的概率，这实际上就是当前抽到数字 $i$ 的概率，根据题目
抽取时，她从
[1, W]的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率
我们知道在任意时刻抽取得到 ${1, 2, .., W}$ 的概率相同（抽取的数字服从离散型均匀分布），即
$$
P(x_{t + 1} = K - 1 + i | x_t = K - 1) = P(\Delta x_t = i) = \frac{1}{W}
$$
另外，$P(win | x_{t+1} = K - 1 + i) = dp[K - 1 + i]$，我们就得到了官方题解里的状态转移方程
$$
dp[K - 1] = P(win | x_t = K - 1) \
= \sum_{i=1}^{W} P(x_{t + 1} = K - 1 + i | x_t = K - 1) P(win | x_{t+1} = K - 1 + i) \
= \sum_{i=1}^{W} \frac{1}{W} \cdot dp[K - 1 + i]\
= \frac{dp[K] + dp[K + 1] + ... + dp[K - 1 + W]}{W}
$$
我们定义的$t$时刻总分$x_t$其实是一个马尔科夫链
题目中，抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率的条件对玩家每一次抽取到数字的分布做出了假设，即假设 “无论玩家当前总分是多少，玩家抽到任意数字的概率都相等”，用转移概率表示就是 $P(x_{t + 1} = x + i | x_t = x) = \frac{1}{W}$，其中 $i \in {1,2,..,W}$，考虑以下两种情况
第一种情况和原题类似，同属于齐次马尔可夫链（即转移概率不随时间变化而变化），第二种情况属于非齐次马尔科夫链，求解更加复杂。
如果我们把上面 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率 的条件改为 抽取时，她从 [0, 1] 两个数字中抽取W次，以W次抽取结果的和作为分数进行累计，其中 W 是整数，那么每一次增加的分数将服从$n=M$, $p=0.5$的二项分布，状态转移方程也将随之改变为
$$
dp[K - 1]
= \sum_{i=0}^{W} C^{i}_{W} (\frac{1}{2})^{W-i} (\frac{1}{2})^{i} \cdot dp[K - 1 + i]\
= \frac{dp[K - 1] + W \cdot dp[K] + \frac{W(W-1)}{2} \cdot dp[K + 1] + ... + dp[K - 1 + W]}{2^W}
$$
爱丽丝获胜的概率只和下一轮开始前的得分有关，因此根据得分计算概率。
令 $\textit{dp}[x]$ 表示从得分为 $x$ 的情况开始游戏并且获胜的概率，目标是求 $\textit{dp}[0]$ 的值。
根据规则，当分数达到或超过 $k$ 时游戏结束，游戏结束时，如果分数不超过 $n$ 则获胜，如果分数超过 $n$ 则失败。因此当 $k \le x \le \min(n, k+\textit{maxPts}-1)$ 时有 $\textit{dp}[x]=1$，当 $x>\min(n, k+\textit{maxPts}-1)$ 时有 $\textit{dp}[x]=0$。
为什么分界线是 $\min(n, k+\textit{maxPts}-1)$？首先，只有在分数不超过 $n$ 时才算获胜；其次，可以达到的最大分数为 $k+\textit{maxPts}-1$，即在最后一次抽取数字之前的分数为 $k-1$，并且抽到了 $\textit{maxPts}$。
当 $0 \le x < k$ 时，如何计算 $\textit{dp}[x]$ 的值？注意到每次在范围 $[1, \textit{maxPts}]$ 内随机抽取一个整数，且每个整数被抽取到的概率相等，因此可以得到如下状态转移方程：
$$
\textit{dp}[x]=\frac{\sum_{i=1}^\textit{maxPts} \textit{dp}[x+i]}{\textit{maxPts}}
$$
根据状态转移方程，可以实现如下简单的动态规划：
###Java
class Solution {
public double new21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
double[] dp = new double[k + maxPts];
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
for (int i = k - 1; i >= 0; i--) {
for (int j = 1; j <= maxPts; j++) {
dp[i] += dp[i + j] / maxPts;
}
}
return dp[0];
}
}
###C#
public class Solution {
public double New21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
double[] dp = new double[k + maxPts];
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
for (int i = k - 1; i >= 0; i--) {
for (int j = 1; j <= maxPts; j++) {
dp[i] += dp[i + j] / maxPts;
}
}
return dp[0];
}
}
###C++
class Solution {
public:
double new21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
vector<double> dp(k + maxPts);
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
for (int i = k - 1; i >= 0; i--) {
for (int j = 1; j <= maxPts; j++) {
dp[i] += dp[i + j] / maxPts;
}
}
return dp[0];
}
};
###Python
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
if k == 0:
return 1.0
dp = [0.0] * (k + maxPts)
for i in range(k, min(n, k + maxPts - 1) + 1):
dp[i] = 1.0
for i in range(k - 1, -1, -1):
for j in range(1, maxPts + 1):
dp[i] += dp[i + j] / maxPts
return dp[0]
###golang
func new21Game(n int, k int, maxPts int) float64 {
if k == 0 {
return 1.0
}
dp := make([]float64, k + maxPts)
for i := k; i <= n && i < k + maxPts; i++ {
dp[i] = 1.0
}
for i := k - 1; i >= 0; i-- {
for j := 1; j <= maxPts; j++ {
dp[i] += dp[i + j] / float64(maxPts)
}
}
return dp[0]
}
上述解法的时间复杂度是 $O(n+k \times \textit{maxPts})$，会超出时间限制，因此需要优化。
考虑对 $\textit{dp}$ 的相邻项计算差分，有如下结果：
$$
\textit{dp}[x] - \textit{dp}[x+1]=\frac{\textit{dp}[x+1] - \textit{dp}[x+\textit{maxPts}+1]}{\textit{maxPts}}
$$
其中 $0 \le x<k-1$。
因此可以得到新的状态转移方程：
$$
\textit{dp}[x]=\textit{dp}[x+1]-\frac{\textit{dp}[x+\textit{maxPts}+1]-\textit{dp}[x+1]}{\textit{maxPts}}
$$
其中 $0 \le x<k-1$。
注意到上述状态转移方程中 $x$ 的取值范围，当 $x=k-1$ 时不适用。因此对于 $\textit{dp}[k-1]$ 的值，需要通过
$$
\textit{dp}[k-1]=\frac{\sum_{i=0}^{\textit{maxPts}-1} \textit{dp}[k+i]}{\textit{maxPts}}
$$
计算得到。注意到只有当 $k \le x \le \min(n, k+\textit{maxPts}-1)$ 时才有 $\textit{dp}[x]=1$，因此
$$
\textit{dp}[k-1]=\frac{\min(n, k+\textit{maxPts}-1) - k + 1}{\textit{maxPts}} = \frac{\min(n-k+1,\textit{maxPts})}{\textit{maxPts}}
$$
可在 $O(1)$ 时间内计算得到 $\textit{dp}[k-1]$ 的值。
对于 $\textit{dp}[k-2]$ 到 $\textit{dp}[0]$ 的值，则可通过新的状态转移方程得到。
###Java
class Solution {
public double new21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
double[] dp = new double[k + maxPts];
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
dp[k - 1] = 1.0 * Math.min(n - k + 1, maxPts) / maxPts;
for (int i = k - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
}
return dp[0];
}
}
###C#
public class Solution {
public double New21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
double[] dp = new double[k + maxPts];
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
dp[k - 1] = 1.0 * Math.Min(n - k + 1, maxPts) / maxPts;
for (int i = k - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
}
return dp[0];
}
}
###C++
class Solution {
public:
double new21Game(int n, int k, int maxPts) {
if (k == 0) {
return 1.0;
}
vector<double> dp(k + maxPts);
for (int i = k; i <= n && i < k + maxPts; i++) {
dp[i] = 1.0;
}
dp[k - 1] = 1.0 * min(n - k + 1, maxPts) / maxPts;
for (int i = k - 2; i >= 0; i--) {
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts;
}
return dp[0];
}
};
###Python
class Solution:
def new21Game(self, n: int, k: int, maxPts: int) -> float:
if k == 0:
return 1.0
dp = [0.0] * (k + maxPts)
for i in range(k, min(n, k + maxPts - 1) + 1):
dp[i] = 1.0
dp[k - 1] = float(min(n - k + 1, maxPts)) / maxPts
for i in range(k - 2, -1, -1):
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / maxPts
return dp[0]
###golang
func new21Game(n int, k int, maxPts int) float64 {
if k == 0 {
return 1.0
}
dp := make([]float64, k + maxPts)
for i := k; i <= n && i < k + maxPts; i++ {
dp[i] = 1.0
}
dp[k - 1] = 1.0 * float64(min(n - k + 1, maxPts)) / float64(maxPts)
for i := k - 2; i >= 0; i-- {
dp[i] = dp[i + 1] - (dp[i + maxPts + 1] - dp[i + 1]) / float64(maxPts)
}
return dp[0]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
复杂度分析
时间复杂度：$O(\min(n, k+\textit{maxPts}))$。即需要计算的 $\textit{dp}$ 值的数量 $\min(n, k+\textit{maxPts}-1)$。
空间复杂度：$O(k+\textit{maxPts})$。创建了一个长度为 $k+\textit{maxPts}$ 的数组 $\textit{dp}$。
给你一个仅由数字 6 和 9 组成的正整数 num。
你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
请返回你可以得到的最大数字。
示例 1：
输入：num = 9669 输出：9969 解释： 改变第一位数字可以得到 6669 。 改变第二位数字可以得到 9969 。 改变第三位数字可以得到 9699 。 改变第四位数字可以得到 9666 。 其中最大的数字是 9969 。
示例 2：
输入：num = 9996 输出：9999 解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。
示例 3：
输入：num = 9999 输出：9999 解释：无需改变就已经是最大的数字了。
提示：
1 <= num <= 10^4num 每一位上的数字都是 6 或者 9 。要想把数字变大，只能把 $6$ 改成 $9$。
比如 $\textit{num}=9669$：
改高位的 $6$ 比改低位的 $6$ 更好。由于至多改一次，所以改最高位的 $6$。若 $\textit{num}$ 无 $6$，则 $\textit{num}$ 不变。
###py
class Solution:
def maximum69Number(self, num: int) -> int:
s = str(num).replace('6', '9', 1) # 替换第一个 6
return int(s)
###py
class Solution:
def maximum69Number(self, num: int) -> int:
s = str(num)
i = s.find('6')
if i < 0:
return num
return int(s[:i] + '9' + s[i + 1:])
###java
class Solution {
public int maximum69Number(int num) {
String s = String.valueOf(num).replaceFirst("6", "9"); // 替换第一个 6
return Integer.parseInt(s);
}
}
###java
class Solution {
public int maximum69Number(int num) {
String s = Integer.toString(num);
int i = s.indexOf('6');
if (i < 0) {
return num;
}
s = s.substring(0, i) + "9" + s.substring(i + 1);
return Integer.parseInt(s);
}
}
###cpp
class Solution {
public:
int maximum69Number(int num) {
string s = to_string(num);
int i = s.find('6');
if (i == string::npos) {
return num;
}
s[i] = '9';
return stoi(s);
}
};
###c
int maximum69Number(int num) {
char s[6];
sprintf(s, "%d", num);
char* p = strchr(s, '6');
if (p == NULL) {
return num;
}
*p = '9';
return atoi(s);
}
###go
func maximum69Number(num int) int {
s := strconv.Itoa(num)
s = strings.Replace(s, "6", "9", 1) // 替换第一个 6
ans, _ := strconv.Atoi(s)
return ans
}
###js
var maximum69Number = function(num) {
const s = String(num).replace('6', '9'); // 替换第一个 6
return parseInt(s);
};
###rust
impl Solution {
pub fn maximum69_number(num: i32) -> i32 {
num.to_string()
.replacen("6", "9", 1) // 替换第一个 6
.parse()
.unwrap()
}
}
可以不用转成字符串处理，而是不断取最低位（模 $10$），去掉最低位（除以 $10$），直到数字为 $0$。
例如 $\textit{num}=9669$：
在这个过程中，维护一个变量 $\textit{base}$，初始值为 $1$，在循环末尾把 $\textit{base}$ 乘以 $10$。每当我们遍历到一个等于 $6$ 的数位，就保存此刻的 $\textit{base}$，即更新 $\textit{maxBase} = \textit{base}$。其中 $\textit{maxBase}$ 初始值为 $0$。由于我们从低位往高位遍历，所以最终的 $\textit{maxBase}$ 就是最高位的 $6$ 对应的 $\textit{base}$。在上面的例子中，我们可以得到 $\textit{maxBase} = 100$。
最终答案为
$$
\textit{num} + \textit{maxBase}\cdot 3
$$
在上面的例子中，答案为 $9669 + 100\cdot 3 = 9969$。
注：如果 $\textit{num}$ 中没有 $6$，由于我们初始化 $\textit{maxBase}=0$，最终答案为 $\textit{num}$。
###py
class Solution:
def maximum69Number(self, num: int) -> int:
max_base = 0
base = 1
x = num
while x:
x, d = divmod(x, 10)
if d == 6:
max_base = base
base *= 10
return num + max_base * 3
###java
class Solution {
public int maximum69Number(int num) {
int maxBase = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
maxBase = base;
}
base *= 10;
}
return num + maxBase * 3;
}
}
###cpp
class Solution {
public:
int maximum69Number(int num) {
int max_base = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
max_base = base;
}
base *= 10;
}
return num + max_base * 3;
}
};
###c
int maximum69Number(int num) {
int max_base = 0;
int base = 1;
for (int x = num; x > 0; x /= 10) {
if (x % 10 == 6) {
max_base = base;
}
base *= 10;
}
return num + max_base * 3;
}
###go
func maximum69Number(num int) int {
maxBase := 0
base := 1
for x := num; x > 0; x /= 10 {
if x%10 == 6 {
maxBase = base
}
base *= 10
}
return num + maxBase*3
}
###js
var maximum69Number = function(num) {
let maxBase = 0;
let base = 1;
for (let x = num; x > 0; x = Math.floor(x / 10)) {
if (x % 10 === 6) {
maxBase = base;
}
base *= 10;
}
return num + maxBase * 3;
};
###rust
impl Solution {
pub fn maximum69_number(num: i32) -> i32 {
let mut max_base = 0;
let mut base = 1;
let mut x = num;
while x > 0 {
if x % 10 == 6 {
max_base = base;
}
base *= 10;
x /= 10;
}
num + max_base * 3
}
}
欢迎在评论区分享你的思路/代码。
见下面贪心题单的「§3.1 字典序最小/最大」。
欢迎关注 B站@灵茶山艾府
