给你一个二进制字符串 s。
请你统计并返回其中 1 显著 的 子字符串 的数量。
如果字符串中 1 的数量 大于或等于 0 的数量的 平方，则认为该字符串是一个 1 显著 的字符串 。
示例 1：
输入：s = "00011"
输出：5
解释：
1 显著的子字符串如下表所示。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 3 | 3 | 1 | 0 | 1 |
| 4 | 4 | 1 | 0 | 1 |
| 2 | 3 | 01 | 1 | 1 |
| 3 | 4 | 11 | 0 | 2 |
| 2 | 4 | 011 | 1 | 2 |
示例 2：
输入：s = "101101"
输出：16
解释：
1 不显著的子字符串如下表所示。
总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。
| i | j | s[i..j] | 0 的数量 | 1 的数量 |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 |
| 4 | 4 | 0 | 1 | 0 |
| 1 | 4 | 0110 | 2 | 2 |
| 0 | 4 | 10110 | 2 | 3 |
| 1 | 5 | 01101 | 2 | 3 |
提示：
登录
1 <= s.length <= 4 * 104s 仅包含字符 '0' 和 '1'。Problem: 100348. 统计 1 显著的字符串的数量
[TOC]
暴力法，逐个判断，用python3肯定过不了，python3实现虽比C++大5-10倍，但python3循环太慢了……
所以我用了C++暴力这道题，871 / 881。
据说Java时限更长，也不太慢，所以我也试了一下，872 / 881。
C++为什么通不过呢？因为时限太短，而且leetcode貌似开了一些检测，慢的出奇。
Java和C++都不行，上numpy，不通过，878 / 881。
所以再引入一个优化，所有0的数量的平方小于等于开头的0的数量，则跳过，通过了，速度甚至接近$O(n\sqrt{n})$的算法。
Wa了三发，终于通过该题。
###python3
from numpy import *
class Solution:
def numberOfSubstrings(self, s: str) -> int:
lz, lo = list(accumulate([i == "0" for i in s])), list(accumulate([i == "1" for i in s]))
z, o = array(lz, int_), array(lo, int_)
n = len(s)
res = 0
for i in range(n):
if (z[-1]-(0 if i == 0 else lz[i-1]))**2 <= o[i]-(0 if i == 0 else lo[i-1]):
res += n-i
else:
a = z[i:]-(0 if i == 0 else lz[i-1])
b = o[i:]-(0 if i == 0 else lo[i-1])
res += sum(a*a <= b)
return int(res)
###C++
template<typename T>
T::value_type* change(T p){
using V = T::value_type;
V *s = new V[p.size()];
copy(p.begin(), p.end(), s);
return s;
}
class Solution {
public:
int numberOfSubstrings(string t) {
int n = t.size();
char *s = change(t);
int res = 0;
for (int i = 0; i < n; ++i){
int z = 0, o = 0;
for (int j = i; j < n; ++j){
if (s[j] == '0') ++z;
else ++o;
res += z*z <= o;
}
}
return res;
}
};
###Java
class Solution {
public int numberOfSubstrings(String t) {
char s[] = t.toCharArray();
int res = 0;
for (int i = 0; i < s.length; ++i){
int z = 0, o = 0;
for (int j = i; j < s.length; ++j){
if (s[j] == '0') ++z;
else ++o;
res += (z*z <= o?1:0);
}
}
return res;
}
}
###python3
from numpy import *
class Solution:
def numberOfSubstrings(self, s: str) -> int:
z, o = array(list(accumulate([i == "0" for i in s])), int_), array(list(accumulate([i == "1" for i in s])), int_)
n = len(s)
res = 0
for i in range(n):
a = z[i:]-(0 if i == 0 else z[i-1])
b = o[i:]-(0 if i == 0 else o[i-1])
res += sum(a*a <= b)
return int(res)
设 $\textit{cnt}_0$ 为子串中的 $0$ 的个数，$\textit{cnt}_1$ 为子串中的 $1$ 的个数。
根据题意，$1$ 显著子串必须满足
$$
0\le \textit{cnt}_0^2 \le \textit{cnt}_1 \le n
$$
解得
$$
0\le \textit{cnt}_0 \le \sqrt{n}
$$
所以 $1$ 显著子串至多有 $\lfloor \sqrt{n}\rfloor$ 个 $0$。本题 $\lfloor \sqrt{n}\rfloor\le 200$。
枚举子串右端点，分别计算：
记录 $s$ 中的 $0$ 的下标，方便计算子串个数。
设子串右端点为 $r$。
设上一个 $0$ 的下标为 $i$。
那么右端点固定为 $r$ 的子串 $[i+1,r],[i+2,r],\ldots,[r,r]$ 都是不包含 $0$ 的，一定是 $1$ 显著子串，这有 $r-i$ 个。
设上上一个 $0$ 的下标为 $j$。
那么子串 $[j+1,r],[j+2,r],\ldots,[i,r]$ 都恰好有 $1$ 个 $0$。
这意味着我们还要考虑子串是否有足够的 $1$。
下面考虑更一般的情况。
{:width=600px}
上图用红线/蓝线标记的子串，右端点相同，左端点不同，都恰好有 $2$ 个 $0$。
子串 $1$ 的个数必须 $\ge$ 子串 $0$ 的个数的平方，也就是至少有 $2^2=4$ 个 $1$。上图中的红色子串不满足要求，蓝色子串满足要求。
在包含的 $0$ 的个数不变的前提下，子串左端点越小，$1$ 的个数越多，越满足要求；子串左端点越大，$1$ 的个数越少，越不满足要求。
算出刚好满足要求的那个蓝色子串的左端点（即左端点的最大值），以及更左边的 $0$ 的位置（图中的 $p$，加一得到左端点的最小值），就能算出蓝色子串的个数。
一般地，外层循环枚举子串右端点 $r=0,1,2,\ldots,n-1$，内层循环枚举子串恰好有 $\textit{cnt}_0 = 0,1,2,\ldots$ 个 $0$，如果 $\textit{cnt}_0^2$ 超过了 $[0,r]$ 中的 $1$ 的个数，则跳出枚举 $\textit{cnt}_0$ 的循环。
设当前枚举的 $\textit{cnt}_0$ 对应的左右两个 $0$ 的下标分别为 $p$ 和 $q$。
右端点为 $r$ 且恰好有 $\textit{cnt}_0$ 个 $0$ 的最短子串为 $[q,r]$，设其有 $\textit{cnt}_1$ 个 $1$。
分类讨论：
综合一下，合法左端点最小是 $p+1$，最大是 $q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0)$，所以一共有
$$
q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0) - p
$$
个合法左端点。考虑到上式可能是负数，所以还要再与 $0$ 取最大值，得
$$
\max\left(q - \max(\textit{cnt}_0^2 - \textit{cnt}_1, 0) - p, 0\right)
$$
累加上式，即为答案。
为了知道 $0$ 的下标，我们用一个列表记录遍历到的 $0$ 的下标。
###py
# 手写 max 更快
max = lambda a, b: b if b > a else a
class Solution:
def numberOfSubstrings(self, s: str) -> int:
pos0 = [-1] # 哨兵，方便处理 cnt0 达到最大时的计数
total1 = 0 # [0,r] 中的 1 的个数
ans = 0
for r, ch in enumerate(s):
if ch == '0':
pos0.append(r) # 记录 0 的下标
else:
total1 += 1
ans += r - pos0[-1] # 单独计算不含 0 的子串个数
# 倒着遍历 pos0，就相当于在从小到大枚举 cnt0
for i in range(len(pos0) - 1, 0, -1):
cnt0 = len(pos0) - i
if cnt0 * cnt0 > total1:
break
p, q = pos0[i - 1], pos0[i]
cnt1 = r - q + 1 - cnt0 # [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += max(q - max(cnt0 * cnt0 - cnt1, 0) - p, 0)
return ans
###java
class Solution {
public int numberOfSubstrings(String s) {
int n = s.length();
int[] pos0 = new int[n + 1]; // 0 的下标
pos0[0] = -1; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
int size = 1;
int total1 = 0; // [0,r] 中的 1 的个数
int ans = 0;
for (int r = 0; r < n; r++) {
if (s.charAt(r) == '0') {
pos0[size++] = r; // 记录 0 的下标
} else {
total1++;
ans += r - pos0[size - 1]; // 单独计算不含 0 的子串个数
}
// 倒着遍历 pos0，那么 cnt0 = size - i
for (int i = size - 1; i > 0 && (size - i) * (size - i) <= total1; i--) {
int p = pos0[i - 1];
int q = pos0[i];
int cnt0 = size - i;
int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += Math.max(q - Math.max(cnt0 * cnt0 - cnt1, 0) - p, 0);
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfSubstrings(string s) {
vector<int> pos0 = {-1}; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
int total1 = 0; // [0,r] 中的 1 的个数
int ans = 0;
for (int r = 0; r < s.size(); r++) {
if (s[r] == '0') {
pos0.push_back(r); // 记录 0 的下标
} else {
total1++;
ans += r - pos0.back(); // 单独计算不含 0 的子串个数
}
int m = pos0.size();
// 倒着遍历 pos0，那么 cnt0 = m - i
for (int i = m - 1; i > 0 && (m - i) * (m - i) <= total1; i--) {
int p = pos0[i - 1], q = pos0[i];
int cnt0 = m - i;
int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += max(q - max(cnt0 * cnt0 - cnt1, 0) - p, 0);
}
}
return ans;
}
};
###c
#define MAX(a, b) ((b) > (a) ? (b) : (a))
int numberOfSubstrings(char* s) {
int n = strlen(s);
int* pos0 = malloc((n + 1) * sizeof(int)); // 0 的下标
pos0[0] = -1; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
int size = 1;
int total1 = 0; // [0,r] 中的 1 的个数
int ans = 0;
for (int r = 0; r < n; r++) {
if (s[r] == '0') {
pos0[size++] = r; // 记录 0 的下标
} else {
total1++;
ans += r - pos0[size - 1]; // 单独计算不含 0 的子串个数
}
// 倒着遍历 pos0，那么 cnt0 = size - i
for (int i = size - 1; i > 0 && (size - i) * (size - i) <= total1; i--) {
int p = pos0[i - 1], q = pos0[i];
int cnt0 = size - i;
int cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += MAX(q - MAX(cnt0 * cnt0 - cnt1, 0) - p, 0);
}
}
free(pos0);
return ans;
}
###go
func numberOfSubstrings(s string) (ans int) {
pos0 := []int{-1} // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
total1 := 0 // [0,r] 中的 1 的个数
for r, ch := range s {
if ch == '0' {
pos0 = append(pos0, r) // 记录 0 的下标
} else {
total1++
ans += r - pos0[len(pos0)-1] // 单独计算不含 0 的子串个数
}
m := len(pos0)
// 倒着遍历 pos0，那么 cnt0 = m-i
for i := m - 1; i > 0 && (m-i)*(m-i) <= total1; i-- {
p, q := pos0[i-1], pos0[i]
cnt0 := m - i
cnt1 := r - q + 1 - cnt0 // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += max(q-max(cnt0*cnt0-cnt1, 0)-p, 0)
}
}
return
}
###js
var numberOfSubstrings = function(s) {
const pos0 = [-1]; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
let total1 = 0; // [0,r] 中的 1 的个数
let ans = 0;
for (let r = 0; r < s.length; r++) {
if (s[r] === '0') {
pos0.push(r); // 记录 0 的下标
} else {
total1++;
ans += r - pos0[pos0.length - 1]; // 单独计算不含 0 的子串个数
}
const m = pos0.length;
// 倒着遍历 pos0，那么 cnt0 = m - i
for (let i = m - 1; i > 0 && (m - i) * (m - i) <= total1; i--) {
const p = pos0[i - 1], q = pos0[i];
const cnt0 = m - i;
const cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += Math.max(q - Math.max(cnt0 * cnt0 - cnt1, 0) - p, 0);
}
}
return ans;
};
###rust
impl Solution {
pub fn number_of_substrings(s: String) -> i32 {
let mut pos0 = vec![-1]; // 加个 -1 哨兵，方便处理 cnt0 达到最大时的计数
let mut total1 = 0; // [0,r] 中的 1 的个数
let mut ans = 0;
for (r, ch) in s.bytes().enumerate() {
let r = r as i32;
if ch == b'0' {
pos0.push(r); // 记录 0 的下标
} else {
total1 += 1;
ans += r - pos0.last().unwrap(); // 单独计算不含 0 的子串个数
}
// 倒着遍历 pos0，就相当于在从小到大枚举 cnt0
for i in (1..pos0.len()).rev() {
let cnt0 = (pos0.len() - i) as i32;
if cnt0 * cnt0 > total1 {
break;
}
let p = pos0[i - 1];
let q = pos0[i];
let cnt1 = r - q + 1 - cnt0; // [q,r] 中的 1 的个数 = [q,r] 的长度 - cnt0
ans += 0.max(q - 0.max(cnt0 * cnt0 - cnt1) - p);
}
}
ans
}
}
注：使用队列，只保存 $r$ 及其左侧的 $\mathcal{O}(\sqrt{n})$ 个 $0$ 的下标，可以把空间复杂度优化到 $\mathcal{O}(\sqrt{n})$。
欢迎关注 B站@灵茶山艾府
设字符串长度为 $n$，显著子串里 $0$ 的数量一定不超过 $\sqrt{n}$。
因此枚举子串的开头，并枚举后续的每个 $0$，直到 $0$ 的数量超过 $\sqrt{n}$。设当前枚举的子串开头是 $i$，当前枚举的 $0$ 的下标是 $j$，下一个 $0$ 的下标是 $k$。那么下标范围 $(j, k)$ 的元素就全是 $1$。下标范围 $[j, k)$ 里有哪些可以作为显著子串的右端点呢？
首先我们检查一下子串 $s[i..k - 1]$ 是否显著，只有它显著了，下标范围 $[j, k)$ 里才有可能出现显著子串的右端点。设子串 $s[i..k - 1]$ 中，$1$ 的数量比 $0$ 的数量平方多 $c$ 个，那么我们可以把子串右端点从 $(k - 1)$ 往左移至多 $c$ 步，它还能是显著的。不过需要注意的是，右端点左移不能超过 $j$，所以一共有 $\min(c + 1, k - j)$ 个下标可以作为显著子串的右端点。
将枚举过程中的答案加起来即可。一共有 $n$ 个子串开头，且每个子串开头我们都枚举了 $\sqrt{n}$ 个 $0$，所以整体复杂度 $\mathcal{O}(n\sqrt{n})$。
###cpp
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.size();
// 最多枚举几个 0
int lim = sqrt(n) + 2;
// 计算下一个 0 的位置
int nxt[n + 1];
nxt[n] = n;
for (int i = n - 1; i >= 0; i--) {
nxt[i] = nxt[i + 1];
if (s[i] == '0') nxt[i] = i;
}
long long ans = 0;
// 枚举子串开头
for (int i = 0; i < n; i++) {
// 从左到右枚举子串里的 0，直到数量超出限制
for (int j = i, cnt = (s[i] == '0' ? 1 : 0); j < n && cnt <= lim; j = nxt[j + 1], cnt++) {
// 求出子串里 1 的数量
int one = (nxt[j + 1] - i) - cnt;
// 子串 s[i..nxt[j + 1] - 1] 必须是显著的，这一段里才有可能出现显著子串的右端点
if (one >= 1LL * cnt * cnt) {
// 看看子串右端点最多能左移几步
int t = one - cnt * cnt + 1;
// 和这一段的长度取 min
ans += min(t, nxt[j + 1] - j);
}
}
}
return ans;
}
};
给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。
另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：
(row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。返回执行完所有操作后得到的矩阵 mat 。
示例 1：
输入：n = 3, queries = [[1,1,2,2],[0,0,1,1]] 输出：[[1,1,0],[1,2,1],[0,1,1]] 解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。 - 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 - 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。
示例 2：
输入：n = 2, queries = [[0,0,1,1]] 输出：[[1,1],[1,1]] 解释：上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 - 第一个操作：将矩阵中的每个元素加 1 。
提示：
1 <= n <= 5001 <= queries.length <= 1040 <= row1i <= row2i < n0 <= col1i <= col2i < n这个题可以用标准的二维差分来做：
对所有的查询，首先维护二维差分数组；然后对差分数组求前缀和即为答案。
如果不熟悉二维差分，可以参考我的这篇 题解。下面的说明摘自我之前的题解。
如果将矩阵的第 $(i,j)$ 个单元格中的值增加 $1$，那么，若对矩阵求二维前缀和，那么下图 $(a)$ 中的黄色区域的值都会增加 $1$。
如果要将矩阵中的 任意 矩形区域（如下图中 $(b)$ 的蓝色区域）的值增加 $1$ 呢？只需按照下图 $(c)$ 来修改矩阵即可。修改后，若对矩阵求前缀和，那么，只会有蓝色的区域的值 $+1$，其它区域的值都不变。
###c++
class Solution {
public:
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
vector<vector<int>> diff(n + 1, vector<int>(n + 1, 0));
vector<vector<int>> ret(n, vector<int>(n, 0));
for(const auto& q : queries) {
diff[q[0]][q[1]]++;
diff[q[0]][q[3]+1]--;
diff[q[2]+1][q[1]]--;
diff[q[2]+1][q[3]+1]++;
}
for(int i = 0; i < n; ++i)
for(int j = 1; j < n; ++j) diff[i][j] += diff[i][j-1];
for(int i = 1; i < n; ++i)
for(int j = 0; j < n; ++j) diff[i][j] += diff[i-1][j];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) ret[i][j] = diff[i][j];
return ret;
}
};
根据题意，我们很自然的想到，需要一个支持在二维数组中进行区间更新和单点查询的数据结构。
因此可以使用二维树状数组求解。
注：本题使用二维差分的做法更优，请参考灵神的题解。
P.S. 抱歉之前的描述有误，我用的二维树状数组而不是线段树。
###Python3
#二维树状数组，维护区域和
class SegmentTree2D:
def __init__(self, n, m):
self.n = n
self.m = m
self.tree = [[0] * (m + 1) for _ in range(n + 1)]
def lowbit(self, x):
return x & (-x)
def update(self, x, y, val):
while x <= self.n:
y1 = y
while y1 <= self.m:
self.tree[x][y1] += val
y1 += self.lowbit(y1)
x += self.lowbit(x)
def query(self, x, y):
res = 0
while x > 0:
y1 = y
while y1 > 0:
res += self.tree[x][y1]
y1 -= self.lowbit(y1)
x -= self.lowbit(x)
return res
class Solution:
def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
seg = SegmentTree2D(n, n)
for x1, y1, x2, y2 in queries:
seg.update(x1 + 1, y1 + 1, 1)
seg.update(x2 + 2, y1 + 1, -1)
seg.update(x1 + 1, y2 + 2, -1)
seg.update(x2 + 2, y2 + 2, 1)
res = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
res[i][j] = seg.query(i + 1, j + 1)
return res
###C++
#include<bits/stdc++.h>
using namespace std;
class SegmentTree2D{
public:
int n, m;
vector<vector<int>> tree;
SegmentTree2D(int n, int m): n(n), m(m), tree(n + 1, vector<int>(m + 1, 0)){}
int lowbit(int x){
return x & (-x);
}
void update(int x, int y, int val){
while(x <= n){
int y1 = y;
while(y1 <= m){
tree[x][y1] += val;
y1 += lowbit(y1);
}
x += lowbit(x);
}
}
int query(int x, int y){
int res = 0;
while(x > 0){
int y1 = y;
while(y1 > 0){
res += tree[x][y1];
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return res;
}
};
class Solution {
public:
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
SegmentTree2D seg(n, n);
for(auto& q: queries){
seg.update(q[0] + 1, q[1] + 1, 1);
seg.update(q[2] + 2, q[1] + 1, -1);
seg.update(q[0] + 1, q[3] + 2, -1);
seg.update(q[2] + 2, q[3] + 2, 1);
}
vector<vector<int>> res(n, vector<int>(n, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
res[i][j] = seg.query(i + 1, j + 1);
}
}
return res;
}
};
###C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct SegmentTree2D{
int n, m;
int **tree;
} SegmentTree2D;
int lowbit(int x){
return x & (-x);
}
void update(SegmentTree2D *seg, int x, int y, int val){
while(x <= seg->n){
int y1 = y;
while(y1 <= seg->m){
seg->tree[x][y1] += val;
y1 += lowbit(y1);
}
x += lowbit(x);
}
}
int query(SegmentTree2D *seg, int x, int y){
int res = 0;
while(x > 0){
int y1 = y;
while(y1 > 0){
res += seg->tree[x][y1];
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return res;
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** rangeAddQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize, int** returnColumnSizes){
SegmentTree2D *seg = (SegmentTree2D *)malloc(sizeof(SegmentTree2D));
seg->n = n;
seg->m = n;
seg->tree = (int **)malloc(sizeof(int *) * (n + 1));
for(int i = 0; i <= n; i++){
seg->tree[i] = (int *)malloc(sizeof(int) * (n + 1));
memset(seg->tree[i], 0, sizeof(int) * (n + 1));
}
for(int i = 0; i < queriesSize; i++){
update(seg, queries[i][0] + 1, queries[i][1] + 1, 1);
update(seg, queries[i][2] + 2, queries[i][1] + 1, -1);
update(seg, queries[i][0] + 1, queries[i][3] + 2, -1);
update(seg, queries[i][2] + 2, queries[i][3] + 2, 1);
}
int **res = (int **)malloc(sizeof(int *) * n);
for(int i = 0; i < n; i++){
res[i] = (int *)malloc(sizeof(int) * n);
for(int j = 0; j < n; j++){
res[i][j] = query(seg, i + 1, j + 1);
}
}
*returnSize = n;
*returnColumnSizes = (int *)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++){
(*returnColumnSizes)[i] = n;
}
return res;
}
###Java
//二维树状数组
class SegmentTree2D{
int n, m;
int[][] tree;
public SegmentTree2D(int n, int m){
this.n = n;
this.m = m;
tree = new int[n + 1][m + 1];
}
int lowbit(int x){
return x & (-x);
}
void update(int x, int y, int val){
while(x <= n){
int y1 = y;
while(y1 <= m){
tree[x][y1] += val;
y1 += lowbit(y1);
}
x += lowbit(x);
}
}
int query(int x, int y){
int res = 0;
while(x > 0){
int y1 = y;
while(y1 > 0){
res += tree[x][y1];
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return res;
}
};
class Solution {
public int[][] rangeAddQueries(int n, int[][] queries) {
SegmentTree2D seg = new SegmentTree2D(n, n);
for(int[] q: queries){
seg.update(q[0] + 1, q[1] + 1, 1);
seg.update(q[2] + 2, q[1] + 1, -1);
seg.update(q[0] + 1, q[3] + 2, -1);
seg.update(q[2] + 2, q[3] + 2, 1);
}
int[][] res = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
res[i][j] = seg.query(i + 1, j + 1);
}
}
return res;
}
}
###Javascript
// #二维树状数组，维护区域和
class SegmentTree2D {
constructor(n, m) {
this.n = n;
this.m = m;
this.tree = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
}
lowbit(x) {
return x & (-x);
}
update(x, y, val) {
while (x <= this.n) {
let y1 = y;
while (y1 <= this.m) {
this.tree[x][y1] += val;
y1 += this.lowbit(y1);
}
x += this.lowbit(x);
}
}
query(x, y) {
let res = 0;
while (x > 0) {
let y1 = y;
while (y1 > 0) {
res += this.tree[x][y1];
y1 -= this.lowbit(y1);
}
x -= this.lowbit(x);
}
return res;
}
}
/**
* @param {number} n
* @param {number[][]} queries
* @return {number[][]}
*/
var rangeAddQueries = function(n, queries) {
let seg = new SegmentTree2D(n, n);
for (let [x1, y1, x2, y2] of queries) {
seg.update(x1 + 1, y1 + 1, 1);
seg.update(x2 + 2, y1 + 1, -1);
seg.update(x1 + 1, y2 + 2, -1);
seg.update(x2 + 2, y2 + 2, 1);
}
let res = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
res[i][j] = seg.query(i + 1, j + 1);
}
}
return res;
};
###Go
package main
type SegmentTree2D struct {
n, m int
tree [][]int
}
func lowbit(x int) int {
return x & (-x)
}
func update(seg *SegmentTree2D, x, y, val int) {
for x <= seg.n {
y1 := y
for y1 <= seg.m {
seg.tree[x][y1] += val
y1 += lowbit(y1)
}
x += lowbit(x)
}
}
func query(seg *SegmentTree2D, x, y int) int {
res := 0
for x > 0 {
y1 := y
for y1 > 0 {
res += seg.tree[x][y1]
y1 -= lowbit(y1)
}
x -= lowbit(x)
}
return res
}
func rangeAddQueries(n int, queries [][]int) [][]int {
seg := &SegmentTree2D{
n: n,
m: n,
tree: make([][]int, n+1),
}
for i := 0; i <= n; i++ {
seg.tree[i] = make([]int, n+1)
}
for _, query := range queries {
update(seg, query[0]+1, query[1]+1, 1)
update(seg, query[2]+2, query[1]+1, -1)
update(seg, query[0]+1, query[3]+2, -1)
update(seg, query[2]+2, query[3]+2, 1)
}
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
for j := 0; j < n; j++ {
res[i][j] = query(seg, i+1, j+1)
}
}
return res
}
###Rust
use std::cmp::min;
struct SegmentTree2D {
n: usize,
m: usize,
tree: Vec<Vec<i32>>,
}
impl SegmentTree2D {
fn new(n: usize, m: usize) -> Self {
let mut tree = vec![vec![0; m + 1]; n + 1];
SegmentTree2D { n, m, tree }
}
fn lowbit(&self, x: usize) -> usize {
x & (!x + 1)
}
fn update(&mut self, x: usize, y: usize, val: i32) {
let mut x = x;
while x <= self.n {
let mut y1 = y;
while y1 <= self.m {
self.tree[x][y1] += val;
y1 += self.lowbit(y1);
}
x += self.lowbit(x);
}
}
fn query(&self, x: usize, y: usize) -> i32 {
let mut res = 0;
let mut x = x;
while x > 0 {
let mut y1 = y;
while y1 > 0 {
res += self.tree[x][y1];
y1 -= self.lowbit(y1);
}
x -= self.lowbit(x);
}
res
}
}
impl Solution {
pub fn range_add_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut seg = SegmentTree2D::new(n as usize, n as usize);
for query in queries {
seg.update(query[0] as usize + 1, query[1] as usize + 1, 1);
seg.update(query[2] as usize + 2, query[1] as usize + 1, -1);
seg.update(query[0] as usize + 1, query[3] as usize + 2, -1);
seg.update(query[2] as usize + 2, query[3] as usize + 2, 1);
}
let mut res = vec![vec![0; n as usize]; n as usize];
for i in 0..n as usize {
for j in 0..n as usize {
res[i][j] = seg.query(i + 1, j + 1);
}
}
res
}
}
###Swift
class SegmentTree2D {
var n: Int
var m: Int
var tree: [[Int]]
init(n: Int, m: Int) {
self.n = n
self.m = m
self.tree = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)
}
func lowbit(_ x: Int) -> Int {
return x & (-x)
}
func update(_ x: Int, _ y: Int, _ val: Int) {
var x = x
while x <= n {
var y1 = y
while y1 <= m {
tree[x][y1] += val
y1 += lowbit(y1)
}
x += lowbit(x)
}
}
func query(_ x: Int, _ y: Int) -> Int {
var res = 0
var x = x
while x > 0 {
var y1 = y
while y1 > 0 {
res += tree[x][y1]
y1 -= lowbit(y1)
}
x -= lowbit(x)
}
return res
}
}
class Solution {
func rangeAddQueries(_ n: Int, _ queries: [[Int]]) -> [[Int]] {
let seg = SegmentTree2D(n: n, m: n)
for q in queries {
seg.update(q[0] + 1, q[1] + 1, 1)
seg.update(q[2] + 2, q[1] + 1, -1)
seg.update(q[0] + 1, q[3] + 2, -1)
seg.update(q[2] + 2, q[3] + 2, 1)
}
var res = Array(repeating: Array(repeating: 0, count: n), count: n)
for i in 0..<n {
for j in 0..<n {
res[i][j] = seg.query(i + 1, j + 1)
}
}
return res
}
}
###Kotlin
class SegmentTree2D {
val n: Int
val m: Int
val tree: Array<IntArray>
constructor(n: Int, m: Int) {
this.n = n
this.m = m
tree = Array(n + 1) { IntArray(m + 1) }
}
fun lowbit(x: Int): Int {
return x and (-x)
}
fun update(x: Int, y: Int, `val`: Int) {
var x = x
while (x <= n) {
var y1 = y
while (y1 <= m) {
tree[x][y1] += `val`
y1 += lowbit(y1)
}
x += lowbit(x)
}
}
fun query(x: Int, y: Int): Int {
var res = 0
var x = x
while (x > 0) {
var y1 = y
while (y1 > 0) {
res += tree[x][y1]
y1 -= lowbit(y1)
}
x -= lowbit(x)
}
return res
}
}
class Solution {
fun rangeAddQueries(n: Int, queries: Array<IntArray>): Array<IntArray> {
val seg = SegmentTree2D(n, n)
for (q in queries) {
seg.update(q[0] + 1, q[1] + 1, 1)
seg.update(q[2] + 2, q[1] + 1, -1)
seg.update(q[0] + 1, q[3] + 2, -1)
seg.update(q[2] + 2, q[3] + 2, 1)
}
val res = Array(n) { IntArray(n) }
for (i in 0 until n) {
for (j in 0 until n) {
res[i][j] = seg.query(i + 1, j + 1)
}
}
return res
}
}
###TypeScript
class SegmentTree2D {
n: number;
m: number;
tree: number[][];
constructor(n: number, m: number) {
this.n = n;
this.m = m;
this.tree = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
}
lowbit(x: number): number {
return x & (-x);
}
update(x: number, y: number, val: number): void {
while (x <= this.n) {
let y1 = y;
while (y1 <= this.m) {
this.tree[x][y1] += val;
y1 += this.lowbit(y1);
}
x += this.lowbit(x);
}
}
query(x: number, y: number): number {
let res = 0;
while (x > 0) {
let y1 = y;
while (y1 > 0) {
res += this.tree[x][y1];
y1 -= this.lowbit(y1);
}
x -= this.lowbit(x);
}
return res;
}
}
function rangeAddQueries(n: number, queries: number[][]): number[][] {
const seg = new SegmentTree2D(n, n);
for (const query of queries) {
seg.update(query[0] + 1, query[1] + 1, 1);
seg.update(query[2] + 2, query[1] + 1, -1);
seg.update(query[0] + 1, query[3] + 2, -1);
seg.update(query[2] + 2, query[3] + 2, 1);
}
const res: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
res[i][j] = seg.query(i + 1, j + 1);
}
}
return res;
};
###C#
class SegmentTree2D{
int n, m;
int[,] tree;
public SegmentTree2D(int n, int m){
this.n = n;
this.m = m;
tree = new int[n + 1,m + 1];
}
public int lowbit(int x){
return x & (-x);
}
public void update(int x, int y, int val){
while(x <= n){
int y1 = y;
while(y1 <= m){
tree[x,y1] += val;
y1 += lowbit(y1);
}
x += lowbit(x);
}
}
public int query(int x, int y){
int res = 0;
while(x > 0){
int y1 = y;
while(y1 > 0){
res += tree[x,y1];
y1 -= lowbit(y1);
}
x -= lowbit(x);
}
return res;
}
};
public class Solution {
public int[][] RangeAddQueries(int n, int[][] queries) {
SegmentTree2D seg = new SegmentTree2D(n, n);
foreach(int[] q in queries){
seg.update(q[0] + 1, q[1] + 1, 1);
seg.update(q[2] + 2, q[1] + 1, -1);
seg.update(q[0] + 1, q[3] + 2, -1);
seg.update(q[2] + 2, q[3] + 2, 1);
}
int[][] res = new int[n][];
for(int i = 0; i < n; i++){
res[i] = new int[n];
for(int j = 0; j < n; j++){
res[i][j] = seg.query(i + 1, j + 1);
}
}
return res;
}
}
时间复杂度：$O(Q \times \log(N^2) + N^2 \times \log(N^2))$。其中Q是查询次数，N是二维数组的宽度和高度。
空间复杂度：$O(N^2)$。
{:width=400}
用二维差分 $\mathcal{O}(1)$ 处理每个 $\textit{queries}[i]$。
然后计算二维差分矩阵的二维前缀和，即为答案。
代码实现时，为方便计算二维前缀和，可以在二维差分矩阵最上面添加一行 $0$，最左边添加一列 $0$，这样计算二维前缀和无需考虑下标越界。
class Solution:
def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
# 二维差分
diff = [[0] * (n + 2) for _ in range(n + 2)]
for r1, c1, r2, c2 in queries:
diff[r1 + 1][c1 + 1] += 1
diff[r1 + 1][c2 + 2] -= 1
diff[r2 + 2][c1 + 1] -= 1
diff[r2 + 2][c2 + 2] += 1
# 原地计算 diff 的二维前缀和，然后填入答案
ans = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j]
ans[i][j] = diff[i + 1][j + 1]
return ans
class Solution {
public int[][] rangeAddQueries(int n, int[][] queries) {
// 二维差分
int[][] diff = new int[n + 2][n + 2];
for (int[] q : queries) {
int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 原地计算 diff 的二维前缀和，然后填入答案
int[][] ans = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
ans[i][j] = diff[i + 1][j + 1];
}
}
return ans;
}
}
class Solution {
public:
vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
// 二维差分
vector diff(n + 2, vector<int>(n + 2));
for (auto& q : queries) {
int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 原地计算 diff 的二维前缀和，然后填入答案
vector ans(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
ans[i][j] = diff[i + 1][j + 1];
}
}
return ans;
}
};
int** rangeAddQueries(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize, int** returnColumnSizes) {
// 二维差分
int** diff = calloc(n + 2, sizeof(int*));
for (int i = 0; i < n + 2; i++) {
diff[i] = calloc(n + 2, sizeof(int));
}
for (int i = 0; i < queriesSize; i++) {
int r1 = queries[i][0], c1 = queries[i][1], r2 = queries[i][2], c2 = queries[i][3];
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 原地计算 diff 的二维前缀和，然后填入答案
int** ans = malloc(n * sizeof(int*));
*returnSize = n;
*returnColumnSizes = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
ans[i] = malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
ans[i][j] = diff[i + 1][j + 1];
}
}
for (int i = 0; i < n + 2; i++) {
free(diff[i]);
}
free(diff);
return ans;
}
func rangeAddQueries(n int, queries [][]int) [][]int {
// 二维差分
diff := make([][]int, n+2)
for i := range diff {
diff[i] = make([]int, n+2)
}
for _, q := range queries {
r1, c1, r2, c2 := q[0], q[1], q[2], q[3]
diff[r1+1][c1+1]++
diff[r1+1][c2+2]--
diff[r2+2][c1+1]--
diff[r2+2][c2+2]++
}
// 原地计算 diff 的二维前缀和，然后填入答案
ans := make([][]int, n)
for i := range ans {
ans[i] = make([]int, n)
for j := range ans[i] {
diff[i+1][j+1] += diff[i+1][j] + diff[i][j+1] - diff[i][j]
ans[i][j] = diff[i+1][j+1]
}
}
return ans
}
var rangeAddQueries = function(n, queries) {
// 二维差分
const diff = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));
for (const [r1, c1, r2, c2] of queries) {
diff[r1 + 1][c1 + 1]++;
diff[r1 + 1][c2 + 2]--;
diff[r2 + 2][c1 + 1]--;
diff[r2 + 2][c2 + 2]++;
}
// 原地计算 diff 的二维前缀和，然后填入答案
const ans = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
ans[i][j] = diff[i + 1][j + 1];
}
}
return ans;
};
impl Solution {
pub fn range_add_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let n = n as usize;
// 二维差分
let mut diff = vec![vec![0; n + 2]; n + 2];
for q in queries {
let (r1, c1, r2, c2) = (q[0] as usize, q[1] as usize, q[2] as usize, q[3] as usize);
diff[r1 + 1][c1 + 1] += 1;
diff[r1 + 1][c2 + 2] -= 1;
diff[r2 + 2][c1 + 1] -= 1;
diff[r2 + 2][c2 + 2] += 1;
}
// 原地计算 diff 的二维前缀和，然后填入答案
let mut ans = vec![vec![0; n]; n];
for i in 0..n {
for j in 0..n {
diff[i + 1][j + 1] += diff[i + 1][j] + diff[i][j + 1] - diff[i][j];
ans[i][j] = diff[i + 1][j + 1];
}
}
ans
}
}
注：也可以创建 $n\times n$ 大小的 $\textit{diff}$，原地计算二维前缀和，最后直接返回 $\textit{diff}$。
见数据结构题单的「§2.2 二维差分」和「§1.6 二维前缀和」。
欢迎关注 B站@灵茶山艾府
给你一个 二进制字符串 s。
你可以对这个字符串执行 任意次 下述操作：
i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。返回你能执行的 最大 操作次数。
示例 1：
输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
i = 0。结果字符串为 s = "0011101"。i = 4。结果字符串为 s = "0011011"。i = 3。结果字符串为 s = "0010111"。i = 2。结果字符串为 s = "0001111"。示例 2：
输入： s = "00111"
输出： 0
提示：
1 <= s.length <= 105s[i] 为 '0' 或 '1'。设 $f(i)$ 表示可以移动原字符串中下标为 $i$ 的 $1$ 几次。
若 $s_i$ 和 $s_{i + 1}$ 都是 $1$，后续只有 $s_{i + 1}$ 动了，$s_i$ 才能动，所以这种情况下 $f(i) = f(i + 1)$。
若 $s_i$ 是 $1$，$s_{i + 1}$ 是 $0$，下一个 $1$ 在 $s_j$（$j > i$），那么我们可以先把 $s_i$ 移动到下标 $(j - 1)$，就变成了上面那种情况。所以这种情况下 $f(i) = f(j) + 1$。
答案就是 $\sum f(i)$。复杂度 $\mathcal{O}(n)$。
###cpp
class Solution {
public:
int maxOperations(string s) {
int n = s.size();
long long ans = 0;
for (int i = n - 2, last = 0; i >= 0; i--) if (s[i] == '1') {
if (s[i + 1] == '0') last++;
ans += last;
}
return ans;
}
};
把 $1$ 当作车，想象有一条长为 $n$ 的道路上有一些车。
题意：把所有的车都开到最右边。例如 $011010$ 最终要变成 $000111$。
如果优先操作右边的（能移动的）车，那么这些车都只需操作一次：
$$
\begin{aligned}
& 011010 \
\to{} & 011001 \
\to{} & 010011 \
\to{} & 000111 \
\end{aligned}
$$
一共需要操作 $3$ 次（注意一次操作可以让一辆车移动多次）。
而如果优先操作左边的（能移动的）车，这会制造大量的「堵车」，每辆车的操作次数会更多。
$$
\begin{aligned}
& 011010 \
\to{} & 010110 \
\to{} & 001110 \
\to{} & 001101 \
\to{} & 001011 \
\to{} & 000111 \
\end{aligned}
$$
一共需要操作 $5$ 次。
算法：
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def maxOperations(self, s: str) -> int:
ans = cnt1 = 0
for i, c in enumerate(s):
if c == '1':
cnt1 += 1
elif i > 0 and s[i - 1] == '1':
ans += cnt1
return ans
###java
class Solution {
public int maxOperations(String S) {
char[] s = S.toCharArray();
int ans = 0;
int cnt1 = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] == '1') {
cnt1++;
} else if (i > 0 && s[i - 1] == '1') {
ans += cnt1;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int maxOperations(string s) {
int ans = 0, cnt1 = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '1') {
cnt1++;
} else if (i > 0 && s[i - 1] == '1') {
ans += cnt1;
}
}
return ans;
}
};
###c
int maxOperations(char* s) {
int ans = 0, cnt1 = 0;
for (int i = 0; s[i]; i++) {
char c = s[i];
if (c == '1') {
cnt1++;
} else if (i > 0 && s[i - 1] == '1') {
ans += cnt1;
}
}
return ans;
}
###go
func maxOperations(s string) (ans int) {
cnt1 := 0
for i, c := range s {
if c == '1' {
cnt1++
} else if i > 0 && s[i-1] == '1' {
ans += cnt1
}
}
return
}
###js
var maxOperations = function(s) {
let ans = 0, cnt1 = 0;
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === '1') {
cnt1++;
} else if (i > 0 && s[i - 1] === '1') {
ans += cnt1;
}
}
return ans;
};
###rust
impl Solution {
pub fn max_operations(s: String) -> i32 {
let s = s.as_bytes();
let mut ans = 0;
let mut cnt1 = 0;
for (i, &c) in s.iter().enumerate() {
if c == b'1' {
cnt1 += 1;
} else if i > 0 && s[i - 1] == b'1' {
ans += cnt1;
}
}
ans
}
}
构造一个 $s$，让返回值尽量大。
如果 $n=10^5$，答案最大能是多少？会不会超过 $\texttt{int}$ 最大值？
欢迎关注 B站@灵茶山艾府
给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：
0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。
两个正整数的最大公约数指的是能整除这两个数的最大正整数。
示例 1：
输入：nums = [2,6,3,4] 输出：4 解释：我们可以执行以下操作： - 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。 - 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。 - 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。 - 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
示例 2：
输入：nums = [2,10,6,14] 输出：-1 解释：无法将所有元素都变成 1 。
提示：
2 <= nums.length <= 501 <= nums[i] <= 106SlidingWindowAggregation 是一个维护幺半群的滑动窗口的数据结构，可以在 $O(1)$ 时间内做到入队、出队、查询滑窗内的聚合值，原理类似 面试题 03.02. 栈的最小值 (StackAggregation).
ps: 吐槽一下这道题的数据量，看到 50 很容易会去想回溯+剪枝，但是会收获一大堆TLE 🤣
###python3
INF = int(1e20)
class Solution:
def minOperations(self, nums: List[int]) -> int:
if gcd(*nums) != 1:
return -1
if 1 in nums:
return len(nums) - nums.count(1)
return minLen(nums) - 1 + len(nums) - 1
def minLen(nums: List[int]) -> int:
"""gcd为1的最短子数组.不存在返回INF."""
n = len(nums)
S = SlidingWindowAggregation(lambda: 0, gcd)
res, n = INF, len(nums)
for right in range(n):
S.append(nums[right])
while S and S.query() == 1:
res = min(res, len(S))
S.popleft()
return res
###python3
from typing import Callable, Generic, List, TypeVar
E = TypeVar("E")
class SlidingWindowAggregation(Generic[E]):
"""SlidingWindowAggregation
Api:
1. append value to tail,O(1).
2. pop value from head,O(1).
3. query aggregated value in window,O(1).
"""
__slots__ = ["_stack0", "_stack1", "_stack2", "_stack3", "_e0", "_e1", "_size", "_op", "_e"]
def __init__(self, e: Callable[[], E], op: Callable[[E, E], E]):
"""
Args:
e: unit element
op: merge function
"""
self._stack0 = []
self._stack1 = []
self._stack2 = []
self._stack3 = []
self._e = e
self._e0 = e()
self._e1 = e()
self._size = 0
self._op = op
def append(self, value: E) -> None:
if not self._stack0:
self._push0(value)
self._transfer()
else:
self._push1(value)
self._size += 1
def popleft(self) -> None:
if not self._size:
return
if not self._stack0:
self._transfer()
self._stack0.pop()
self._stack2.pop()
self._e0 = self._stack2[-1] if self._stack2 else self._e()
self._size -= 1
def query(self) -> E:
return self._op(self._e0, self._e1)
def _push0(self, value):
self._stack0.append(value)
self._e0 = self._op(value, self._e0)
self._stack2.append(self._e0)
def _push1(self, value):
self._stack1.append(value)
self._e1 = self._op(self._e1, value)
self._stack3.append(self._e1)
def _transfer(self):
while self._stack1:
self._push0(self._stack1.pop())
while self._stack3:
self._stack3.pop()
self._e1 = self._e()
def __len__(self):
return self._size
首先，如果所有数的 GCD（最大公约数）大于 $1$，那么无论如何都无法操作出 $1$，我们返回 $-1$。
如果 $\textit{nums}$ 中有一个 $1$，那么从 $1$ 向左向右不断替换就能把所有数变成 $1$。
例如 $[2,2,1,2,2]\rightarrow[2,\underline{1},1,2,2]\rightarrow[\underline{1},1,1,2,2]\rightarrow[1,1,1,\underline{1},2]\rightarrow[1,1,1,1,\underline{1}]$，一共 $n-1=5-1=4$ 次操作。
如果有多个 $1$，那么每个 $1$ 只需要向左修改，最后一个 $1$ 向右修改剩余的数字。
例如 $[2,1,2,1,2]\rightarrow[\underline{1},1,2,1,2]\rightarrow[1,1,\underline{1},1,2]\rightarrow[1,1,1,1,\underline{1}]$，一共 $n-\textit{cnt}_1=5-2=3$ 次操作。这里 $\textit{cnt}_1$ 表示 $\textit{nums}$ 中 $1$ 的个数。
所以如果 $\textit{nums}$ 中有 $1$，答案为
$$
n-\textit{cnt}_1
$$
如果 $\textit{nums}$ 中没有 $1$ 呢？
如果 $\textit{nums}$ 中没有 $1$，想办法花费尽量少的操作得出一个 $1$。
由于只能操作相邻的数，所以这个 $1$ 必然是一个连续子数组的 GCD。（如果在不连续的情况下得到了 $1$，那么这个 $1$ 只能属于其中某个连续子数组，其余的操作是多余的。）
那么找到最短的 GCD 为 $1$ 的子数组，设其长度为 $\textit{minSize}$，那么我们需要操作 $\textit{minSize}-1$ 次得到 $1$。
例如 $[2,6,3,4]$ 中的 $[3,4]$ 可以操作 $2-1=1$ 次得到 $1$。
然后就转化成提示 1 中的情况了，最终答案为
$$
(\textit{minSize}-1) + (n-1) = \textit{minSize}+n-2
$$
本题视频讲解（第四题）
class Solution:
def minOperations(self, nums: List[int]) -> int:
if gcd(*nums) > 1:
return -1
n = len(nums)
cnt1 = sum(x == 1 for x in nums)
if cnt1:
return n - cnt1
min_size = n
for i in range(n):
g = 0
for j in range(i, n):
g = gcd(g, nums[j])
if g == 1:
# 这里本来是 j-i+1，把 +1 提出来合并到 return 中
min_size = min(min_size, j - i)
break
return min_size + n - 1
class Solution {
public int minOperations(int[] nums) {
int n = nums.length, gcdAll = 0, cnt1 = 0;
for (int x : nums) {
gcdAll = gcd(gcdAll, x);
if (x == 1) ++cnt1;
}
if (gcdAll > 1) return -1;
if (cnt1 > 0) return n - cnt1;
int minSize = n;
for (int i = 0; i < n; i++) {
int g = 0;
for (int j = i; j < n; j++) {
g = gcd(g, nums[j]);
if (g == 1) {
// 这里本来是 j-i+1，把 +1 提出来合并到 return 中
minSize = Math.min(minSize, j - i);
break;
}
}
}
return minSize + n - 1;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size(), gcd_all = 0, cnt1 = 0;
for (int x : nums) {
gcd_all = gcd(gcd_all, x);
cnt1 += x == 1;
}
if (gcd_all > 1) return -1;
if (cnt1) return n - cnt1;
int min_size = n;
for (int i = 0; i < n; i++) {
int g = 0;
for (int j = i; j < n; j++) {
g = gcd(g, nums[j]);
if (g == 1) {
// 这里本来是 j-i+1，把 +1 提出来合并到 return 中
min_size = min(min_size, j - i);
break;
}
}
}
return min_size + n - 1;
}
};
func minOperations(nums []int) int {
n, gcdAll, cnt1 := len(nums), 0, 0
for _, x := range nums {
gcdAll = gcd(gcdAll, x)
if x == 1 {
cnt1++
}
}
if gcdAll > 1 {
return -1
}
if cnt1 > 0 {
return n - cnt1
}
minSize := n
for i := range nums {
g := 0
for j, x := range nums[i:] {
g = gcd(g, x)
if g == 1 {
// 这里本来是 j+1，把 +1 提出来合并到 return 中
minSize = min(minSize, j)
break
}
}
}
return minSize + n - 1
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
前置知识：LogTrick 入门教程。
这个做法可以解决 $n=10^5$ 的情况。
class Solution:
def minOperations(self, nums: List[int]) -> int:
if gcd(*nums) > 1:
return -1
n = len(nums)
cnt1 = sum(x == 1 for x in nums)
if cnt1:
return n - cnt1
min_size = n
a = [] # [GCD，相同 GCD 闭区间的右端点]
for i, x in enumerate(nums):
a.append([x, i])
# 原地去重，因为相同的 GCD 都相邻在一起
j = 0
for p in a:
p[0] = gcd(p[0], x)
if a[j][0] != p[0]:
j += 1
a[j] = p
else:
a[j][1] = p[1]
del a[j + 1:]
if a[0][0] == 1:
# 这里本来是 i-a[0][1]+1，把 +1 提出来合并到 return 中
min_size = min(min_size, i - a[0][1])
return min_size + n - 1
class Solution {
public int minOperations(int[] nums) {
int n = nums.length, gcdAll = 0, cnt1 = 0;
for (int x : nums) {
gcdAll = gcd(gcdAll, x);
if (x == 1) ++cnt1;
}
if (gcdAll > 1) return -1;
if (cnt1 > 0) return n - cnt1;
int minSize = n;
var g = new ArrayList<int[]>(); // [GCD，相同 GCD 闭区间的右端点]
for (int i = 0; i < n; i++) {
g.add(new int[]{nums[i], i});
// 原地去重，因为相同的 GCD 都相邻在一起
var j = 0;
for (var p : g) {
p[0] = gcd(p[0], nums[i]);
if (g.get(j)[0] == p[0])
g.get(j)[1] = p[1]; // 合并相同值，下标取最小的
else g.set(++j, p);
}
g.subList(j + 1, g.size()).clear();
if (g.get(0)[0] == 1)
// 这里本来是 i-g.get(0)[1]+1，把 +1 提出来合并到 return 中
minSize = Math.min(minSize, i - g.get(0)[1]);
}
return minSize + n - 1;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size(), gcd_all = 0, cnt1 = 0;
for (int x : nums) {
gcd_all = gcd(gcd_all, x);
cnt1 += x == 1;
}
if (gcd_all > 1) return -1;
if (cnt1) return n - cnt1;
int min_size = n;
vector<pair<int, int>> g; // {GCD，相同 GCD 闭区间的右端点}
for (int i = 0; i < n; i++) {
g.emplace_back(nums[i], i);
// 原地去重，因为相同的 GCD 都相邻在一起
int j = 0;
for (auto& p : g) {
p.first = gcd(p.first, nums[i]);
if (g[j].first == p.first)
g[j].second = p.second;
else g[++j] = move(p);
}
g.resize(j + 1);
if (g[0].first == 1)
// 这里本来是 i-g[0].second+1，把 +1 提出来合并到 return 中
min_size = min(min_size, i - g[0].second);
}
return min_size + n - 1;
}
};
func minOperations(nums []int) int {
n, gcdAll, cnt1 := len(nums), 0, 0
for _, x := range nums {
gcdAll = gcd(gcdAll, x)
if x == 1 {
cnt1++
}
}
if gcdAll > 1 {
return -1
}
if cnt1 > 0 {
return n - cnt1
}
minSize := n
type result struct{ gcd, i int }
a := []result{}
for i, x := range nums {
for j, r := range a {
a[j].gcd = gcd(r.gcd, x)
}
a = append(a, result{x, i})
// 去重
j := 0
for _, q := range a[1:] {
if a[j].gcd != q.gcd {
j++
a[j] = q
} else {
a[j].i = q.i // 相同 gcd 保存最右边的位置
}
}
a = a[:j+1]
if a[0].gcd == 1 {
// 这里本来是 i-a[0].i+1，把 +1 提出来合并到 return 中
minSize = min(minSize, i-a[0].i)
}
}
return minSize + n - 1
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
注：由于本题数据范围小，这两种做法的运行时间区别并不明显。
见下面位运算题单的「LogTrick」。
补充：
欢迎关注 B站@灵茶山艾府
首先处理一些特殊情况：
剩下的情况就是：序列的最大公约数为 $1$，但是每个元素都大于 $1$。如果我们能通过某种方式把第一个 $1$ 弄出来，就转化为了上述第二种特殊情况，答案就是“弄出第一个 $1$ 的最少步数”，加上“弄出第一个 $1$ 后，序列里大于 $1$ 的数还有几个”。第二项的值显然是 $(n - 1)$，因此剩下的问题就是计算“弄出第一个 $1$ 的最少步数”。
首先注意到一个关键结论：进行任意次操作之后，序列里的第 $i$ 个数一定是 $\text{gcd}(a[l..r])$，其中 $a[l..r]$ 表示序列里从第 $l$ 个数到第 $r$ 个数形成的连续子数组，并且满足 $l \le i \le r$。这个结论可以用归纳法进行证明。
既然操作的结果是一段连续子数组的最大公约数，那么对于一个长度为 $k$ 的子数组，我们可以通过 $(k - 1)$ 次操作把其中一个数变成整个子数组的最大公约数。因此，我们只需要找到长度最小的子数组，使得子数组的最大公约数等于 $1$，那么“弄出第一个 $1$ 的最少步数”就是子数组的长度减去一。
因为整个序列的长度只有 $50$，我们完全可以从 $2$ 到 $n$ 枚举 $k$，并检查是否存在长度为 $k$ 的，且最大公约数为 $1$ 的子数组。复杂度 $\mathcal{O}(n^3)$。
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// 剩余情况，枚举子数组的长度 l 和子数组的初始下标 i，检查 a[i..i + l - 1] 的 gcd 是否为 1
for (int l = 2; l <= n; l++) for (int i = 0, j = l - 1; j < n; i++, j++) {
int g = nums[i];
for (int k = i; k <= j; k++) g = gcd(g, nums[k]);
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (g == 1) return l - 1 + n - 1;
}
// 不可能，但是函数的所有 branch 一定要有返回值
assert(false);
return -1;
}
};
我们还可以对以上代码进行优化。主要是针对“寻找最大公约数等于 $1$，且长度最小的子数组”这一部分。如果一个子数组的最大公约数为 $1$，那么包含该子数组的其它子数组最大公约数也等于 $1$，因此这一部分可以使用 two pointers 解决，复杂度降至 $\mathcal{O}(n^2)$。
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// 求 a[L..R] 的 gcd
auto gao = [&](int L, int R) {
int g = 0;
for (int i = L; i <= R; i++) g = gcd(g, nums[i]);
return g;
};
int ans = 1e9;
// 双指针求以 i 为开头的，长度最短的，最大公约数为 1 的子数组
// 这个子数组含 i 不含 j
for (int i = 0, j = 0; i < n; i++) {
while (j < n && gao(i, j - 1) != 1) j++;
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (gao(i, j - 1) == 1) ans = min(ans, j - i - 1 + n - 1);
}
return ans;
}
};
上述求子数组最大公约数的 gao 函数仍然可以优化。由于最大公约数满足结合律，我们可以通过 RMQ 或 线段树 在每次 $\mathcal{O}(\log n)$ 的复杂度下计算子数组的最大公约数，复杂度降至 $\mathcal{O}(n\log n)$。
###c++
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 特殊情况 1：整个序列的 gcd > 1
int g = nums[0];
for (int x : nums) g = gcd(g, x);
if (g > 1) return -1;
// 特殊情况 2：序列里已经有 1
int cnt = 0;
for (int x : nums) if (x != 1) cnt++;
if (cnt != n) return cnt;
// go[id] 是线段树节点 id 代表的区间的 gcd
int go[n * 4 + 10];
// 构建线段树
function<void(int, int, int)> build = [&](int id, int l, int r) {
if (l == r) go[id] = nums[l];
else {
int nxt = id << 1, mid = (l + r) >> 1;
build(nxt, l, mid);
build(nxt | 1, mid + 1, r);
go[id] = gcd(go[nxt], go[nxt | 1]);
}
};
build(1, 0, n - 1);
// 查询 [ql, qr] 区间的 gcd
function<int(int, int, int, int, int)> query = [&](int id, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return go[id];
int nxt = id << 1, mid = (l + r) >> 1;
return gcd(
ql <= mid ? query(nxt, l, mid, ql, qr) : 0,
qr > mid ? query(nxt | 1, mid + 1, r, ql, qr) : 0
);
};
// 求 a[L..R] 的 gcd
auto gao = [&](int L, int R) {
if (L > R) return 0;
return query(1, 0, n - 1, L, R);
};
int ans = 1e9;
// 双指针求以 i 为开头的，长度最短的，最大公约数为 1 的子数组
// 这个子数组含 i 不含 j
for (int i = 0, j = 0; i < n; i++) {
while (j < n && gao(i, j - 1) != 1) j++;
// 找到了符合要求的子数组，答案就是子数组长度减去一，再加上 (n - 1)
if (gao(i, j - 1) == 1) ans = min(ans, j - i - 1 + n - 1);
}
return ans;
}
};
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i] 仅由 '0' 和 '1' 组成1 <= m, n <= 100设 $\textit{strs}[i]$ 中 $0$ 的个数为 $\textit{cnt}_0[i]$，$1$ 的个数为 $\textit{cnt}_1[i]$，那么本题相当于：
这相当于背包有两种体积（二维），所以在定义状态的时候，相比只有一种体积的 0-1 背包，要多加一个参数。
如果你不了解 0-1 背包，请看【基础算法精讲 18】。
在一维 0-1 背包的基础上，多加一个参数，即定义 $\textit{dfs}(i,j,k)$ 表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。
考虑 $\textit{strs}[i]$ 选或不选：
两种情况取最大值，得
$$
\textit{dfs}(i,j,k) = \max(\textit{dfs}(i-1,j,k), \textit{dfs}(i-1,j-\textit{cnt}_0[i],k-\textit{cnt}_1[i]) + 1)
$$
如果
递归边界：$\textit{dfs}(-1,j,k)=0$。此时没有物品可以选。
递归入口：$\textit{dfs}(k-1,m,n)$，这是原问题，也是答案。其中 $k$ 为 $\textit{strs}$ 的长度。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
cnt0 = [s.count('0') for s in strs]
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, j: int, k: int) -> int:
if i < 0:
return 0
res = dfs(i - 1, j, k) # 不选 strs[i]
cnt1 = len(strs[i]) - cnt0[i]
if j >= cnt0[i] and k >= cnt1:
res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1) # 选 strs[i]
return res
return dfs(len(strs) - 1, m, n)
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int k = strs.length;
int[] cnt0 = new int[k];
for (int i = 0; i < k; i++) {
cnt0[i] = (int) strs[i].chars().filter(ch -> ch == '0').count();
}
int[][][] memo = new int[strs.length][m + 1][n + 1];
for (int[][] mat : memo) {
for (int[] arr : mat) {
Arrays.fill(arr, -1); // -1 表示没有计算过
}
}
return dfs(k - 1, m, n, strs, cnt0, memo);
}
private int dfs(int i, int j, int k, String[] strs, int[] cnt0, int[][][] memo) {
if (i < 0) {
return 0;
}
if (memo[i][j][k] != -1) { // 之前计算过
return memo[i][j][k];
}
// 不选 strs[i]
int res = dfs(i - 1, j, k, strs, cnt0, memo);
int cnt1 = strs[i].length() - cnt0[i];
if (j >= cnt0[i] && k >= cnt1) {
// 选 strs[i]
res = Math.max(res, dfs(i - 1, j - cnt0[i], k - cnt1, strs, cnt0, memo) + 1);
}
return memo[i][j][k] = res; // 记忆化
}
}
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> cnt0(strs.size());
for (int i = 0; i < strs.size(); i++) {
cnt0[i] = ranges::count(strs[i], '0');
}
vector memo(strs.size(), vector(m + 1, vector<int>(n + 1, -1))); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i < 0) {
return 0;
}
int& res = memo[i][j][k]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
res = dfs(i - 1, j, k); // 不选 strs[i]
int cnt1 = strs[i].size() - cnt0[i];
if (j >= cnt0[i] && k >= cnt1) {
res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1); // 选 strs[i]
}
return res;
};
return dfs(strs.size() - 1, m, n);
}
};
func findMaxForm(strs []string, m, n int) int {
k := len(strs)
cnt0 := make([]int, k)
for i, s := range strs {
cnt0[i] = strings.Count(s, "0")
}
memo := make([][][]int, k)
for i := range memo {
memo[i] = make([][]int, m+1)
for j := range memo[i] {
memo[i][j] = make([]int, n+1)
for k := range memo[i][j] {
memo[i][j][k] = -1 // -1 表示没有计算过
}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) int {
if i < 0 {
return 0
}
p := &memo[i][j][k]
if *p != -1 { // 之前计算过
return *p
}
res := dfs(i-1, j, k) // 不选 strs[i]
cnt1 := len(strs[i]) - cnt0[i]
if j >= cnt0[i] && k >= cnt1 {
res = max(res, dfs(i-1, j-cnt0[i], k-cnt1)+1) // 选 strs[i]
}
*p = res // 记忆化
return res
}
return dfs(k-1, m, n)
}
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，$f[i+1][j][k]$ 的定义和 $\textit{dfs}(i,j,k)$ 的定义是一样的，都表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。这里 $+1$ 是为了把 $\textit{dfs}(-1,j,k)$ 这个状态也翻译过来，这样我们可以把 $f[0][j][k]$ 作为初始值。
相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：
$$
f[i+1][j][k] = \max(f[i][j][k], f[i][j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$
初始值 $f[0][j][k]=0$，翻译自递归边界 $\textit{dfs}(-1,j,k)=0$。
答案为 $f[k][m][n]$，翻译自递归入口 $\textit{dfs}(k-1,m,n)$。其中 $k$ 为 $\textit{strs}$ 的长度。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
f = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]
for i, s in enumerate(strs):
cnt0 = s.count('0')
cnt1 = len(s) - cnt0
for j in range(m + 1):
for k in range(n + 1):
if j >= cnt0 and k >= cnt1:
f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1)
else:
f[i + 1][j][k] = f[i][j][k]
return f[-1][m][n]
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][][] f = new int[strs.length + 1][m + 1][n + 1];
for (int i = 0; i < strs.length; i++) {
int cnt0 = (int) strs[i].chars().filter(ch -> ch == '0').count();
int cnt1 = strs[i].length() - cnt0;
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
if (j >= cnt0 && k >= cnt1) {
f[i + 1][j][k] = Math.max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
} else {
f[i + 1][j][k] = f[i][j][k];
}
}
}
}
return f[strs.length][m][n];
}
}
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector f(strs.size() + 1, vector(m + 1, vector<int>(n + 1)));
for (int i = 0; i < strs.size(); i++) {
int cnt0 = ranges::count(strs[i], '0');
int cnt1 = strs[i].size() - cnt0;
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= n; k++) {
if (j >= cnt0 && k >= cnt1) {
f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
} else {
f[i + 1][j][k] = f[i][j][k];
}
}
}
}
return f.back()[m][n];
}
};
func findMaxForm(strs []string, m, n int) int {
k := len(strs)
f := make([][][]int, k+1)
for i := range f {
f[i] = make([][]int, m+1)
for j := range f[i] {
f[i][j] = make([]int, n+1)
}
}
for i, s := range strs {
cnt0 := strings.Count(s, "0")
cnt1 := len(s) - cnt0
for j := range m + 1 {
for k := range n + 1 {
if j >= cnt0 && k >= cnt1 {
f[i+1][j][k] = max(f[i][j][k], f[i][j-cnt0][k-cnt1]+1)
} else {
f[i+1][j][k] = f[i][j][k]
}
}
}
}
return f[k][m][n]
}
观察上面的状态转移方程，在计算 $f[i+1]$ 时，只会用到 $f[i]$，不会用到比 $i$ 更早的状态。
那么去掉第一个维度，把 $f[i+1]$ 和 $f[i]$ 保存到同一个二维数组中。
状态转移方程改为
$$
f[j][k] = \max(f[j][k], f[j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$
初始值 $f[j][k]=0$。
答案为 $f[m][n]$。
下面代码为什么要倒序循环，请看【基础算法精讲 18】。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
f = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
cnt0 = s.count('0')
cnt1 = len(s) - cnt0
for j in range(m, cnt0 - 1, -1):
for k in range(n, cnt1 - 1, -1):
f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1)
return f[m][n]
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] f = new int[m + 1][n + 1];
for (String s : strs) {
int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
int cnt1 = s.length() - cnt0;
for (int j = m; j >= cnt0; j--) {
for (int k = n; k >= cnt1; k--) {
f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
}
}
}
return f[m][n];
}
}
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector f(m + 1, vector<int>(n + 1));
for (string& s : strs) {
int cnt0 = ranges::count(s, '0');
int cnt1 = s.size() - cnt0;
for (int j = m; j >= cnt0; j--) {
for (int k = n; k >= cnt1; k--) {
f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
}
}
}
return f[m][n];
}
};
func findMaxForm(strs []string, m, n int) int {
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
for _, s := range strs {
cnt0 := strings.Count(s, "0")
cnt1 := len(s) - cnt0
for j := m; j >= cnt0; j-- {
for k := n; k >= cnt1; k-- {
f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
}
}
}
return f[m][n]
}
比如 $n=m=90$，前 $3$ 个字符串总共有 $5$ 个 $0$ 和 $6$ 个 $1$，那么无论我们怎么选，也选不出几十个 $0$ 和 $1$，所以上面的代码中，其实有大量的循环是多余的。
为此，额外用两个变量 $\textit{sum}_0$ 和 $\textit{sum}_1$ 分别维护前 $i$ 个字符串中的 $0$ 的个数和 $1$ 的个数（但不能超过 $m$ 和 $n$）。循环的时候 $j$ 从 $\textit{sum}_0$ 开始，$k$ 从 $\textit{sum}_1$ 开始。
注意这个优化会导致只有一部分 $f[j][k]$ 被更新到，最大值并没有传递给 $f[m][n]$，可能留在二维数组中间的某个位置上。所以最后要遍历 $f$，取其中最大值作为答案。
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
f = [[0] * (n + 1) for _ in range(m + 1)]
sum0 = sum1 = 0
for s in strs:
cnt0 = s.count('0')
cnt1 = len(s) - cnt0
sum0 = min(sum0 + cnt0, m)
sum1 = min(sum1 + cnt1, n)
for j in range(sum0, cnt0 - 1, -1):
for k in range(sum1, cnt1 - 1, -1):
v = f[j - cnt0][k - cnt1] + 1
if v > f[j][k]: # 手写 max，效率更高
f[j][k] = v
return max(map(max, f))
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] f = new int[m + 1][n + 1];
int sum0 = 0;
int sum1 = 0;
for (String s : strs) {
int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
int cnt1 = s.length() - cnt0;
sum0 = Math.min(sum0 + cnt0, m);
sum1 = Math.min(sum1 + cnt1, n);
for (int j = sum0; j >= cnt0; j--) {
for (int k = sum1; k >= cnt1; k--) {
f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
}
}
}
int ans = 0;
for (int[] row : f) {
for (int v : row) {
ans = Math.max(ans, v);
}
}
return ans;
}
}
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector f(m + 1, vector<int>(n + 1));
int sum0 = 0, sum1 = 0;
for (string& s : strs) {
int cnt0 = ranges::count(s, '0');
int cnt1 = s.size() - cnt0;
sum0 = min(sum0 + cnt0, m);
sum1 = min(sum1 + cnt1, n);
for (int j = sum0; j >= cnt0; j--) {
for (int k = sum1; k >= cnt1; k--) {
f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
}
}
}
int ans = 0;
for (auto& row : f) {
ans = max(ans, ranges::max(row));
}
return ans;
}
};
func findMaxForm(strs []string, m, n int) (ans int) {
f := make([][]int, m+1)
for i := range f {
f[i] = make([]int, n+1)
}
sum0, sum1 := 0, 0
for _, s := range strs {
cnt0 := strings.Count(s, "0")
cnt1 := len(s) - cnt0
sum0 = min(sum0+cnt0, m)
sum1 = min(sum1+cnt1, n)
for j := sum0; j >= cnt0; j-- {
for k := sum1; k >= cnt1; k-- {
f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
}
}
}
for _, row := range f {
ans = max(ans, slices.Max(row))
}
return
}
更多相似题目，见 动态规划题单 中的「§3.1 0-1 背包」。
欢迎关注 B站@灵茶山艾府
