给你一个二进制字符串 s（仅由 '0' 和 '1' 组成的字符串）。
返回所有字符都为 1 的子字符串的数目。
由于答案可能很大，请你将它对 10^9 + 7 取模后返回。
示例 1：
输入：s = "0110111" 输出：9 解释：共有 9 个子字符串仅由 '1' 组成 "1" -> 5 次 "11" -> 3 次 "111" -> 1 次
示例 2：
输入：s = "101" 输出：2 解释：子字符串 "1" 在 s 中共出现 2 次
示例 3：
输入：s = "111111" 输出：21 解释：每个子字符串都仅由 '1' 组成
示例 4：
输入：s = "000" 输出：0
提示：
登录
s[i] == '0' 或 s[i] == '1'
1 <= s.length <= 10^5遍历 $s$ 的过程中，记录上一个 $0$ 的位置 $\textit{last}_0$。
如果 $s[i]=1$，那么对于右端点为 $i$ 的全 $1$ 子串，左端点可以是
$$
\textit{last}_0+1,\textit{last}_0+2,\ldots,i-1,i
$$
一共有 $i - \textit{last}_0$ 个，加到答案中。
比如 $\textit{last}_0=2$，现在 $s[5]=1$，那么子串 $[3,5],[4,5],[5,5]$ 都只包含 $1$，有 $5-2=3$ 个以 $5$ 为右端点的全 $1$ 子串。
可能一开始没有 $0$，为了让公式兼容这种情况，初始化 $\textit{last}_0=-1$。
注意答案不超过 $64$ 位整数的最大值，可以在最后返回时再取模。
###py
class Solution:
def numSub(self, s: str) -> int:
MOD = 1_000_000_007
ans = 0
last0 = -1
for i, ch in enumerate(s):
if ch == '0':
last0 = i # 记录上个 0 的位置
else:
ans += i - last0 # 右端点为 i 的全 1 子串个数
return ans % MOD
###java
class Solution {
public int numSub(String s) {
final int MOD = 1_000_000_007;
long ans = 0;
int last0 = -1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '0') {
last0 = i; // 记录上个 0 的位置
} else {
ans += i - last0; // 右端点为 i 的全 1 子串个数
}
}
return (int) (ans % MOD);
}
}
###cpp
class Solution {
public:
int numSub(string s) {
constexpr int MOD = 1'000'000'007;
long long ans = 0;
int last0 = -1;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0') {
last0 = i; // 记录上个 0 的位置
} else {
ans += i - last0; // 右端点为 i 的全 1 子串个数
}
}
return ans % MOD;
}
};
###c
#define MOD 1000000007
int numSub(char* s) {
long long ans = 0;
int last0 = -1;
for (int i = 0; s[i]; i++) {
if (s[i] == '0') {
last0 = i; // 记录上个 0 的位置
} else {
ans += i - last0; // 右端点为 i 的全 1 子串个数
}
}
return ans % MOD;
}
###go
func numSub(s string) (ans int) {
const mod = 1_000_000_007
last0 := -1
for i, ch := range s {
if ch == '0' {
last0 = i // 记录上个 0 的位置
} else {
ans += i - last0 // 右端点为 i 的全 1 子串个数
}
}
return ans % mod
}
###js
var numSub = function(s) {
const MOD = 1_000_000_007;
let ans = 0, last0 = -1;
for (let i = 0; i < s.length; i++) {
if (s[i] === '0') {
last0 = i; // 记录上个 0 的位置
} else {
ans += i - last0; // 右端点为 i 的全 1 子串个数
}
}
return ans % MOD;
};
###rust
impl Solution {
pub fn num_sub(s: String) -> i32 {
const MOD: i64 = 1_000_000_007;
let mut ans = 0;
let mut last0 = -1;
for (i, ch) in s.bytes().enumerate() {
if ch == b'0' {
last0 = i as i32; // 记录上个 0 的位置
} else {
ans += (i as i32 - last0) as i64; // 右端点为 i 的全 1 子串个数
}
}
(ans % MOD) as _
}
}
见下面双指针题单的「六、分组循环」。
欢迎关注 B站@灵茶山艾府
###c++
class Solution {
public:
int numSub(string s) {
int res = 0, cnt = 0;
int mod = pow(10,9) + 7;
for(char c: s){
if(c=='1'){
++cnt;
res = (res + cnt) % mod;
}
else cnt = 0;
}
return res;
}
};
如果一个所有字符都为 $1$ 的字符串的长度为 $k$，则该字符串包含的所有字符都为 $1$ 的子字符串（包括该字符串本身）的数量是 $\dfrac{k * (k + 1)}{2}$。
首先寻找到所有的只包含字符 $1$ 的最长子字符串。这里的「只包含字符 $1$ 的最长子字符串」的意思是，假设该子字符串的下标范围是 $[i, j]$（包含下标 $i$ 和下标 $j$），其中 $i \le j$，该子字符串中的所有字符都是 $1$，且下标 $i$ 满足 $i$ 位于字符串 $s$ 的最左侧或者下标 $i - 1$ 位置的字符是 $0$，以及下标 $j$ 满足 $j$ 位于字符串 $s$ 的最右侧或者下标 $j + 1$ 位置的字符是 $0$。
寻找到所有的只包含字符 $1$ 的最长子字符串之后，就可以计算所有字符都为 $1$ 的子字符串的数量。
具体做法是，从左到右遍历字符串，如果遇到字符 $1$ 则计算连续字符 $1$ 的数量，如果遇到字符 $0$ 则说明上一个只包含字符 $1$ 的最长子字符串遍历结束，根据最长子字符串的长度计算子字符串的数量，然后将连续字符 $1$ 的数量清零。遍历结束后，如果连续字符 $1$ 的数量大于零，则还有最后一个只包含字符 $1$ 的最长子字符串，因此还需要计算其对应的子字符串的数量。
###Java
class Solution {
public int numSub(String s) {
final int MODULO = 1000000007;
long total = 0;
int length = s.length();
long consecutive = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return (int) total;
}
}
###C++
class Solution {
public:
static constexpr int P = int(1E9) + 7;
int numSub(string s) {
int p = 0;
long long ans = 0;
while (p < s.size()) {
if (s[p] == '0') {
++p;
continue;
}
int cnt = 0;
while (p < s.size() && s[p] == '1') {
++cnt;
++p;
}
ans = ans + (1LL + (long long)cnt) * cnt / 2;
ans = ans % P;
}
return ans;
}
};
###Python
class Solution:
def numSub(self, s: str) -> int:
total, consecutive = 0, 0
length = len(s)
for i in range(length):
if s[i] == '0':
total += consecutive * (consecutive + 1) // 2
consecutive = 0
else:
consecutive += 1
total += consecutive * (consecutive + 1) // 2
total %= (10**9 + 7)
return total
###C#
public class Solution {
public int NumSub(string s) {
const int MODULO = 1000000007;
long total = 0;
long consecutive = 0;
foreach (char c in s) {
if (c == '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return (int)total;
}
}
###Go
func numSub(s string) int {
const MODULO = 1000000007
total := 0
consecutive := 0
for _, c := range s {
if c == '0' {
total += consecutive * (consecutive + 1) / 2
total %= MODULO
consecutive = 0
} else {
consecutive++
}
}
total += consecutive * (consecutive + 1) / 2
total %= MODULO
return total
}
###C
int numSub(char * s) {
const int MODULO = 1000000007;
long total = 0;
long consecutive = 0;
for (int i = 0; s[i]; i++) {
if (s[i] == '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return (int)total;
}
###JavaScript
var numSub = function(s) {
const MODULO = 1000000007;
let total = 0;
let consecutive = 0;
for (const c of s) {
if (c === '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return total;
};
###TypeScript
function numSub(s: string): number {
const MODULO = 1000000007;
let total = 0;
let consecutive = 0;
for (const c of s) {
if (c === '0') {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive++;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
return total;
}
###Rust
impl Solution {
pub fn num_sub(s: String) -> i32 {
const MODULO: i64 = 1000000007;
let mut total: i64 = 0;
let mut consecutive: i64 = 0;
for c in s.chars() {
if c == '0' {
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
consecutive = 0;
} else {
consecutive += 1;
}
}
total += consecutive * (consecutive + 1) / 2;
total %= MODULO;
total as i32
}
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。需要遍历字符串一次。
空间复杂度：$O(1)$。只需要维护有限的变量，空间复杂度是常数。
给你一个二进制字符串 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
