两种方法：BFS / 数学（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年8月31日 10:29

方法一：BFS

做法和 2612. 最少翻转操作数是类似的，请先阅读我的题解。

设 $s$ 的长度为 $n$，其中有 $z$ 个 $0$。

翻转一次后，$s$ 有多少个 $0$？$z$ 可以变成什么数？

设翻转了 $x$ 个 $0$，那么也同时翻转了 $k-x$ 个 $1$，这些 $1$ 变成了 $0$。

所以 $z$ 减少了 $x$，然后又增加了 $k-x$。

所以新的 $z'$ 为

$$
z' = z - x + (k-x) = z+k-2x
$$

$x$ 最大可以是 $k$，但这不能超过 $s$ 中的 $0$ 的个数 $z$，所以 $x$ 最大为 $\min(k,z)$。

$k-x$ 最大可以是 $k$，但这不能超过 $s$ 中的 $1$ 的个数 $n-z$，所以 $k-x$ 最大为 $\min(k,n-z)$，所以 $x$ 最小为 $\max(0,k-n+z)$。

所以 $x$ 的范围为

$$
[\max(0,k-n+z),\min(k,z)]
$$

其余逻辑同 2612 题。

###py

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n = len(s)
        not_vis = [SortedList(range(0, n + 1, 2)), SortedList(range(1, n + 1, 2))]
        not_vis[0].add(n + 1)  # 哨兵，下面 sl[idx] <= mx 无需判断越界
        not_vis[1].add(n + 1)

        start = s.count('0')  # 起点
        not_vis[start % 2].discard(start)
        q = [start]
        ans = 0
        while q:
            tmp = q
            q = []
            for z in tmp:
                if z == 0:  # 没有 0，翻转完毕
                    return ans
                # not_vis[mn % 2] 中的从 mn 到 mx 都可以从 z 翻转到
                mn = z + k - 2 * min(k, z)
                mx = z + k - 2 * max(0, k - n + z)
                sl = not_vis[mn % 2]
                idx = sl.bisect_left(mn)
                while sl[idx] <= mx:
                    j = sl.pop(idx)  # 注意 pop(idx) 会使后续元素向左移，不需要写 idx += 1
                    q.append(j)
            ans += 1
        return -1

###java

class Solution {
    public int minOperations(String s, int k) {
        int n = s.length();
        TreeSet<Integer>[] notVis = new TreeSet[2];
        for (int m = 0; m < 2; m++) {
            notVis[m] = new TreeSet<>();
            for (int i = m; i <= n; i += 2) {
                notVis[m].add(i);
            }
        }

        // 计算起点
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                start++;
            }
        }

        notVis[start % 2].remove(start);
        List<Integer> q = List.of(start);
        for (int ans = 0; !q.isEmpty(); ans++) {
            List<Integer> tmp = q;
            q = new ArrayList<>();
            for (int z : tmp) {
                if (z == 0) { // 没有 0，翻转完毕
                    return ans;
                }
                // notVis[mn % 2] 中的从 mn 到 mx 都可以从 z 翻转到
                int mn = z + k - 2 * Math.min(k, z);
                int mx = z + k - 2 * Math.max(0, k - n + z);
                TreeSet<Integer> set = notVis[mn % 2];
                for (Iterator<Integer> it = set.tailSet(mn).iterator(); it.hasNext(); it.remove()) {
                    int j = it.next();
                    if (j > mx) {
                        break;
                    }
                    q.add(j);
                }
            }
        }
        return -1;
    }
}

###cpp

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size();
        set<int> not_vis[2];
        for (int m = 0; m < 2; m++) {
            for (int i = m; i <= n; i += 2) {
                not_vis[m].insert(i);
            }
            not_vis[m].insert(n + 1); // 哨兵，下面无需判断 it != st.end()
        }

        int start = ranges::count(s, '0'); // 起点
        not_vis[start % 2].erase(start);
        vector<int> q = {start};
        for (int ans = 0; !q.empty(); ans++) {
            vector<int> nxt;
            for (int z : q) {
                if (z == 0) { // 没有 0，翻转完毕
                    return ans;
                }
                // not_vis[mn % 2] 中的从 mn 到 mx 都可以从 z 翻转到
                int mn = z + k - 2 * min(k, z);
                int mx = z + k - 2 * max(0, k - n + z);
                auto& st = not_vis[mn % 2];
                for (auto it = st.lower_bound(mn); *it <= mx; it = st.erase(it)) {
                    nxt.push_back(*it);
                }
            }
            q = move(nxt);
        }
        return -1;
    }
};

###go

// import "github.com/emirpasic/gods/v2/trees/redblacktree"
func minOperations(s string, k int) (ans int) {
n := len(s)
notVis := [2]*redblacktree.Tree[int, struct{}]{}
for m := range notVis {
notVis[m] = redblacktree.New[int, struct{}]()
for i := m; i <= n; i += 2 {
notVis[m].Put(i, struct{}{})
}
notVis[m].Put(n+1, struct{}{}) // 哨兵，下面无需判断 node != nil
}

start := strings.Count(s, "0")
notVis[start%2].Remove(start)
q := []int{start}
for q != nil {
tmp := q
q = nil
for _, z := range tmp {
if z == 0 { // 没有 0，翻转完毕
return ans
}
// notVis[mn % 2] 中的从 mn 到 mx 都可以从 z 翻转到
mn := z + k - 2*min(k, z)
mx := z + k - 2*max(0, k-n+z)
t := notVis[mn%2]
for node, _ := t.Ceiling(mn); node.Key <= mx; node, _ = t.Ceiling(mn) {
q = append(q, node.Key)
t.Remove(node.Key)
}
}
ans++
}
return -1
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $s$ 的长度。$[0,n]$ 中的每个数至多入队出队各一次，每次 $\mathcal{O}(\log n)$ 时间。
空间复杂度：$\mathcal{O}(n)$。

方法二：数学

分析

设 $s$ 中有 $z$ 个 $0$，设一共操作了 $m$ 次。那么总翻转次数为 $mk$。

这 $z$ 个 $0$ 必须翻转奇数次，其余 $n-z$ 个 $1$ 必须翻转偶数次。

总翻转次数减去 $z$，剩下每个位置都必须翻转偶数次，所以

$$
mk-z\ 是偶数
$$

下面计算 $m$ 的下界。只要能证明 $m$ 可以等于下界，问题就解决了。

要想把 $z$ 个 $0$ 变成 $1$，总翻转次数至少要是 $z$，即

$$
mk\ge z
$$

即

$$
m\ge \left\lceil\dfrac{z}{k}\right\rceil
$$

除此以外，还需要满足什么要求？

情况一：m 是偶数

由于 $mk-z$ 是偶数，如果 $m$ 是偶数，那么 $z$ 也必须是偶数。

$s$ 中的每个位置至多翻转 $m$ 次。但是，对于 $s$ 中的 $0$，由于要翻转奇数次，所以至多翻转 $m-1$ 次。

所以 $s$ 中的所有位置的翻转次数的上界是 $z(m-1)+(n-z)m$，其可能等于 $mk$，也可能比 $mk$ 大（因为是上界），所以有

$$
z(m-1)+(n-z)m\ge mk
$$

解得

$$
m\ge \left\lceil\dfrac{z}{n-k}\right\rceil
$$

与

$$
m\ge \left\lceil\dfrac{z}{k}\right\rceil
$$

联立得

$$
m\ge \max\left(\left\lceil\dfrac{z}{k}\right\rceil,\left\lceil\dfrac{z}{n-k}\right\rceil\right)
$$

情况二：m 是奇数

由于 $mk-z$ 是偶数，如果 $m$ 是奇数，那么 $z$ 和 $k$ 必须同为奇数，或者同为偶数（奇偶性相同）。

$s$ 中的每个位置至多翻转 $m$ 次。但是，对于 $s$ 中的 $1$，由于要翻转偶数次，所以至多翻转 $m-1$ 次。

所以 $s$ 中的所有位置的翻转次数的上界是 $zm+(n-z)(m-1)$，其可能等于 $mk$，也可能比 $mk$ 大（因为是上界），所以有

$$
zm+(n-z)(m-1)\ge mk
$$

解得

$$
m\ge \left\lceil\dfrac{n-z}{n-k}\right\rceil
$$

与

$$
m\ge \left\lceil\dfrac{z}{k}\right\rceil
$$

联立得

$$
m\ge \max\left(\left\lceil\dfrac{z}{k}\right\rceil,\left\lceil\dfrac{n-z}{n-k}\right\rceil\right)
$$

情况一和情况二取最小值。

如果两个情况都不满足要求，返回 $-1$。

下界可以取到

这可以用 Gale-Ryser 定理证明。

具体来说，我们需要判断是否存在一个 $m$ 行 $n$ 列的 $0\text{-}1$ 矩阵 $M$，第 $i$ 行对应着第 $i$ 次操作，其中 $M_{i,j} = 0$ 表示没有翻转 $s_j$，$M_{i,j} = 1$ 表示翻转 $s_j$。每一行的元素和都是 $k$，第 $j$ 列的元素和是 $s_j$ 的翻转次数 $a_j$。由于 $a_j\le m$ 且 $\sum\limits_{j} a_j\le mk$，由 Gale-Ryser 定理可得，这样的矩阵是存在的。

特殊情况

如果 $z=0$，那么无需操作，答案是 $0$。

由于下界公式中的分母 $n-k$ 不能为 $0$，我们需要特判 $n=k$ 的情况，此时每次操作只能翻转整个 $s$。

如果 $z=n$，即 $s$ 全为 $0$，那么只需操作 $1$ 次。
否则无论怎么操作，$s$ 中始终有 $0$，返回 $-1$。

上取整转成下取整

关于上取整的计算，当 $a$ 为非负整数，$b$ 为正整数时，有恒等式

$$
\left\lceil\dfrac{a}{b}\right\rceil = \left\lfloor\dfrac{a+b-1}{b}\right\rfloor
$$

证明见上取整下取整转换公式的证明。

###py

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n = len(s)
        z = s.count('0')
        if z == 0:
            return 0
        if k == n:
            return 1 if z == n else -1

        ans = inf
        # 情况一：操作次数 m 是偶数
        if z % 2 == 0:  # z 必须是偶数
            m = max((z + k - 1) // k, (z + n - k - 1) // (n - k))  # 下界
            ans = m + m % 2  # 把 m 往上调整为偶数

        # 情况二：操作次数 m 是奇数
        if z % 2 == k % 2:  # z 和 k 的奇偶性必须相同
            m = max((z + k - 1) // k, (n - z + n - k - 1) // (n - k))  # 下界
            ans = min(ans, m | 1)  # 把 m 往上调整为奇数

        return ans if ans < inf else -1

###java

class Solution {
    public int minOperations(String s, int k) {
        int n = s.length();
        int z = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                z++;
            }
        }

        if (z == 0) {
            return 0;
        }
        if (k == n) {
            return z == n ? 1 : -1;
        }

        int ans = Integer.MAX_VALUE;
        // 情况一：操作次数 m 是偶数
        if (z % 2 == 0) { // z 必须是偶数
            int m = Math.max((z + k - 1) / k, (z + n - k - 1) / (n - k)); // 下界
            ans = m + m % 2; // 把 m 往上调整为偶数
        }

        // 情况二：操作次数 m 是奇数
        if (z % 2 == k % 2) { // z 和 k 的奇偶性必须相同
            int m = Math.max((z + k - 1) / k, (n - z + n - k - 1) / (n - k)); // 下界
            ans = Math.min(ans, m | 1); // 把 m 往上调整为奇数
        }

        return ans < Integer.MAX_VALUE ? ans : -1;
    }
}

###cpp

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size();
        int z = ranges::count(s, '0');
        if (z == 0) {
            return 0;
        }
        if (k == n) {
            return z == n ? 1 : -1;
        }

        int ans = INT_MAX;
        // 情况一：操作次数 m 是偶数
        if (z % 2 == 0) { // z 必须是偶数
            int m = max((z + k - 1) / k, (z + n - k - 1) / (n - k)); // 下界
            ans = m + m % 2; // 把 m 往上调整为偶数
        }

        // 情况二：操作次数 m 是奇数
        if (z % 2 == k % 2) { // z 和 k 的奇偶性必须相同
            int m = max((z + k - 1) / k, (n - z + n - k - 1) / (n - k)); // 下界
            ans = min(ans, m | 1); // 把 m 往上调整为奇数
        }

        return ans < INT_MAX ? ans : -1;
    }
};

###go

func minOperations(s string, k int) int {
n := len(s)
z := strings.Count(s, "0")
if z == 0 {
return 0
}
if k == n {
if z == n {
return 1
}
return -1
}

ans := math.MaxInt
// 情况一：操作次数 m 是偶数
if z%2 == 0 { // z 必须是偶数
m := max((z+k-1)/k, (z+n-k-1)/(n-k)) // 下界
ans = m + m%2 // 把 m 往上调整为偶数
}

// 情况二：操作次数 m 是奇数
if z%2 == k%2 { // z 和 k 的奇偶性必须相同
m := max((z+k-1)/k, (n-z+n-k-1)/(n-k)) // 下界
ans = min(ans, m|1) // 把 m 往上调整为奇数
}

if ans < math.MaxInt {
return ans
}
return -1
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。瓶颈在遍历 $s$ 上。如果已知 $s$ 中的 $0$ 的个数，则时间复杂度是 $\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
简单题，简单做（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年11月7日 10:29

简单题，简单做（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年11月7日 10:29

双关键字排序。对于 $\textit{arr}$ 中的两个数：

先比较二者的二进制 $1$ 的个数是否相同，若不同，$1$ 的个数少的排前面。
若二进制 $1$ 的个数相同，那么数值小的排前面。

###py

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        arr.sort(key=lambda x: (x.bit_count(), x))
        return arr

###java

class Solution {
    public int[] sortByBits(int[] arr) {
        return IntStream.of(arr)
                .boxed()
                .sorted((a, b) -> {
                    int ca = Integer.bitCount(a);
                    int cb = Integer.bitCount(b);
                    return ca != cb ? ca - cb : a - b;
                })
                .mapToInt(a -> a)
                .toArray();
    }
}

###java

class Solution {
    public int[] sortByBits(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.bitCount(arr[i]) << 16 | arr[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            arr[i] &= 0xffff;
        }
        return arr;
    }
}

###cpp

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        ranges::sort(arr, {}, [](int x) {
            return pair(popcount((uint32_t) x), x);
        });
        return arr;
    }
};

###c

int cmp(const void* a, const void* b) {
    int x = *(int*)a, y = *(int*)b;
    int cx = __builtin_popcount(x), cy = __builtin_popcount(y);
    return cx != cy ? cx - cy : x - y;
}

int* sortByBits(int* arr, int arrSize, int* returnSize) {
    qsort(arr, arrSize, sizeof(int), cmp);
    *returnSize = arrSize;
    return arr;
}

###go

func sortByBits(arr []int) []int {
slices.SortFunc(arr, func(a, b int) int {
return cmp.Or(bits.OnesCount(uint(a))-bits.OnesCount(uint(b)), a-b)
})
return arr
}

###js

var sortByBits = function(arr) {
    return arr.sort((a, b) => bitCount32(a) - bitCount32(b) || a - b);
};

// 参考 Java 的 Integer.bitCount
function bitCount32(i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

###rust

impl Solution {
    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
        arr.sort_unstable_by_key(|&x| (x.count_ones(), x));
        arr
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{arr}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。忽略排序的栈开销。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
两种 DFS 写法（Python/Java/C++/Go）endlesscheng
2026年2月24日 08:25

两种 DFS 写法（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月24日 08:25

从大家熟悉的十进制说起。如何把路径 $1\to 2\to 3$ 变成十进制数 $123$？过程如下：

$$
0\xrightarrow{\times 10 + 1}1\xrightarrow{\times 10 + 2} 12\xrightarrow{\times 10 + 3}123
$$

二进制的做法类似。例如把路径 $1\to 0\to 1\to 1$ 变成二进制数 $1011$，过程如下：

$$
0\xrightarrow{\times 2 + 1}1\xrightarrow{\times 2 + 0} 10\xrightarrow{\times 2 + 1}101\xrightarrow{\times 2 + 1}1011
$$

其中 $\times 2$ 等价于左移一位，$+$ 也可以写成或运算。

我们可以对 $\textit{dfs}$ 额外添加参数 $\textit{num}$，表示在自顶向下递归的过程中，当前数字是 $\textit{num}$。每访问到一个新的节点 $\textit{node}$，就把 $\textit{num}$ 更新成 num << 1 | node.val。

如果 $\textit{node}$ 是叶子节点，把 $\textit{num}$ 加到答案中。

写法一

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        # 从根到 node（不含）的路径值为 num
        def dfs(node: Optional[TreeNode], num: int) -> None:
            nonlocal ans
            if node is None:
                return
            num = num << 1 | node.val
            if node.left is None and node.right is None:
                ans += num
                return
            dfs(node.left, num)
            dfs(node.right, num)

        ans = 0
        dfs(root, 0)
        return ans

class Solution {
    private int ans = 0;

    public int sumRootToLeaf(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    // 从根到 node（不含）的路径值为 num
    private void dfs(TreeNode node, int num) {
        if (node == null) {
            return;
        }
        num = num << 1 | node.val;
        if (node.left == null && node.right == null) {
            ans += num;
            return;
        }
        dfs(node.left, num);
        dfs(node.right, num);
    }
}

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int ans = 0;

        // 从根到 node（不含）的路径值为 num
        auto dfs = [&](this auto&& dfs, TreeNode* node, int num) -> void {
            if (node == nullptr) {
                return;
            }
            num = num << 1 | node->val;
            if (node->left == nullptr && node->right == nullptr) {
                ans += num;
                return;
            }
            dfs(node->left, num);
            dfs(node->right, num);
        };

        dfs(root, 0);
        return ans;
    }
};

func sumRootToLeaf(root *TreeNode) (ans int) {
// 从根到 node（不含）的路径值为 num
var dfs func(*TreeNode, int)
dfs = func(node *TreeNode, num int) {
if node == nil {
return
}
num = num<<1 | node.Val
if node.Left == nil && node.Right == nil {
ans += num
return
}
dfs(node.Left, num)
dfs(node.Right, num)
}
dfs(root, 0)
return
}

写法二

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], num: int) -> int:
            if node is None:
                return 0
            num = num << 1 | node.val
            if node.left is None and node.right is None:
                return num
            return dfs(node.left, num) + dfs(node.right, num)

        return dfs(root, 0)

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }
        num = num << 1 | node.val;
        if (node.left == null && node.right == null) {
            return num;
        }
        return dfs(node.left, num) + dfs(node.right, num);
    }
}

class Solution {
    int dfs(TreeNode* node, int num) {
        if (node == nullptr) {
            return 0;
        }
        num = num << 1 | node->val;
        if (node->left == nullptr && node->right == nullptr) {
            return num;
        }
        return dfs(node->left, num) + dfs(node->right, num);
    }

public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
};

func dfs(node *TreeNode, num int) int {
if node == nil {
return 0
}
num = num<<1 | node.Val
if node.Left == nil && node.Right == nil {
return num
}
return dfs(node.Left, num) + dfs(node.Right, num)
}

func sumRootToLeaf(root *TreeNode) int {
return dfs(root, 0)
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是二叉树的节点个数。
空间复杂度：$\mathcal{O}(h)$，其中 $h$ 是二叉树的高度。递归需要 $\mathcal{O}(h)$ 的栈开销。

专题训练

见下面树题单的「§2.2 自顶向下 DFS」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
两种方法：暴力 / 位运算（Python/Java/C++/Go）endlesscheng
2026年2月14日 10:45

两种方法：暴力 / 位运算（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月14日 10:45

方法一：暴力

暴力枚举所有长为 $k$ 的子串，保存到一个哈希集合中。

如果最终哈希集合的大小恰好等于 $2^k$，那么说明所有长为 $k$ 的二进制串都在 $s$ 中。

###py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        st = {s[i - k: i] for i in range(k, len(s) + 1)}
        return len(st) == 1 << k

###java

class Solution {
    public boolean hasAllCodes(String s, int k) {
        Set<String> set = new HashSet<>();
        for (int i = k; i <= s.length(); i++) {
            set.add(s.substring(i - k, i));
        }
        return set.size() == (1 << k);
    }
}

###cpp

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        unordered_set<string> st;
        for (int i = k; i <= s.size(); i++) {
            st.insert(s.substr(i - k, k));
        }
        return st.size() == (1 << k);
    }
};

###go

func hasAllCodes(s string, k int) bool {
set := map[string]struct{}{}
for i := k; i <= len(s); i++ {
set[s[i-k:i]] = struct{}{}
}
return len(set) == 1<<k
}

复杂度分析

时间复杂度：$\mathcal{O}((n-k)k)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}((n-k)k)$。

方法二：位运算滑窗

把子串转成整数，保存到哈希集合或者布尔数组中。

小优化：如果循环过程中发现已经找到 $2^k$ 个不同的二进制数，可以提前返回 $\texttt{true}$。

###py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        MASK = (1 << k) - 1
        st = set()  # 更快的写法见另一份代码【Python3 列表】
        x = 0
        for i, ch in enumerate(s):
            # 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch
            # &MASK 目的是去掉超出 k 的比特位
            x = (x << 1 & MASK) | int(ch)
            if i >= k - 1:
                st.add(x)
        return len(st) == 1 << k

###py

class Solution:
    def hasAllCodes(self, s: str, k: int) -> bool:
        MASK = (1 << k) - 1
        has = [False] * (1 << k)
        cnt = x = 0
        for i, ch in enumerate(s):
            # 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch
            # &MASK 目的是去掉超出 k 的比特位
            x = (x << 1 & MASK) | int(ch)
            if i < k - 1 or has[x]:
                continue
            has[x] = True
            cnt += 1
            if cnt == 1 << k:
                return True
        return False

###java

class Solution {
    public boolean hasAllCodes(String s, int k) {
        final int MASK = (1 << k) - 1;
        boolean[] has = new boolean[1 << k];
        int cnt = 0;
        int x = 0;
        for (int i = 0; i < s.length() && cnt < (1 << k); i++) {
            char ch = s.charAt(i);
            // 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch&1
            // &MASK 目的是去掉超出 k 的比特位
            x = (x << 1 & MASK) | (ch & 1);
            if (i >= k - 1 && !has[x]) {
                has[x] = true;
                cnt++;
            }
        }
        return cnt == (1 << k);
    }
}

###cpp

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        const int MASK = (1 << k) - 1;
        vector<int8_t> has(1 << k);
        int cnt = 0;
        int x = 0;
        for (int i = 0; i < s.size() && cnt < (1 << k); i++) {
            // 把 s[i] 加到 x 的末尾：x 整体左移一位，然后或上 s[i]&1
            // &MASK 目的是去掉超出 k 的比特位
            x = (x << 1 & MASK) | (s[i] & 1);
            if (i >= k - 1 && !has[x]) {
                has[x] = true;
                cnt++;
            }
        }
        return cnt == (1 << k);
    }
};

###go

func hasAllCodes(s string, k int) bool {
has := make([]bool, 1<<k)
cnt := 0
mask := 1<<k - 1
x := 0
for i, ch := range s {
// 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch&1
// &mask 目的是去掉超出 k 的比特位
x = x<<1&mask | int(ch&1)
if i < k-1 || has[x] {
continue
}
has[x] = true
cnt++
if cnt == 1<<k {
return true
}
}
return false
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(n-k)$ 或 $\mathcal{O}(2^k)$，取决于实现。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
计算尾零个数（Python/Java/C++/Go/C/JS/Rust）endlesscheng
2026年2月22日 07:15

计算尾零个数（Python/Java/C++/Go/C/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月22日 07:15

以 $n = 1010010$ 为例。从右往左，我们需要计算 $1001$ 的间距 $3$，以及 $101$ 的间距 $2$：

去掉 $n$ 末尾的 $10$，得到 $10100$。这一步可以先计算出 $n$ 的 $\text{lowbit} = 10$，然后把 $n$ 更新成 $\dfrac{n}{2\cdot \text{lowbit}}$。$\text{lowbit}$ 的原理请看从集合论到位运算，常见位运算技巧分类总结。
计算 $10100$ 的尾零个数加一，得到 $3$，即 $1001$ 的间距。然后把 $10100$ 右移 $3$ 位，得到 $10$。
计算 $10$ 的尾零个数加一，得到 $2$，即 $101$ 的间距。然后把 $101$ 右移 $2$ 位，得到 $0$。算法结束。

class Solution:
    def binaryGap(self, n: int) -> int:
        ans = 0
        n //= (n & -n) * 2  # 去掉 n 末尾的 100..0
        while n > 0:
            gap = (n & -n).bit_length()  # n 的尾零个数加一
            ans = max(ans, gap)
            n >>= gap  # 去掉 n 末尾的 100..0
        return ans

class Solution {
    public int binaryGap(int n) {
        int ans = 0;
        n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
        while (n > 0) {
            int gap = Integer.numberOfTrailingZeros(n) + 1;
            ans = Math.max(ans, gap);
            n >>= gap; // 去掉 n 末尾的 100..0
        }
        return ans;
    }
}

class Solution {
public:
    int binaryGap(int n) {
        int ans = 0;
        n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
        while (n > 0) {
            int gap = countr_zero((uint32_t) n) + 1;
            ans = max(ans, gap);
            n >>= gap; // 去掉 n 末尾的 100..0
        }
        return ans;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int binaryGap(int n) {
    int ans = 0;
    n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
    while (n > 0) {
        int gap = __builtin_ctz(n) + 1;
        ans = MAX(ans, gap);
        n >>= gap; // 去掉 n 末尾的 100..0
    }
    return ans;
}

func binaryGap(n int) (ans int) {
n /= n & -n * 2 // 去掉 n 末尾的 100..0
for n > 0 {
gap := bits.TrailingZeros(uint(n)) + 1
ans = max(ans, gap)
n >>= gap // 去掉 n 末尾的 100..0
}
return
}

var binaryGap = function(n) {
    let ans = 0;
    n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
    while (n > 0) {
        const gap = 32 - Math.clz32(n & -n); // n 的尾零个数加一
        ans = Math.max(ans, gap);
        n >>= gap; // 去掉 n 末尾的 100..0
    }
    return ans;
};

impl Solution {
    pub fn binary_gap(mut n: i32) -> i32 {
        let mut ans = 0;
        n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
        while n > 0 {
            let gap = n.trailing_zeros() + 1;
            ans = ans.max(gap);
            n >>= gap; // 去掉 n 末尾的 100..0
        }
        ans as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(k)$，其中 $k$ 是 $n$ 二进制中的 $1$ 的个数。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面位运算题单的「一、基础题」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
三种方法：暴力枚举 / 数位 DP / 组合数学（Python/Java/C++/Go）endlesscheng
2026年2月21日 08:25

三种方法：暴力枚举 / 数位 DP / 组合数学（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月21日 08:25

方法一：暴力枚举

枚举 $[\textit{left},\textit{right}]$ 中的整数 $x$，计算 $x$ 二进制中的 $1$ 的个数 $c$。如果 $c$ 是质数，那么答案增加一。

由于 $[1,10^6]$ 中的二进制数至多有 $19$ 个 $1$，所以只需 $19$ 以内的质数，即

$$
2, 3, 5, 7, 11, 13, 17, 19
$$

primes = {2, 3, 5, 7, 11, 13, 17, 19}

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        ans = 0
        for x in range(left, right + 1):
            if x.bit_count() in primes:
                ans += 1
        return ans

class Solution {
    private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);

    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; x++) {
            if (primes.contains(Integer.bitCount(x))) {
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
    // 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
    static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};

public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (uint32_t x = left; x <= right; x++) {
            if (ranges::contains(primes, popcount(x))) {
                ans++;
            }
        }
        return ans;
    }
};

// 注：也可以用哈希集合做，由于本题质数很少，用 slice 也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}

func countPrimeSetBits(left, right int) (ans int) {
for x := left; x <= right; x++ {
if slices.Contains(primes, bits.OnesCount(uint(x))) {
ans++
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(\textit{right}-\textit{left})$。
空间复杂度：$\mathcal{O}(1)$。不计入质数集合的空间。

方法二：上下界数位 DP

数位 DP v1.0 模板讲解

数位 DP v2.0 模板讲解（上下界数位 DP）

对于本题，在递归边界（$i=n$）我们需要判断是否填了质数个 $1$，所以需要参数 $\textit{cnt}_1$ 表示填过的 $1$ 的个数。其余同 v2.0 模板。

primes = {2, 3, 5, 7, 11, 13, 17, 19}

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        high_s = list(map(int, bin(right)[2:]))  # 避免在 dfs 中频繁调用 int()
        n = len(high_s)
        low_s = list(map(int, bin(left)[2:].zfill(n)))  # 添加前导零，长度和 high_s 对齐

        # 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
        @cache  # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
        def dfs(i: int, cnt1: int, limit_low: bool, limit_high: bool) -> int:
            if i == n:
                return 1 if cnt1 in primes else 0

            lo = low_s[i] if limit_low else 0
            hi = high_s[i] if limit_high else 1

            res = 0
            for d in range(lo, hi + 1):
                res += dfs(i + 1, cnt1 + d, limit_low and d == lo, limit_high and d == hi)
            return res

        return dfs(0, 0, True, True)

class Solution {
    private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);

    public int countPrimeSetBits(int left, int right) {
        int n = 32 - Integer.numberOfLeadingZeros(right);
        int[][] memo = new int[n][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(n - 1, 0, true, true, left, right, memo);
    }

    // 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
    private int dfs(int i, int cnt1, boolean limitLow, boolean limitHigh, int left, int right, int[][] memo) {
        if (i < 0) {
            return primes.contains(cnt1) ? 1 : 0;
        }
        if (!limitLow && !limitHigh && memo[i][cnt1] != -1) {
            return memo[i][cnt1];
        }

        int lo = limitLow ? left >> i & 1 : 0;
        int hi = limitHigh ? right >> i & 1 : 1;

        int res = 0;
        for (int d = lo; d <= hi; d++) {
            res += dfs(i - 1, cnt1 + d, limitLow && d == lo, limitHigh && d == hi, left, right, memo);
        }

        if (!limitLow && !limitHigh) {
            memo[i][cnt1] = res;
        }
        return res;
    }
}

class Solution {
    // 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
    static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};

public:
    int countPrimeSetBits(int left, int right) {
        int n = bit_width((uint32_t) right);
        vector memo(n, vector<int>(n + 1, -1));

        // 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
        auto dfs = [&](this auto&& dfs, int i, int cnt1, bool limit_low, bool limit_high) -> int {
            if (i < 0) {
                return ranges::contains(primes, cnt1);
            }
            if (!limit_low && !limit_high && memo[i][cnt1] != -1) {
                return memo[i][cnt1];
            }

            int lo = limit_low ? left >> i & 1 : 0;
            int hi = limit_high ? right >> i & 1 : 1;

            int res = 0;
            for (int d = lo; d <= hi; d++) {
                res += dfs(i - 1, cnt1 + d, limit_low && d == lo, limit_high && d == hi);
            }

            if (!limit_low && !limit_high) {
                memo[i][cnt1] = res;
            }
            return res;
        };

        return dfs(n - 1, 0, true, true);
    }
};

// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}

func countPrimeSetBits(left int, right int) int {
n := bits.Len(uint(right))
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}

// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
var dfs func(int, int, bool, bool) int
dfs = func(i, cnt1 int, limitLow, limitHigh bool) (res int) {
if i < 0 {
if slices.Contains(primes, cnt1) {
return 1
}
return 0
}
if !limitLow && !limitHigh {
p := &memo[i][cnt1]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}

lo := 0
if limitLow {
lo = left >> i & 1
}
hi := 1
if limitHigh {
hi = right >> i & 1
}

for d := lo; d <= hi; d++ {
res += dfs(i-1, cnt1+d, limitLow && d == lo, limitHigh && d == hi)
}
return
}

return dfs(n-1, 0, true, true)
}

复杂度分析

时间复杂度：$\mathcal{O}(\log^2 \textit{right})$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(\log^2 \textit{right})$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(\log^2 \textit{right})$。
空间复杂度：$\mathcal{O}(\log^2 \textit{right})$。保存多少状态，就需要多少空间。

方法三：组合数学

primes = [2, 3, 5, 7, 11, 13, 17, 19]

class Solution:
    def calc(self, high: int) -> int:
        # 转换成计算 < high + 1 的合法正整数个数
        # 这样转换可以方便下面的代码把 high 也算进来
        high += 1
        res = ones = 0
        for i in range(high.bit_length() - 1, -1, -1):
            if high >> i & 1 == 0:
                continue
            # 如果这一位填 0，那么后面可以随便填
            # 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
            for p in primes:
                k = p - ones  # 剩余需要填的 1 的个数
                if k > i:
                    break
                if k >= 0:
                    res += comb(i, k)
            # 这一位填 1，继续计算
            ones += 1
        return res

    def countPrimeSetBits(self, left: int, right: int) -> int:
        return self.calc(right) - self.calc(left - 1)

MX = 20
comb = [[0] * MX for _ in range(MX)]
for i in range(MX):
    comb[i][0] = 1
    for j in range(1, i + 1):
        comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]

primes = [2, 3, 5, 7, 11, 13, 17, 19]

class Solution:
    def calc(self, high: int) -> int:
        # 转换成计算 < high + 1 的合法正整数个数
        # 这样转换可以方便下面的代码把 high 也算进来
        high += 1
        res = ones = 0
        for i in range(high.bit_length() - 1, -1, -1):
            if high >> i & 1 == 0:
                continue
            # 如果这一位填 0，那么后面可以随便填
            # 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
            for p in primes:
                k = p - ones  # 剩余需要填的 1 的个数
                if k > i:
                    break
                if k >= 0:
                    res += comb[i][k]
            # 这一位填 1，继续计算
            ones += 1
        return res

    def countPrimeSetBits(self, left: int, right: int) -> int:
        return self.calc(right) - self.calc(left - 1)

class Solution {
    private static final int MX = 20;
    private static final int[][] comb = new int[MX][MX];
    private static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
    private static boolean initialized = false;

    // 这样写比 static block 快
    public Solution() {
        if (initialized) {
            return;
        }
        initialized = true;

        // 预处理组合数
        for (int i = 0; i < MX; i++) {
            comb[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
            }
        }
    }

    public int countPrimeSetBits(int left, int right) {
        return calc(right) - calc(left - 1);
    }

    private int calc(int high) {
        // 转换成计算 < high + 1 的合法正整数个数
        // 这样转换可以方便下面的代码把 high 也算进来
        high++;
        int res = 0;
        int ones = 0;
        for (int i = 31 - Integer.numberOfLeadingZeros(high); i >= 0; i--) {
            if ((high >> i & 1) == 0) {
                continue;
            }
            // 如果这一位填 0，那么后面可以随便填
            // 问题变成在 pos 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
            for (int p : primes) {
                int k = p - ones; // 剩余需要填的 1 的个数
                if (k > i) {
                    break;
                }
                if (k >= 0) {
                    res += comb[i][k];
                }
            }
            ones++; // 这一位填 1，继续计算
        }
        return res;
    }
}

constexpr int MX = 20;
int comb[MX][MX];

auto init = [] {
    // 预处理组合数
    for (int i = 0; i < MX; i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
    return 0;
}();

class Solution {
    static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};

    int calc(int high) {
        // 转换成计算 < high + 1 的合法正整数个数
        // 这样转换可以方便下面的代码把 high 也算进来
        high++;
        int res = 0, ones = 0;
        for (int i = bit_width((uint32_t) high) - 1; i >= 0; i--) {
            if ((high >> i & 1) == 0) {
                continue;
            }
            // 如果这一位填 0，那么后面可以随便填
            // 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
            for (int p : primes) {
                int k = p - ones; // 剩余需要填的 1 的个数
                if (k > i) {
                    break;
                }
                if (k >= 0) {
                    res += comb[i][k];
                }
            }
            ones++; // 这一位填 1，继续计算
        }
        return res;
    }

public:
    int countPrimeSetBits(int left, int right) {
        return calc(right) - calc(left - 1);
    }
};

const mx = 20

var comb [mx][mx]int
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}

func init() {
// 预处理组合数
for i := range comb {
comb[i][0] = 1
for j := 1; j <= i; j++ {
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
}
}
}

func calc(high int) (res int) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++
ones := 0
for i := bits.Len(uint(high)) - 1; i >= 0; i-- {
if high>>i&1 == 0 {
continue
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for _, p := range primes {
k := p - ones // 剩余需要填的 1 的个数
if k > i {
break
}
if k >= 0 {
res += comb[i][k]
}
}
// 这一位填 1，继续计算
ones++
}
return res
}

func countPrimeSetBits(left, right int) int {
return calc(right) - calc(left-1)
}

复杂度分析

不计入预处理的时间和空间。

时间复杂度：$\mathcal{O}\left(\dfrac{\log^2 \textit{right}}{\log\log \textit{right}}\right)$。循环 $\mathcal{O}(\log \textit{right})$ 次，每次循环会遍历 $\mathcal{O}(\log \textit{right})$ 以内的质数，根据质数密度，这有 $\mathcal{O}\left(\dfrac{\log \textit{right}}{\log\log \textit{right}}\right)$ 个。预处理组合数后，计算组合数的时间为 $\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

专题训练

动态规划题单的「十、数位 DP」。
数学题单的「§2.2 组合计数」。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
一次遍历，简洁写法（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年2月7日 09:22

一次遍历，简洁写法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月7日 09:22

题意：子串必须形如 $\underbrace{\texttt{0}\cdots \texttt{0}}{k\ 个\ \texttt{0}}\underbrace{\texttt{1}\cdots \texttt{1}}{k\ 个\ \texttt{1}}$ 或者 $\underbrace{\texttt{1}\cdots \texttt{1}}{k\ 个\ \texttt{1}}\underbrace{\texttt{0}\cdots \texttt{0}}{k\ 个\ \texttt{0}}$。只能有一段 $\texttt{0}$ 和一段 $\texttt{1}$，不能是 $\texttt{00111}$（两段长度不等）或者 $\texttt{010}$（超过两段）等。

例如 $s = \texttt{001110000}$，按照连续相同字符，分成三组 $\texttt{00},\texttt{111},\texttt{0000}$。

在前两组中，我们可以得到 $2$ 个合法子串：$\texttt{0011}$ 和 $\texttt{01}$。
在后两组中，我们可以得到 $3$ 个合法子串：$\texttt{111000}$、$\texttt{1100}$ 和 $\texttt{10}$。

一般地，遍历 $s$，按照连续相同字符分组，计算每一组的长度。设当前这组的长度为 $\textit{cur}$，上一组的长度为 $\textit{pre}$，那么当前这组和上一组，能得到 $\min(\textit{pre},\textit{cur})$ 个合法子串，加到答案中。

###py

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        n = len(s)
        pre = cur = ans = 0
        for i in range(n):
            cur += 1
            if i == n - 1 or s[i] != s[i + 1]:
                # 遍历到了这一组的末尾
                ans += min(pre, cur)
                pre = cur
                cur = 0
        return ans

###java

class Solution {
    public int countBinarySubstrings(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int pre = 0;
        int cur = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            cur++;
            if (i == n - 1 || s[i] != s[i + 1]) {
                // 遍历到了这一组的末尾
                ans += Math.min(pre, cur);
                pre = cur;
                cur = 0;
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int countBinarySubstrings(string s) {
        int n = s.size();
        int pre = 0, cur = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            cur++;
            if (i == n - 1 || s[i] != s[i + 1]) {
                // 遍历到了这一组的末尾
                ans += min(pre, cur);
                pre = cur;
                cur = 0;
            }
        }
        return ans;
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))

int countBinarySubstrings(char* s) {
    int pre = 0, cur = 0, ans = 0;
    for (int i = 0; s[i]; i++) {
        cur++;
        if (s[i] != s[i + 1]) {
            // 遍历到了这一组的末尾
            ans += MIN(pre, cur);
            pre = cur;
            cur = 0;
        }
    }
    return ans;
}

###go

func countBinarySubstrings(s string) (ans int) {
n := len(s)
pre, cur := 0, 0
for i := range n {
cur++
if i == n-1 || s[i] != s[i+1] {
// 遍历到了这一组的末尾
ans += min(pre, cur)
pre = cur
cur = 0
}
}
return
}

###js

var countBinarySubstrings = function(s) {
    const n = s.length;
    let pre = 0, cur = 0, ans = 0;
    for (let i = 0; i < n; i++) {
        cur++;
        if (i === n - 1 || s[i] !== s[i + 1]) {
            // 遍历到了这一组的末尾
            ans += Math.min(pre, cur);
            pre = cur;
            cur = 0;
        }
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_binary_substrings(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        let mut pre = 0;
        let mut cur = 0;
        let mut ans = 0;
        for i in 0..n {
            cur += 1;
            if i == n - 1 || s[i] != s[i + 1] {
                // 遍历到了这一组的末尾
                ans += pre.min(cur);
                pre = cur;
                cur = 0;
            }
        }
        ans
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面双指针题单的「六、分组循环」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
O(1) 做法原理讲解（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年2月18日 08:26

O(1) 做法原理讲解（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月18日 08:26

为了做到 $\mathcal{O}(1)$ 时间，我们需要快速判断所有相邻比特位是否都不同。

如何判断不同？用哪个位运算最合适？

用异或运算最合适。对于单个比特的异或，如果两个数不同，那么结果是 $1$；如果两个数相同，那么结果是 $0$。

如何对所有相邻比特位做异或运算？

例如 $n = 10101$，可以把 $n$ 右移一位，得到 $01010$，再与 $10101$ 做异或运算，计算的就是相邻比特位的异或值了。

如果异或结果全为 $1$，就说明所有相邻比特位都不同。

如何判断一个二进制数全为 $1$？

这相当于判断二进制数加一后，是否为 231. 2 的幂。

设 $x$ 为 (n >> 1) ^ n，如果 (x + 1) & x 等于 $0$，那么说明 $x$ 全为 $1$。

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        x = (n >> 1) ^ n
        return (x + 1) & x == 0

class Solution {
    public boolean hasAlternatingBits(int n) {
        int x = (n >> 1) ^ n;
        return ((x + 1) & x) == 0;
    }
}

class Solution {
public:
    bool hasAlternatingBits(int n) {
        uint32_t x = (n >> 1) ^ n;
        return ((x + 1) & x) == 0;
    }
};

bool hasAlternatingBits(int n) {
    uint32_t x = (n >> 1) ^ n;
    return ((x + 1) & x) == 0;
}

func hasAlternatingBits(n int) bool {
x := n>>1 ^ n
return (x+1)&x == 0
}

var hasAlternatingBits = function(n) {
    const x = (n >> 1) ^ n;
    return ((x + 1) & x) === 0;
};

impl Solution {
    pub fn has_alternating_bits(n: i32) -> bool {
        let x = (n >> 1) ^ n;
        (x + 1) & x == 0
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面位运算题单的「一、基础题」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

简单题，简单做（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月17日 07:29

枚举小时 $h=0,1,2,\ldots,11$ 以及分钟 $m=0,1,2,\ldots,59$。如果 $h$ 二进制中的 $1$ 的个数加上 $m$ 二进制中的 $1$ 的个数恰好等于 $\textit{turnedOn}$，那么把 $h:m$ 添加到答案中。

注意如果 $m$ 是个位数，需要添加一个前导零。

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        ans = []
        for h in range(12):
            for m in range(60):
                if h.bit_count() + m.bit_count() == turnedOn:
                    ans.append(f"{h}:{m:02d}")
        return ans

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> ans = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        char s[6];
        for (uint8_t h = 0; h < 12; h++) {
            for (uint8_t m = 0; m < 60; m++) {
                if (popcount(h) + popcount(m) == turnedOn) {
                    sprintf(s, "%d:%02d", h, m);
                    ans.emplace_back(s);
                }
            }
        }
        return ans;
    }
};

func readBinaryWatch(turnedOn int) (ans []string) {
    for h := range 12 {
        for m := range 60 {
            if bits.OnesCount8(uint8(h))+bits.OnesCount8(uint8(m)) == turnedOn {
                ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return
}

复杂度分析

时间复杂度：$\mathcal{O}(1)$。
空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
O(1) 位运算分治，原理讲解（Python/Java/C++/Go）endlesscheng
2026年2月12日 09:58

O(1) 位运算分治，原理讲解（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月12日 09:58

以反转一个 $8$ 位整数为例。

为方便阅读，我把这个数字记作 $12345678$。目标是得到 $87654321$。

用分治思考，反转 $12345678$ 可以分成如下三步：

递归反转左半 $1234$，得到 $4321$。
递归反转右半 $5678$，得到 $8765$。
交换 $4321$ 和 $8765$，得到 $87654321$。

反转 $1234$ 可以拆分为反转 $12$ 和 $34$，反转 $5678$ 可以拆分为反转 $56$ 和 $78$。

对于 $12$ 这种长为 $2$ 的情况，交换 $1$ 和 $2$ 即可完成反转。

无法加载 SVG 图片，请在网页上查看

你可能会问：这样做，算法能更快吗？

利用位运算「并行计算」的特点，我们可以高效地实现上述过程。

去掉递归的「递」，直接看「归」的过程（自底向上）。

递归的最底层是反转 $12$，反转 $34$，反转 $56$，反转 $78$。利用位运算，这些反转可以同时完成：

$$
\begin{array}{c}
\text{12345678} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{1\phantom{2}3\phantom{4}5\phantom{6}7\phantom{8}} \
\text{\phantom{1}2\phantom{3}4\phantom{5}6\phantom{7}8} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{2}1\phantom{2}3\phantom{4}5\phantom{6}7} \
\text{2\phantom{3}4\phantom{5}6\phantom{7}8\phantom{7}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{21436587} \
\end{array}
$$

然后两个两个交换：

$$
\begin{array}{c}
\text{21436587} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{21\phantom{11}65\phantom{11}} \
\text{\phantom{11}43\phantom{11}87} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{11}21\phantom{11}65} \
\text{43\phantom{11}87\phantom{11}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{43218765} \
\end{array}
$$

然后四个四个交换：

$$
\begin{array}{c}
\text{43218765} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{4321\phantom{1111}} \
\text{\phantom{1111}8765} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{1111}4321} \
\text{8765\phantom{1111}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{87654321} \
\end{array}
$$

依此类推。

对于 $32$ 位整数，还需要执行八个八个交换，最后把高低 $16$ 位交换。

m0 = 0x55555555  # 01010101 ...
m1 = 0x33333333  # 00110011 ...
m2 = 0x0f0f0f0f  # 00001111 ...
m3 = 0x00ff00ff  # 00000000111111110000000011111111
m4 = 0x0000ffff  # 00000000000000001111111111111111

class Solution:
    def reverseBits(self, n: int) -> int:
        n = n>>1&m0 | (n&m0)<<1  # 交换相邻位
        n = n>>2&m1 | (n&m1)<<2  # 两个两个交换
        n = n>>4&m2 | (n&m2)<<4  # 四个四个交换
        n = n>>8&m3 | (n&m3)<<8  # 八个八个交换
        return n>>16 | (n&m4)<<16  # 交换高低 16 位

class Solution {
    private static final int m0 = 0x55555555; // 01010101 ...
    private static final int m1 = 0x33333333; // 00110011 ...
    private static final int m2 = 0x0f0f0f0f; // 00001111 ...
    private static final int m3 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
        n = n>>>1&m0 | (n&m0)<<1; // 交换相邻位
        n = n>>>2&m1 | (n&m1)<<2; // 两个两个交换
        n = n>>>4&m2 | (n&m2)<<4; // 四个四个交换
        n = n>>>8&m3 | (n&m3)<<8; // 八个八个交换
        return n>>>16 | n<<16;    // 交换高低 16 位
    }
}

class Solution {
    static constexpr uint32_t m0 = 0x55555555; // 01010101 ...
    static constexpr uint32_t m1 = 0x33333333; // 00110011 ...
    static constexpr uint32_t m2 = 0x0f0f0f0f; // 00001111 ...
    static constexpr uint32_t m3 = 0x00ff00ff; // 00000000111111110000000011111111

    uint32_t reverseBits32(uint32_t n) {
        n = n>>1&m0 | (n&m0)<<1; // 交换相邻位
        n = n>>2&m1 | (n&m1)<<2; // 两个两个交换
        n = n>>4&m2 | (n&m2)<<4; // 四个四个交换
        n = n>>8&m3 | (n&m3)<<8; // 八个八个交换
        return n>>16 | n<<16;    // 交换高低 16 位
    }

public:
    int reverseBits(int n) {
        return reverseBits32(n);
    }
};

const m0 = 0x55555555 // 01010101 ...
const m1 = 0x33333333 // 00110011 ...
const m2 = 0x0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff // 00000000111111110000000011111111
const m4 = 0x0000ffff // 00000000000000001111111111111111

func reverseBits(n int) int {
n = n>>1&m0 | n&m0<<1   // 交换相邻位
n = n>>2&m1 | n&m1<<2   // 两个两个交换
n = n>>4&m2 | n&m2<<4   // 四个四个交换
n = n>>8&m3 | n&m3<<8   // 八个八个交换
return n>>16 | n&m4<<16 // 交换高低 16 位
}

复杂度分析

时间复杂度：$\mathcal{O}(1)$。无论输入的是 $0$ 还是 $2^{31}-2$，计算量没有任何区别。更精细地说，时间复杂度是 $\mathcal{O}(\log W)$，其中 $W=32$ 是位宽。
空间复杂度：$\mathcal{O}(1)$。

附：库函数写法

class Solution:
    def reverseBits(self, n: int) -> int:
        # 没有 O(1) 的库函数，只能用字符串转换代替
        # 032b 中的 b 表示转成二进制串，032 表示补前导零到长度等于 32
        return int(f'{n:032b}'[::-1], 2)

class Solution:
    def reverseBits(self, n: int) -> int:
        # 没有 O(1) 的库函数，只能用字符串转换代替
        return int(bin(n)[2:].zfill(32)[::-1], 2)

class Solution {
    public int reverseBits(int n) {
        return Integer.reverse(n);
    }
}

class Solution {
public:
    int reverseBits(int n) {
        return __builtin_bitreverse32(n);
    }
};

func reverseBits(n int) int {
return int(bits.Reverse32(uint32(n)))
}

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
模拟加法计算过程（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年2月5日 09:42

模拟加法计算过程（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月5日 09:42

二进制的加法怎么算？

和十进制的加法一样，从低到高（从右往左）计算。

示例 1 是 $11+1$，计算过程如下：

计算最低位，$1+1=10$，所以答案的最低位填 $0$，进位是 $1$。
计算下一位，$a$ 中的 $1$ 和进位的 $1$ 相加，$1+1=10$，所以答案的下一位填 $0$，进位是 $1$。现在答案是 $00$。
虽然 $a$ 和 $b$ 都遍历完了，但计算并未结束。还剩下进位 $1$，填入答案的下一位（从低到高第三位）。最终答案为 $100$。

由此可见，需要在计算过程中维护进位值 $\textit{carry}$，每次计算

$$
\textit{sum} = a\ 这一位的值 + b\ 这一位的值 + \textit{carry}
$$

然后答案这一位填 $\textit{sum}\bmod 2$，进位更新为 $\left\lfloor\dfrac{\textit{sum}}{2}\right\rfloor$。例如 $\textit{sum} = 10$，那么答案这一位填 $0$，进位更新为 $1$。

写法一

把计算结果插在答案的末尾，最后把答案反转。

###py

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        ans = []
        i = len(a) - 1  # 从右往左遍历 a 和 b
        j = len(b) - 1
        carry = 0  # 保存进位

        while i >= 0 or j >= 0 or carry:
            x = int(a[i]) if i >= 0 else 0
            y = int(b[j]) if j >= 0 else 0
            s = x + y + carry  # 计算这一位的加法
            # 例如 s = 10，把 '0' 填入答案，把 carry 置为 1
            ans.append(str(s % 2))
            carry = s // 2
            i -= 1
            j -= 1

        return ''.join(reversed(ans))

###java

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder();
        int i = a.length() - 1; // 从右往左遍历 a 和 b
        int j = b.length() - 1;
        int carry = 0; // 保存进位

        while (i >= 0 || j >= 0 || carry > 0) {
            int x = i >= 0 ? a.charAt(i) - '0' : 0;
            int y = j >= 0 ? b.charAt(j) - '0' : 0;
            int sum = x + y + carry; // 计算这一位的加法
            // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
            ans.append(sum % 2);
            carry = sum / 2;
            i--;
            j--;
        }

        return ans.reverse().toString();
    }
}

###cpp

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        int i = a.size() - 1; // 从右往左遍历 a 和 b
        int j = b.size() - 1;
        int carry = 0; // 保存进位

        while (i >= 0 || j >= 0 || carry) {
            int x = i >= 0 ? a[i] - '0' : 0;
            int y = j >= 0 ? b[j] - '0' : 0;
            int sum = x + y + carry; // 计算这一位的加法
            // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
            ans += sum % 2 + '0';
            carry = sum / 2;
            i--;
            j--;
        }

        ranges::reverse(ans);
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

char* addBinary(char* a, char* b) {
    int n = strlen(a);
    int m = strlen(b);
    char* ans = malloc((MAX(n, m) + 2) * sizeof(char));
    int k = 0;

    int i = n - 1; // 从右往左遍历 a 和 b
    int j = m - 1;
    int carry = 0; // 保存进位

    while (i >= 0 || j >= 0 || carry) {
        int x = i >= 0 ? a[i] - '0' : 0;
        int y = j >= 0 ? b[j] - '0' : 0;
        int sum = x + y + carry; // 计算这一位的加法
        // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
        ans[k++] = sum % 2 + '0';
        carry = sum / 2;
        i--;
        j--;
    }

    // 反转 ans
    for (int l = 0, r = k - 1; l < r; l++, r--) {
        char tmp = ans[l];
        ans[l] = ans[r];
        ans[r] = tmp;
    }

    ans[k] = '\0';
    return ans;
}

###go

func addBinary(a, b string) string {
    ans := []byte{}
    i := len(a) - 1 // 从右往左遍历 a 和 b
    j := len(b) - 1
    carry := byte(0) // 保存进位

    for i >= 0 || j >= 0 || carry > 0 {
        // 计算这一位的加法
        sum := carry
        if i >= 0 {
            sum += a[i] - '0'
        }
        if j >= 0 {
            sum += b[j] - '0'
        }
        // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
        ans = append(ans, sum%2+'0')
        carry = sum / 2
        i--
        j--
    }

    slices.Reverse(ans)
    return string(ans)
}

###js

var addBinary = function(a, b) {
    const ans = [];
    let i = a.length - 1; // 从右往左遍历 a 和 b
    let j = b.length - 1;
    let carry = 0; // 保存进位

    while (i >= 0 || j >= 0 || carry) {
        const x = i >= 0 ? Number(a[i]) : 0;
        const y = j >= 0 ? Number(b[j]) : 0;
        const sum = x + y + carry; // 计算这一位的加法
        // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
        ans.push(String(sum % 2));
        carry = Math.floor(sum / 2);
        i--;
        j--;
    }

    return ans.reverse().join('');
};

###rust

impl Solution {
    pub fn add_binary(a: String, b: String) -> String {
        let a = a.as_bytes();
        let b = b.as_bytes();
        let mut ans = vec![];
        let mut i = a.len() as isize - 1; // 从右往左遍历 a 和 b
        let mut j = b.len() as isize - 1;
        let mut carry = 0; // 保存进位

        while i >= 0 || j >= 0 || carry > 0 {
            let x = if i >= 0 { a[i as usize] - b'0' } else { 0 };
            let y = if j >= 0 { b[j as usize] - b'0' } else { 0 };
            let sum = x + y + carry; // 计算这一位的加法
            // 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
            ans.push(sum % 2 + b'0');
            carry = sum / 2;
            i -= 1;
            j -= 1;
        }

        ans.reverse();
        unsafe { String::from_utf8_unchecked(ans) }
    }
}

写法二

直接填入答案，不反转。

###py

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # 保证 len(a) >= len(b)，简化后续代码逻辑
        if len(a) < len(b):
            a, b = b, a

        n, m = len(a), len(b)
        ans = [0] * (n + 1)
        carry = 0  # 保存进位

        for i in range(n - 1, -1, -1):
            j = m - (n - i)
            y = int(b[j]) if j >= 0 else 0
            s = int(a[i]) + y + carry
            ans[i + 1] = str(s % 2)
            carry = s // 2

        ans[0] = str(carry)
        return ''.join(ans[carry ^ 1:])  # 如果 carry == 0 则去掉 ans[0]

###java

class Solution {
    public String addBinary(String a, String b) {
        // 保证 a.length() >= b.length()，简化后续代码逻辑
        if (a.length() < b.length()) {
            return addBinary(b, a);
        }

        int n = a.length();
        int m = b.length();
        char[] ans = new char[n + 1];
        int carry = 0; // 保存进位

        for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
            int x = a.charAt(i) - '0';
            int y = j >= 0 ? b.charAt(j) - '0' : 0;
            int sum = x + y + carry;
            ans[i + 1] = (char) (sum % 2 + '0');
            carry = sum / 2;
        }

        ans[0] = (char) (carry + '0');
        // 如果 carry == 0 则去掉 ans[0]
        return new String(ans, carry ^ 1, n + carry);
    }
}

###cpp

class Solution {
public:
    string addBinary(string a, string b) {
        // 保证 a.size() >= b.size()，简化后续代码逻辑
        if (a.size() < b.size()) {
            swap(a, b);
        }

        int n = a.size(), m = b.size();
        string ans(n + 1, 0);
        int carry = 0; // 保存进位

        for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
            int x = a[i] - '0';
            int y = j >= 0 ? b[j] - '0' : 0;
            int sum = x + y + carry;
            ans[i + 1] = sum % 2 + '0';
            carry = sum / 2;
        }

        if (carry) {
            ans[0] = '1';
        } else {
            ans.erase(ans.begin());
        }

        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

char* addBinary(char* a, char* b) {
    int n = strlen(a);
    int m = strlen(b);
    char* ans = malloc((MAX(n, m) + 2) * sizeof(char));
    ans[MAX(n, m) + 1] = '\0';
    int carry = 0; // 保存进位

    for (int i = n - 1, j = m - 1; i >= 0 || j >= 0; i--, j--) {
        int x = i >= 0 ? a[i] - '0' : 0;
        int y = j >= 0 ? b[j] - '0' : 0;
        int sum = x + y + carry;
        ans[MAX(i, j) + 1] = sum % 2 + '0';
        carry = sum / 2;
    }

    ans[0] = carry + '0';
    // 如果 carry == 0 则去掉 ans[0]
    return ans + (carry ^ 1);
}

###go

func addBinary(a, b string) string {
    // 保证 len(a) >= len(b)，简化后续代码逻辑
    if len(a) < len(b) {
        a, b = b, a
    }

    n, m := len(a), len(b)
    ans := make([]byte, n+1)
    carry := byte(0) // 保存进位

    for i := n - 1; i >= 0; i-- {
        sum := a[i] - '0' + carry
        if j := m - (n - i); j >= 0 {
            sum += b[j] - '0'
        }
        ans[i+1] = sum%2 + '0'
        carry = sum / 2
    }

    ans[0] = carry + '0'
    // 如果 carry == 0 则去掉 ans[0]
    return string(ans[carry^1:])
}

###js

var addBinary = function(a, b) {
    // 保证 a.length >= b.length，简化后续代码逻辑
    if (a.length < b.length) {
        [a, b] = [b, a];
    }

    const n = a.length;
    const m = b.length;
    const ans = Array(n + 1);
    let carry = 0; // 保存进位

    for (let i = n - 1, j = m - 1; i >= 0; i--, j--) {
        const x = Number(a[i]);
        const y = j >= 0 ? Number(b[j]) : 0;
        const sum = x + y + carry;
        ans[i + 1] = String(sum % 2);
        carry = Math.floor(sum / 2);
    }

    if (carry) {
        ans[0] = '1';
    } else {
        ans.shift();
    }

    return ans.join('');
};

###rust

impl Solution {
    pub fn add_binary(a: String, b: String) -> String {
        // 保证 a.len() >= b.len()，简化后续代码逻辑
        if a.len() < b.len() {
            return Self::add_binary(b, a);
        }

        let a = a.as_bytes();
        let b = b.as_bytes();
        let n = a.len();
        let m = b.len();
        let mut ans = vec![0; n + 1];
        let mut carry = 0; // 保存进位

        for i in (0..n).rev() {
            let x = a[i] - b'0';
            let y = if n - i <= m { b[m - (n - i)] - b'0' } else { 0 };
            let sum = x + y + carry;
            ans[i + 1] = sum % 2 + b'0';
            carry = sum / 2;
        }

        if carry > 0 {
            ans[0] = b'1';        
        } else {
            ans.remove(0);
        }

        unsafe { String::from_utf8_unchecked(ans) }
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(\max(n,m))$，其中 $n$ 是 $a$ 的长度，$m$ 是 $b$ 的长度。
空间复杂度：$\mathcal{O}(\max(n,m))$。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
BFS 模拟 + 优化（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年2月14日 08:37

BFS 模拟 + 优化（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年2月14日 08:37

类似 102. 二叉树的层序遍历，用一个 BFS 模拟香槟溢出流程：第一层溢出的香槟流到第二层，第二层溢出的香槟流到第三层，依此类推。

具体地：

处理第一层到第二层，从 $(0,0)$ 溢出的香槟流到 $(1,0)$ 和 $(1,1)$。设溢出的香槟量为 $x$，那么 $(1,0)$ 和 $(1,1)$ 的香槟量都增加 $\dfrac{x}{2}$。
处理第二层到第三层，从 $(1,0)$ 溢出的香槟流到 $(2,0)$ 和 $(2,1)$，从 $(1,1)$ 溢出的香槟流到 $(2,1)$ 和 $(2,2)$。
依此类推。一般地，从 $(i,j)$ 溢出的香槟流到 $(i+1,j)$ 和 $(i+1,j+1)$。设溢出的香槟量为 $x$，那么下一层的 $j$ 和 $j+1$ 的香槟量都增加 $\dfrac{x}{2}$。用一个数组保存下一层每个玻璃杯的香槟量。

优化前

###py

class Solution:
    def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
        cur = [float(poured)]
        for i in range(1, queryRow + 1):
            nxt = [0.0] * (i + 1)
            for j, x in enumerate(cur):
                if x > 1:  # 溢出到下一层
                    nxt[j] += (x - 1) / 2
                    nxt[j + 1] += (x - 1) / 2
            cur = nxt
        return min(cur[queryGlass], 1.0)  # 如果溢出，容量是 1

###java

class Solution {
    public double champagneTower(int poured, int queryRow, int queryGlass) {
        double[] cur = new double[]{(double) poured};
        for (int i = 1; i <= queryRow; i++) {
            double[] nxt = new double[i + 1];
            for (int j = 0; j < cur.length; j++) {
                double x = cur[j] - 1;
                if (x > 0) { // 溢出到下一层
                    nxt[j] += x / 2;
                    nxt[j + 1] += x / 2;
                }
            }
            cur = nxt;
        }
        return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
    }
}

###cpp

class Solution {
public:
    double champagneTower(int poured, int queryRow, int queryGlass) {
        vector<double> cur = {1.0 * poured};
        for (int i = 1; i <= queryRow; i++) {
            vector<double> nxt(i + 1);
            for (int j = 0; j < cur.size(); j++) {
                double x = cur[j] - 1;
                if (x > 0) { // 溢出到下一层
                    nxt[j] += x / 2;
                    nxt[j + 1] += x / 2;
                }
            }
            cur = move(nxt);
        }
        return min(cur[queryGlass], 1.0); // 如果溢出，容量是 1
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))

double champagneTower(int poured, int queryRow, int queryGlass) {
    double* cur = malloc(sizeof(double));
    cur[0] = poured;
    int curSize = 1;

    for (int i = 1; i <= queryRow; i++) {
        double* nxt = calloc(i + 1, sizeof(double));
        for (int j = 0; j < curSize; j++) {
            double x = cur[j] - 1;
            if (x > 0) { // 溢出到下一层
                nxt[j] += x / 2;
                nxt[j + 1] += x / 2;
            }
        }
        free(cur);
        cur = nxt;
        curSize = i + 1;
    }

    double ans = MIN(cur[queryGlass], 1); // 如果溢出，容量是 1
    free(cur);
    return ans;
}

###go

func champagneTower(poured, queryRow, queryGlass int) float64 {
cur := []float64{float64(poured)}
for i := 1; i <= queryRow; i++ {
nxt := make([]float64, i+1)
for j, x := range cur {
if x > 1 { // 溢出到下一层
nxt[j] += (x - 1) / 2
nxt[j+1] += (x - 1) / 2
}
}
cur = nxt
}
return min(cur[queryGlass], 1) // 如果溢出，容量是 1
}

###js

var champagneTower = function(poured, queryRow, queryGlass) {
    let cur = [poured];
    for (let i = 1; i <= queryRow; i++) {
        const nxt = Array(i + 1).fill(0);
        for (let j = 0; j < cur.length; j++) {
            const x = cur[j] - 1;
            if (x > 0) { // 溢出到下一层
                nxt[j] += x / 2;
                nxt[j + 1] += x / 2;
            }
        }
        cur = nxt;
    }
    return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
};

###rust

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let mut cur = vec![poured as f64];
        for i in 1..=query_row as usize {
            let mut nxt = vec![0.0; i + 1];
            for (j, x) in cur.into_iter().enumerate() {
                if x > 1.0 { // 溢出到下一层
                    nxt[j] += (x - 1.0) / 2.0;
                    nxt[j + 1] += (x - 1.0) / 2.0;
                }
            }
            cur = nxt;
        }
        cur[query_glass as usize].min(1.0) // 如果溢出，容量是 1
    }
}

优化

无需使用两个数组，可以像 0-1 背包那样，在同一个数组上修改。

###py

class Solution:
    def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
        f = [0.0] * (queryRow + 1)
        f[0] = float(poured)
        for i in range(queryRow):
            for j in range(i, -1, -1):
                x = f[j] - 1
                if x > 0:
                    f[j + 1] += x / 2
                    f[j] = x / 2
                else:
                    f[j] = 0.0
        return min(f[queryGlass], 1.0)  # 如果溢出，容量是 1

###java

class Solution {
    public double champagneTower(int poured, int queryRow, int queryGlass) {
        double[] f = new double[queryRow + 1];
        f[0] = poured;
        for (int i = 0; i < queryRow; i++) {
            for (int j = i; j >= 0; j--) {
                double x = f[j] - 1;
                if (x > 0) {
                    f[j + 1] += x / 2;
                    f[j] = x / 2;
                } else {
                    f[j] = 0;
                }
            }
        }
        return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
    }
}

###cpp

class Solution {
public:
    double champagneTower(int poured, int queryRow, int queryGlass) {
        vector<double> f(queryRow + 1);
        f[0] = poured;
        for (int i = 0; i < queryRow; i++) {
            for (int j = i; j >= 0; j--) {
                double x = f[j] - 1;
                if (x > 0) {
                    f[j + 1] += x / 2;
                    f[j] = x / 2;
                } else {
                    f[j] = 0;
                }
            }
        }
        return min(f[queryGlass], 1.0); // 如果溢出，容量是 1
    }
};

###c

#define MIN(a, b) ((b) < (a) ? (b) : (a))

double champagneTower(int poured, int queryRow, int queryGlass) {
    double* f = calloc(queryRow + 1, sizeof(double));
    f[0] = poured;

    for (int i = 0; i < queryRow; i++) {
        for (int j = i; j >= 0; j--) {
            double x = f[j] - 1;
            if (x > 0) {
                f[j + 1] += x / 2;
                f[j] = x / 2;
            } else {
                f[j] = 0;
            }
        }
    }

    double ans = MIN(f[queryGlass], 1); // 如果溢出，容量是 1
    free(f);
    return ans;
}

###go

func champagneTower(poured, queryRow, queryGlass int) float64 {
f := make([]float64, queryRow+1)
f[0] = float64(poured)
for i := range queryRow {
for j := i; j >= 0; j-- {
x := f[j] - 1
if x > 0 {
f[j+1] += x / 2
f[j] = x / 2
} else {
f[j] = 0
}
}
}
return min(f[queryGlass], 1) // 如果溢出，容量是 1
}

###js

var champagneTower = function(poured, queryRow, queryGlass) {
    const f = Array(queryRow + 1).fill(0);
    f[0] = poured;
    for (let i = 0; i < queryRow; i++) {
        for (let j = i; j >= 0; j--) {
            const x = f[j] - 1;
            if (x > 0) {
                f[j + 1] += x / 2;
                f[j] = x / 2;
            } else {
                f[j] = 0;
            }
        }
    }
    return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
};

###rust

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let query_row = query_row as usize;
        let mut f = vec![0.0; query_row + 1];
        f[0] = poured as f64;
        for i in 0..query_row {
            for j in (0..=i).rev() {
                let x = f[j] - 1.0;
                if x > 0.0 {
                    f[j + 1] += x / 2.0;
                    f[j] = x / 2.0;
                } else {
                    f[j] = 0.0;
                }
            }
        }
        f[query_glass as usize].min(1.0) // 如果溢出，容量是 1
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(\textit{queryRow}^2)$。
空间复杂度：$\mathcal{O}(\textit{queryRow})$。

相似题目

118. 杨辉三角

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
式子变形 + 枚举右维护左（Python/Java/C++/Go）endlesscheng
2025年10月12日 12:01

式子变形 + 枚举右维护左（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年10月12日 12:01

问题拆解

分成如下三类问题，依次解答：

子串只包含一种字母。
子串只包含两种字母。
子串包含三种字母。

子串只包含一种字母

即 $s$ 中的最长连续相同子串的长度。这题是 1446. 连续字符。

这可以用分组循环解决。

适用场景：按照题目要求，序列会被分割成若干组，每一组的判断/处理逻辑是相同的。

核心思想：

外层循环负责遍历组之前的准备工作（记录开始位置），和遍历组之后的统计工作（更新答案最大值）。
内层循环负责遍历组，找出这一组最远在哪结束。

这个写法的好处是，各个逻辑块分工明确，也不需要特判最后一组（易错点）。以我的经验，这个写法是所有写法中最不容易出 bug 的，推荐大家记住。

分组循环详细讲解。

子串只包含两种字母

同样地，用分组循环分组，每组只包含两种字母。

对于每一组，计算含有相同数量的两种字母的最长子串。这题是 525. 连续数组。

做法见我的题解。

子串包含三种字母

仿照 525 题的做法，设 $\texttt{a}$ 在这个组的个数前缀和数组为 $S_a$，$\texttt{b}$ 在这个组的个数前缀和数组为 $S_b$，$\texttt{c}$ 在这个组的个数前缀和数组为 $S_c$。

子串 $[l,r)$ 中的字母 $\texttt{a},\texttt{b},\texttt{c}$ 的出现次数相等，可以拆分为如下两个约束：

子串 $[l,r)$ 中的字母 $\texttt{a}$ 和 $\texttt{b}$ 的出现次数相等。
子串 $[l,r)$ 中的字母 $\texttt{b}$ 和 $\texttt{c}$ 的出现次数相等。

只要满足这两个约束，由等号的传递性可知，子串 $[l,r)$ 中的字母 $\texttt{a}$ 和 $\texttt{c}$ 的出现次数相等，即三个字母的出现次数都相等。

两个约束即如下两个等式

$$
\begin{aligned}
S_a[r] - S_b[r] &= S_a[l] - S_b[l] \
S_b[r] - S_c[r] &= S_b[l] - S_c[l] \
\end{aligned}
$$

定义数组 $a[i] = (S_a[i] - S_b[i], S_b[i] - S_c[i])$，问题变成：

计算数组 $a$ 中的一对相等元素的最远距离。

做法同上。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)

        # 一种字母
        ans = i = 0
        while i < n:
            start = i
            i += 1
            while i < n and s[i] == s[i - 1]:
                i += 1
            ans = max(ans, i - start)

        # 两种字母
        def f(x: str, y: str) -> None:
            nonlocal ans
            i = 0
            while i < n:
                pos = {0: i - 1}  # 前缀和数组的首项是 0，位置相当于在 i-1
                d = 0  # x 的个数减去 y 的个数
                while i < n and (s[i] == x or s[i] == y):
                    d += 1 if s[i] == x else -1
                    if d in pos:
                        ans = max(ans, i - pos[d])
                    else:
                        pos[d] = i
                    i += 1
                i += 1

        f('a', 'b')
        f('a', 'c')
        f('b', 'c')

        # 三种字母
        # 前缀和数组的首项是 0，位置相当于在 -1
        pos = {(0, 0): -1}
        cnt = defaultdict(int)
        for i, b in enumerate(s):
            cnt[b] += 1
            p = (cnt['a'] - cnt['b'], cnt['b'] - cnt['c'])
            if p in pos:
                ans = max(ans, i - pos[p])
            else:
                pos[p] = i
        return ans

###java

class Solution {
    public int longestBalanced(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ans = 0;

        // 一种字母
        for (int i = 0; i < n; ) {
            int start = i;
            for (i++; i < n && s[i] == s[i - 1]; i++) ;
            ans = Math.max(ans, i - start);
        }

        // 两种字母
        ans = Math.max(ans, f(s, 'a', 'b'));
        ans = Math.max(ans, f(s, 'a', 'c'));
        ans = Math.max(ans, f(s, 'b', 'c'));

        // 三种字母
        // 把 (x, y) 压缩成一个 long，方便保存至哈希表
        // (x, y) 变成 (x + n) << 20 | (y + n)，其中 +n 避免出现负数
        Map<Long, Integer> pos = new HashMap<>();
        pos.put((long) n << 20 | n, -1); // 前缀和数组的首项是 0，位置相当于在 -1
        int[] cnt = new int[3];
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            long p = (long) (cnt[0] - cnt[1] + n) << 20 | (cnt[1] - cnt[2] + n);
            if (pos.containsKey(p)) {
                ans = Math.max(ans, i - pos.get(p));
            } else {
                pos.put(p, i);
            }
        }
        return ans;
    }

    private int f(char[] s, char x, char y) {
        int n = s.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> pos = new HashMap<>();
            pos.put(0, i - 1); // 前缀和数组的首项是 0，位置相当于在 i-1
            int d = 0; // x 的个数减去 y 的个数
            for (; i < n && (s[i] == x || s[i] == y); i++) {
                d += s[i] == x ? 1 : -1;
                if (pos.containsKey(d)) {
                    ans = Math.max(ans, i - pos.get(d));
                } else {
                    pos.put(d, i);
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.size();
        int ans = 0;
        
        // 一种字母
        for (int i = 0; i < n;) {
            int start = i;
            for (i++; i < n && s[i] == s[i - 1]; i++);
            ans = max(ans, i - start);
        }

        // 两种字母
        auto f = [&](char x, char y) -> void {
            for (int i = 0; i < n; i++) {
                unordered_map<int, int> pos = {{0, i - 1}}; // 前缀和数组的首项是 0，位置相当于在 i-1
                int d = 0; // x 的个数减去 y 的个数
                for (; i < n && (s[i] == x || s[i] == y); i++) {
                    d += s[i] == x ? 1 : -1;
                    if (pos.contains(d)) {
                        ans = max(ans, i - pos[d]);
                    } else {
                        pos[d] = i;
                    }
                }
            }
        };
        f('a', 'b');
        f('a', 'c');
        f('b', 'c');

        // 三种字母
        // 把 (x, y) 压缩成一个 long long，方便保存至哈希表
        // (x, y) 变成 (x + n) << 32 | (y + n)，其中 +n 避免出现负数
        unordered_map<long long, int> pos = {{1LL * n << 32 | n, -1}}; // 前缀和数组的首项是 0，位置相当于在 -1
        int cnt[3]{};
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            long long p = 1LL * (cnt[0] - cnt[1] + n) << 32 | (cnt[1] - cnt[2] + n);
            if (pos.contains(p)) {
                ans = max(ans, i - pos[p]);
            } else {
                pos[p] = i;
            }
        }
        return ans;
    }
};

###go

func longestBalanced(s string) (ans int) {
n := len(s)

// 一种字母
for i := 0; i < n; {
start := i
for i++; i < n && s[i] == s[i-1]; i++ {
}
ans = max(ans, i-start)
}

// 两种字母
f := func(x, y byte) {
for i := 0; i < n; i++ {
pos := map[int]int{0: i - 1} // 前缀和数组的首项是 0，位置相当于在 i-1
d := 0 // x 的个数减去 y 的个数
for ; i < n && (s[i] == x || s[i] == y); i++ {
if s[i] == x {
d++
} else {
d--
}
if j, ok := pos[d]; ok {
ans = max(ans, i-j)
} else {
pos[d] = i
}
}
}
}
f('a', 'b')
f('a', 'c')
f('b', 'c')

// 三种字母
type pair struct{ diffAB, diffBC int }
pos := map[pair]int{{}: -1} // 前缀和数组的首项是 0，位置相当于在 -1
cnt := [3]int{}
for i, b := range s {
cnt[b-'a']++
p := pair{cnt[0] - cnt[1], cnt[1] - cnt[2]}
if j, ok := pos[p]; ok {
ans = max(ans, i-j)
} else {
pos[p] = i
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

专题训练

下面双指针题单的「六、分组循环」。
下面数据结构题单的「§1.2 前缀和与哈希表」。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
两种方法：暴力枚举 / 枚举右维护左（Python/Java/C++/Go）endlesscheng
2025年10月12日 12:09

两种方法：暴力枚举 / 枚举右维护左（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年10月12日 12:09

写法一：暴力枚举

枚举子串左端点 $i$，然后枚举子串右端点 $j=i,i+1,i+2,\ldots,n-1$。

在枚举右端点 $j$ 的过程中，统计子串 $[i,j]$ 每种字母的出现次数 $\textit{cnt}$。

遍历 $\textit{cnt}$，如果所有字母的出现次数均相同，用子串长度 $j-i+1$ 更新答案的最大值。

本题视频讲解，欢迎点赞关注~

优化前

###py

class Solution:
    def longestBalanced(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i in range(n):
            cnt = defaultdict(int)
            for j in range(i, n):
                cnt[s[j]] += 1
                if len(set(cnt.values())) == 1:
                    ans = max(ans, j - i + 1)
        return ans

###java

class Solution {
    public int longestBalanced(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int[] cnt = new int[26];
            next:
            for (int j = i; j < n; j++) {
                int base = ++cnt[s[j] - 'a'];
                for (int c : cnt) {
                    if (c > 0 && c != base) {
                        continue next;
                    }
                }
                ans = Math.max(ans, j - i + 1);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int cnt[26]{};
            for (int j = i; j < n; j++) {
                int base = ++cnt[s[j] - 'a'];
                for (int c : cnt) {
                    if (c && c != base) {
                        base = -1;
                        break;
                    }
                }
                if (base != -1) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

###go

func longestBalanced(s string) (ans int) {
for i := range s {
cnt := make([]int, 26)
next:
for j := i; j < len(s); j++ {
cnt[s[j]-'a']++
base := cnt[s[j]-'a']
for _, c := range cnt {
if c > 0 && c != base {
continue next
}
}
ans = max(ans, j-i+1)
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2|\Sigma|)$，其中 $n$ 是 $s$ 的长度，$|\Sigma|=26$ 是字符集合的大小。
空间复杂度：$\mathcal{O}(|\Sigma|)$。

优化

设 $\textit{mx} = \max(\textit{cnt})$，设 $\textit{kinds}$ 为子串中的不同字母个数。

如果 $\textit{mx}\cdot \textit{kinds} = j-i+1$，说明子串所有字母的出现次数均为 $\textit{mx}$，均相等。

###py

# 手写 max 更快
max = lambda a, b: b if b > a else a

class Solution:
    def longestBalanced(self, s: str) -> int:
        ans = 0
        for i in range(len(s)):
            cnt = defaultdict(int)
            mx = 0
            for j in range(i, len(s)):
                cnt[s[j]] += 1
                mx = max(mx, cnt[s[j]])
                if mx * len(cnt) == j - i + 1:
                    ans = max(ans, j - i + 1)
        return ans

###java

class Solution {
    public int longestBalanced(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int[] cnt = new int[26];
            int mx = 0, kinds = 0;
            for (int j = i; j < n; j++) {
                int b = s[j] - 'a';
                if (cnt[b] == 0) {
                    kinds++;
                }
                mx = Math.max(mx, ++cnt[b]);
                if (mx * kinds == j - i + 1) {
                    ans = Math.max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int cnt[26]{};
            int mx = 0, kinds = 0;
            for (int j = i; j < n; j++) {
                int b = s[j] - 'a';
                if (cnt[b] == 0) {
                    kinds++;
                }
                mx = max(mx, ++cnt[b]);
                if (mx * kinds == j - i + 1) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

###go

func longestBalanced(s string) (ans int) {
for i := range s {
cnt := [26]int{}
mx, kinds := 0, 0
for j := i; j < len(s); j++ {
b := s[j] - 'a'
if cnt[b] == 0 {
kinds++
}
cnt[b]++
mx = max(mx, cnt[b])
if mx*kinds == j-i+1 {
ans = max(ans, j-i+1)
}
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n^2)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(|\Sigma|)$，其中 $|\Sigma|=26$ 是字符集合的大小。

写法二：枚举右，维护左

推荐先完成 3714. 最长的平衡子串 II，再来理解这个做法。

能否只用一个哈希表，同时解决子串包含 $1$ 个、$2$ 个……$26$ 个字母的情况？

定义 $S[i][j]$ 表示前缀 $[0,i]$ 中的字母 $j$ 的出现次数。$S[-1][j] = 0$。

如果要找只包含字母 $\texttt{abc}$ 的平衡子串 $(l,r]$，3714 题告诉我们：

用 $S[r][1] - S[r][0] = S[l][1] - S[l][0]$ 判断子串中的 $\texttt{a}$ 和 $\texttt{b}$ 的个数是否相等。
用 $S[r][2] - S[r][0] = S[l][2] - S[l][0]$ 判断子串中的 $\texttt{a}$ 和 $\texttt{c}$ 的个数是否相等。
此外，子串不能包含 $\ge \texttt{d}$ 的字母，即 $S[r][j] - S[l][j] = 0\ (j\ge 3)$，也就是 $S[r][j] = S[l][j]\ (j\ge 3)$。

据此，定义

$$
d[i][j] =
\begin{cases}
S[i][j] - S[i][\textit{minCh}], & j\ 在子串中 \
S[i][j], & j\ 不在子串中 \
\end{cases}
$$

其中 $\textit{minCh}$ 是子串中的最小字母，用来作为减法的基准。

然而，这个定义面临一个尴尬的问题：

我怎么知道 $j$ 是否在子串中？

必须先知道子串包含哪些字母，才能准确地算出 $d[i][j]$。

难道要像 3714 题那样，枚举所有非空字母子集，即 $2^{26}-1$ 种情况？

实际上，考虑以 $i$ 为右端点的子串，当子串左端点从 $i$ 开始向左移动（扩展）时，子串中的字母种类数要么不变，要么加一，所以固定右端点时，只有至多 $26$ 种字母集合。（这有点像 LogTrick）

于是，对于每个右端点 $i$，我们至多枚举 $26$ 种字母集合。

对于一个固定的字母集合，$d[i][j]$ 的值就是固定的了。问题相当于：

找到一对距离最远的 $(d[l],d[i])$，满足 $d[l] = d[i]$。
用 $i-l$ 更新答案的最大值。

现在，「枚举右维护左」中的「枚举右」解决了，「维护左」怎么做？

对于子串 $(l,r]$，我们需要：

枚举以 $l+1$ 为左端点的字母集合（至多 $26$ 种）。
计算 $d[l]$，作为哈希表的 key。哈希表的 value 为 $l$。

如果 $d[l] = d[r]$，那么子串 $(l,r]$ 就是平衡子串吗？

不一定。存在 $d[i]$ 相同，但字母集合不同的情况。所以我们还需要在哈希表的 key 中添加一个 $\textit{mask}$，表示字母集合（实现时用二进制数压缩表示）。

小优化：如果整个 $s$ 是平衡的，返回 $n$。

###py

class Solution:
    def longestBalanced(self, s: str) -> int:
        n = len(s)
        cnt = Counter(s)
        if max(cnt.values()) * len(cnt) == n:  # s 是平衡的
            return n

        mp = {c: i for i, c in enumerate(cnt)}
        s = [mp[c] for c in s]  # 离散化，字母 -> 数字

        n = len(s)
        suf_orders = [None] * n
        order = []
        for i in range(n - 1, -1, -1):
            # 把最近出现的字母移到 order 末尾
            try: order.remove(s[i])
            except: pass
            order.append(s[i])
            suf_orders[i] = order[:]

        order = []
        cnt = [0] * len(mp)
        pos = {}
        ans = 0
        for i, b in enumerate(s):
            suf_order = suf_orders[i]
            min_ch = inf
            mask = 0
            for j in range(len(suf_order) - 1, -1, -1):
                min_ch = min(min_ch, suf_order[j])
                # 注意此时 cnt 并不包含 s[i]，我们计算的是前缀 s[:i] 的信息
                # 在子串中的字母，计算差值
                # 不在子串中的字母，维持原样
                d = cnt[:]
                for ch in suf_order[j:]:
                    d[ch] -= cnt[min_ch]
                mask |= 1 << suf_order[j]
                p = (tuple(d), mask)  # mask 用来区分 d[ch] 是差值还是原始值
                # 记录 p 首次出现的位置
                if p not in pos:
                    pos[p] = i - 1

            # 把最近出现的字母移到 order 末尾
            try: order.remove(b)
            except: pass
            order.append(b)

            cnt[b] += 1
            min_ch = inf
            mask = 0
            for j in range(len(order) - 1, -1, -1):
                min_ch = min(min_ch, order[j])
                d = cnt[:]
                for ch in order[j:]:
                    d[ch] -= cnt[min_ch]
                mask |= 1 << order[j]
                p = (tuple(d), mask)
                # 再次遇到完全一样的 p，说明我们找到了一个平衡子串，左端点为 pos[p]+1，右端点为 i
                if p in pos:
                    ans = max(ans, i - pos[p])

        return ans

###go

func longestBalanced(s string) (ans int) {
n := len(s)
sufOrders := make([][]byte, n)
order := []byte{}
move := func(b byte) {
// 把最近出现的字母 b 移到 order 末尾
j := bytes.IndexByte(order, b)
if j >= 0 {
order = append(order[:j], order[j+1:]...)
}
order = append(order, b)
}
for i := n - 1; i >= 0; i-- {
move(s[i] - 'a')
sufOrders[i] = slices.Clone(order)
}

order = []byte{}
cnt := [27]int{} // cnt[26] 作为 mask，用来区分 tmp[ch] 是差值还是原始值
pos := map[[27]int]int{}
for i, b := range s {
sufOrder := sufOrders[i]
minCh := byte(25)
cnt[26] = 0
for j := len(sufOrder) - 1; j >= 0; j-- {
cnt[26] |= 1 << sufOrder[j]
minCh = min(minCh, sufOrder[j])
// 注意此时 cnt 并不包含 s[i]，我们计算的是前缀 s[:i] 的信息
// 在子串中的字母，计算差值
// 不在子串中的字母，维持原样
d := cnt
for _, ch := range sufOrder[j:] {
d[ch] -= cnt[minCh]
}
// 记录 d 首次出现的位置
if _, ok := pos[d]; !ok {
pos[d] = i - 1
}
}

// 把最近出现的字母移到 order 末尾
move(byte(b - 'a'))

cnt[b-'a']++
minCh = byte(25)
cnt[26] = 0
for j := len(order) - 1; j >= 0; j-- {
cnt[26] |= 1 << order[j]
minCh = min(minCh, order[j])
d := cnt
for _, ch := range order[j:] {
d[ch] -= cnt[minCh]
}
// 再次遇到完全一样的状态，说明找到了一个平衡子串，左端点为 l+1，右端点为 i
if l, ok := pos[d]; ok {
ans = max(ans, i-l)
}
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n|\Sigma|^2)$，其中 $n$ 是 $s$ 的长度，$|\Sigma|=26$ 是字符集合的大小。
空间复杂度：$\mathcal{O}(n|\Sigma|)$。

注：每次 $\textit{minCh}$ 变小时，我们都要重新算一遍 $\textit{tmp}$。如果计算 $\textit{tmp}$ 的多项式哈希值（代替哈希表的 key），我们可以 $\mathcal{O}(1)$ 计算哈希值的变化量，从而做到 $\mathcal{O}(n|\Sigma|)$ 时间。但该做法无法保证 100% 正确。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
两种方法维护前缀和：Lazy 线段树 / 分块（Python/Java/C++/Go）endlesscheng
2025年10月19日 12:09

两种方法维护前缀和：Lazy 线段树 / 分块（Python/Java/C++/Go）

LeetCode 每日一题题解

作者 endlesscheng

2025年10月19日 12:09

前置题目/知识

本题的简单版本 525. 连续数组，我的题解。
前缀和。
Lazy 线段树。

转化

如果可以把问题转化成 525 题，就好解决了。

对比一下：

525 题，相同元素多次统计。
本题，相同元素只能统计一次。

如果我们能找到一个方法，使得相同元素只被统计一次，那么就能转化成 525 题。

从左到右遍历 $\textit{nums}$，如果固定子数组右端点为 $i$，要想让子数组包含某个元素 $x$，左端点必须 $\le x\ 最后一次出现的位置$。只要子数组包含最近遇到的 $x$，那么无论子数组有多长，都包含了 $x$。题目要求，多个 $x$ 只能算一次，那么把除了最近一次的 $x$ 全部不计入，就变成 525 题了！

以 $\textit{nums}=[1,2,1,2,3,3]$ 为例：

遍历到 $i=0$，把 $\textit{nums}$ 视作 $[1,,,,,*]$。
遍历到 $i=1$，把 $\textit{nums}$ 视作 $[1,2,,,,]$。
遍历到 $i=2$，把 $\textit{nums}$ 视作 $[,2,1,,,]$。
遍历到 $i=3$，把 $\textit{nums}$ 视作 $[,,1,2,,]$。
遍历到 $i=4$，把 $\textit{nums}$ 视作 $[,,1,2,3,*]$。
遍历到 $i=5$，把 $\textit{nums}$ 视作 $[,,1,2,*,3]$。

根据 525 题，把偶数视作 $-1$，奇数视作 $1$，遍历过的星号视作 $0$，设这个新数组为 $a$，问题相当于：

计算 $a$ 中和为 $0$ 的最长子数组的长度。

设 $a$ 的长为 $n+1$ 的前缀和数组为 $\textit{sum}$。根据 525 题，问题相当于：

枚举 $i$，在 $[0,i-1]$ 中找到一个下标最小的 $\textit{sum}[j]$，满足 $\textit{sum}[j] = \textit{sum}[i]$。
用子数组长度 $i-j$ 更新答案的最大值。

根据上面动态变化的过程：

设 $x=\textit{nums}[i]$ 对应的 $a[i]$ 值为 $v$。
当我们首次遇到 $x$ 时，对于前缀和 $\textit{sum}$ 来说，$[i,n]$ 要全部增加 $v$。
当我们再次遇到 $x$ 时，原来的 $\textit{nums}[j]$ 变成星号（$a[j]=0$），$x$ 搬到了新的位置 $i$，所以之前的「$[j,n]$ 全部增加 $v$」变成了「$[i,n]$ 全部增加 $v$」，也就是撤销 $[j,i-1]$ 的加 $v$，也就是把 $[j,i-1]$ 减 $v$。

整理一下，我们需要维护一个动态变化的前缀和数组，需要一个数据结构，支持：

把 $\textit{sum}$ 的某个子数组增加 $1$ 或者 $-1$。
查询 $\textit{sum}[i]$ 在 $\textit{sum}$ 中首次出现的位置。

本题视频讲解，欢迎点赞关注~

方法一：Lazy 线段树

由于 $a$ 中元素只有 $-1,0,1$，所以 $\textit{sum}$ 数组相邻元素之差 $\le 1$。根据离散介值定理，设 $\textit{min}$ 和 $\textit{max}$ 分别为区间的最小值和最大值，只要 $\textit{sum}[i]$ 在 $[\textit{min},\textit{max}]$ 范围中，区间就一定存在等于 $\textit{sum}[i]$ 的数。

用 Lazy 线段树维护区间最小值、区间最大值、区间加的 Lazy tag。

下面只用到部分线段树模板，完整线段树模板见 数据结构题单。

###py

# 手写 min max 更快
min = lambda a, b: b if b < a else a
max = lambda a, b: b if b > a else a

class Node:
    __slots__ = 'min', 'max', 'todo'

    def __init__(self):
        self.min = self.max = self.todo = 0

class LazySegmentTree:
    def __init__(self, n: int):
        self._n = n
        self._tree = [Node() for _ in range(2 << (n - 1).bit_length())]

    # 把懒标记作用到 node 子树
    def _apply(self, node: int, todo: int) -> None:
        cur = self._tree[node]
        cur.min += todo
        cur.max += todo
        cur.todo += todo

    # 把当前节点的懒标记下传给左右儿子
    def _spread(self, node: int) -> None:
        todo = self._tree[node].todo
        if todo == 0:  # 没有需要下传的信息
            return
        self._apply(node * 2, todo)
        self._apply(node * 2 + 1, todo)
        self._tree[node].todo = 0  # 下传完毕

    # 合并左右儿子的 min max 到当前节点
    def _maintain(self, node: int) -> None:
        l_node = self._tree[node * 2]
        r_node = self._tree[node * 2 + 1]
        self._tree[node].min = min(l_node.min, r_node.min)
        self._tree[node].max = max(l_node.max, r_node.max)

    def _update(self, node: int, l: int, r: int, ql: int, qr: int, f: int) -> None:
        if ql <= l and r <= qr:  # 当前子树完全在 [ql, qr] 内
            self._apply(node, f)
            return
        self._spread(node)
        m = (l + r) // 2
        if ql <= m:  # 更新左子树
            self._update(node * 2, l, m, ql, qr, f)
        if qr > m:  # 更新右子树
            self._update(node * 2 + 1, m + 1, r, ql, qr, f)
        self._maintain(node)

    def _find_first(self, node: int, l: int, r: int, ql: int, qr: int, target: int) -> int:
        if l > qr or r < ql or not self._tree[node].min <= target <= self._tree[node].max:
            return -1
        if l == r:
            return l
        self._spread(node)
        m = (l + r) // 2
        idx = self._find_first(node * 2, l, m, ql, qr, target)
        if idx < 0:
            # 去右子树找
            idx = self._find_first(node * 2 + 1, m + 1, r, ql, qr, target)
        return idx

    # 用 f 更新 [ql, qr] 中的每个 sum[i]
    # 0 <= ql <= qr <= n-1
    # 时间复杂度 O(log n)
    def update(self, ql: int, qr: int, f: int) -> None:
        self._update(1, 0, self._n - 1, ql, qr, f)

    # 查询 [ql, qr] 内第一个等于 target 的元素下标
    # 找不到返回 -1
    # 0 <= ql <= qr <= n-1
    # 时间复杂度 O(log n)
    def find_first(self, ql: int, qr: int, target: int) -> int:
        return self._find_first(1, 0, self._n - 1, ql, qr, target)

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        t = LazySegmentTree(n + 1)

        last = {}  # nums 的元素上一次出现的位置
        ans = cur_sum = 0
        for i, x in enumerate(nums, 1):
            v = 1 if x % 2 else -1
            j = last.get(x, 0)
            if j == 0:  # 首次遇到 x
                cur_sum += v
                t.update(i, n, v)  # sum[i:] 增加 v
            else:  # 再次遇到 x
                t.update(j, i - 1, -v)  # 撤销之前对 sum[j:i] 的增加
            last[x] = i

            # 把 i-1 优化成 i-1-ans，因为在下标 > i-1-ans 中搜索是没有意义的，不会把答案变大
            j = t.find_first(0, i - 1 - ans, cur_sum)
            if j >= 0:
                ans = i - j  # 如果找到了，那么答案肯定会变大
        return ans

###java

class LazySegmentTree {
    private static final class Node {
        int min;
        int max;
        int todo;
    }

    // 把懒标记作用到 node 子树
    private void apply(int node, int todo) {
        Node cur = tree[node];
        cur.min += todo;
        cur.max += todo;
        cur.todo += todo;
    }

    private final int n;
    private final Node[] tree;

    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1）
    public LazySegmentTree(int n) {
        this.n = n;
        tree = new Node[2 << (32 - Integer.numberOfLeadingZeros(n - 1))];
        Arrays.setAll(tree, _ -> new Node());
    }

    // 用 f 更新 [ql, qr] 中的每个 sum[i]
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    public void update(int ql, int qr, int f) {
        update(1, 0, n - 1, ql, qr, f);
    }

    // 查询 [ql, qr] 内第一个等于 target 的元素下标
    // 找不到返回 -1
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    public int findFirst(int ql, int qr, int target) {
        return findFirst(1, 0, n - 1, ql, qr, target);
    }

    // 把当前节点的懒标记下传给左右儿子
    private void spread(int node) {
        int todo = tree[node].todo;
        if (todo == 0) { // 没有需要下传的信息
            return;
        }
        apply(node * 2, todo);
        apply(node * 2 + 1, todo);
        tree[node].todo = 0; // 下传完毕
    }

    // 合并左右儿子的 val 到当前节点的 val
    private void maintain(int node) {
        tree[node].min = Math.min(tree[node * 2].min, tree[node * 2 + 1].min);
        tree[node].max = Math.max(tree[node * 2].max, tree[node * 2 + 1].max);
    }

    private void update(int node, int l, int r, int ql, int qr, int f) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            apply(node, f);
            return;
        }
        spread(node);
        int m = (l + r) / 2;
        if (ql <= m) { // 更新左子树
            update(node * 2, l, m, ql, qr, f);
        }
        if (qr > m) { // 更新右子树
            update(node * 2 + 1, m + 1, r, ql, qr, f);
        }
        maintain(node);
    }

    private int findFirst(int node, int l, int r, int ql, int qr, int target) {
        if (l > qr || r < ql || target < tree[node].min || target > tree[node].max) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        spread(node);
        int m = (l + r) / 2;
        int idx = findFirst(node * 2, l, m, ql, qr, target);
        if (idx < 0) {
            idx = findFirst(node * 2 + 1, m + 1, r, ql, qr, target);
        }
        return idx;
    }
}

class Solution {
    public int longestBalanced(int[] nums) {
        int n = nums.length;
        LazySegmentTree t = new LazySegmentTree(n + 1);

        Map<Integer, Integer> last = new HashMap<>(); // nums 的元素上一次出现的位置
        int ans = 0;
        int curSum = 0;

        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int v = x % 2 > 0 ? 1 : -1;
            Integer j = last.get(x);
            if (j == null) { // 首次遇到 x
                curSum += v;
                t.update(i, n, v); // sum 的 [i,n] 增加 v
            } else { // 再次遇到 x
                t.update(j, i - 1, -v); // 撤销之前对 sum 的 [j,i-1] 的增加
            }
            last.put(x, i);

            // 把 i-1 优化成 i-1-ans，因为在下标 > i-1-ans 中搜索是没有意义的，不会把答案变大
            int l = t.findFirst(0, i - 1 - ans, curSum);
            if (l >= 0) {
                ans = i - l; // 如果找到了，那么答案肯定会变大
            }
        }
        return ans;
    }
}

###cpp

class LazySegmentTree {
    using T = pair<int, int>;
    using F = int;

    // 懒标记初始值
    const F TODO_INIT = 0;

    struct Node {
        T val;
        F todo;
    };

    int n;
    vector<Node> tree;

    // 合并两个 val
    T merge_val(const T& a, const T& b) const {
        return {min(a.first, b.first), max(a.second, b.second)};
    }

    // 合并两个懒标记
    F merge_todo(const F& a, const F& b) const {
        return a + b;
    }

    // 把懒标记作用到 node 子树（本例为区间加）
    void apply(int node, int l, int r, F todo) {
        Node& cur = tree[node];
        // 计算 tree[node] 区间的整体变化
        cur.val.first += todo;
        cur.val.second += todo;
        cur.todo = merge_todo(todo, cur.todo);
    }

    // 把当前节点的懒标记下传给左右儿子
    void spread(int node, int l, int r) {
        Node& cur = tree[node];
        F todo = cur.todo;
        if (todo == TODO_INIT) { // 没有需要下传的信息
            return;
        }
        int m = (l + r) / 2;
        apply(node * 2, l, m, todo);
        apply(node * 2 + 1, m + 1, r, todo);
        cur.todo = TODO_INIT; // 下传完毕
    }

    // 合并左右儿子的 val 到当前节点的 val
    void maintain(int node) {
        tree[node].val = merge_val(tree[node * 2].val, tree[node * 2 + 1].val);
    }

    // 用 a 初始化线段树
    // 时间复杂度 O(n)
    void build(const vector<T>& a, int node, int l, int r) {
        Node& cur = tree[node];
        cur.todo = TODO_INIT;
        if (l == r) { // 叶子
            cur.val = a[l]; // 初始化叶节点的值
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m); // 初始化左子树
        build(a, node * 2 + 1, m + 1, r); // 初始化右子树
        maintain(node);
    }

    void update(int node, int l, int r, int ql, int qr, F f) {
        if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
            apply(node, l, r, f);
            return;
        }
        spread(node, l, r);
        int m = (l + r) / 2;
        if (ql <= m) { // 更新左子树
            update(node * 2, l, m, ql, qr, f);
        }
        if (qr > m) { // 更新右子树
            update(node * 2 + 1, m + 1, r, ql, qr, f);
        }
        maintain(node);
    }

    // 查询 [ql,qr] 内第一个等于 target 的元素下标
    // 找不到返回 -1
    int find_first(int node, int l, int r, int ql, int qr, int target) {
        // 不相交 或 target 不在当前区间的 [min,max] 范围内
        if (l > qr || r < ql || target < tree[node].val.first || target > tree[node].val.second) {
            return -1;
        }
        if (l == r) {
            // 此处必然等于 target
            return l;
        }
        spread(node, l, r);
        int m = (l + r) / 2;
        int idx = find_first(node * 2, l, m, ql, qr, target);
        if (idx < 0) {
            // 去右子树找
            idx = find_first(node * 2 + 1, m + 1, r, ql, qr, target);
        }
        return idx;
    }

public:
    // 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
    LazySegmentTree(int n, T init_val = {0, 0}) : LazySegmentTree(vector<T>(n, init_val)) {}

    // 线段树维护数组 a
    LazySegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) {
        build(a, 1, 0, n - 1);
    }

    // 用 f 更新 [ql, qr] 中的每个 a[i]
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    void update(int ql, int qr, F f) {
        update(1, 0, n - 1, ql, qr, f);
    }

    // 查询 [ql, qr] 内第一个等于 target 的元素下标
    // 找不到返回 -1
    // 0 <= ql <= qr <= n-1
    // 时间复杂度 O(log n)
    int find_first(int ql, int qr, int target) {
        return find_first(1, 0, n - 1, ql, qr, target);
    }
};

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        LazySegmentTree t(n + 1);

        unordered_map<int, int> last; // nums 的元素上一次出现的位置
        int ans = 0, cur_sum = 0;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int v = x % 2 ? 1 : -1;
            auto it = last.find(x);
            if (it == last.end()) { // 首次遇到 x
                cur_sum += v;
                t.update(i, n, v); // sum 的 [i,n] 增加 v
            } else { // 再次遇到 x
                int j = it->second;
                t.update(j, i - 1, -v); // 撤销之前对 sum 的 [j,i-1] 的增加
            }
            last[x] = i;

            // 把 i-1 优化成 i-1-ans，因为在下标 > i-1-ans 中搜索是没有意义的，不会把答案变大
            int j = t.find_first(0, i - 1 - ans, cur_sum);
            if (j >= 0) {
                ans = i - j; // 如果找到了，那么答案肯定会变大
            }
        }
        return ans;
    }
};

###go

// 完整模板及注释见数据结构题单 https://leetcode.cn/circle/discuss/mOr1u6/
type pair struct{ min, max int }
type lazySeg []struct {
l, r int
pair
todo int
}

func merge(l, r pair) pair {
return pair{min(l.min, r.min), max(l.max, r.max)}
}

func (t lazySeg) apply(o int, f int) {
cur := &t[o]
cur.min += f
cur.max += f
cur.todo += f
}

func (t lazySeg) maintain(o int) {
t[o].pair = merge(t[o<<1].pair, t[o<<1|1].pair)
}

func (t lazySeg) spread(o int) {
f := t[o].todo
if f == 0 {
return
}
t.apply(o<<1, f)
t.apply(o<<1|1, f)
t[o].todo = 0
}

func (t lazySeg) build(o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
return
}
m := (l + r) >> 1
t.build(o<<1, l, m)
t.build(o<<1|1, m+1, r)
}

func (t lazySeg) update(o, l, r int, f int) {
if l <= t[o].l && t[o].r <= r {
t.apply(o, f)
return
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if l <= m {
t.update(o<<1, l, r, f)
}
if m < r {
t.update(o<<1|1, l, r, f)
}
t.maintain(o)
}

// 查询 [l,r] 内第一个等于 target 的元素下标
func (t lazySeg) findFirst(o, l, r, target int) int {
if t[o].l > r || t[o].r < l || target < t[o].min || target > t[o].max {
return -1
}
if t[o].l == t[o].r {
return t[o].l
}
t.spread(o)
idx := t.findFirst(o<<1, l, r, target)
if idx < 0 {
// 去右子树找
idx = t.findFirst(o<<1|1, l, r, target)
}
return idx
}

func longestBalanced(nums []int) (ans int) {
n := len(nums)
t := make(lazySeg, 2<<bits.Len(uint(n)))
t.build(1, 0, n)

last := map[int]int{} // nums 的元素上一次出现的位置
curSum := 0
for i := 1; i <= n; i++ {
x := nums[i-1]
v := x%2*2 - 1
if j := last[x]; j == 0 { // 首次遇到 x
curSum += v
t.update(1, i, n, v) // sum[i:] 增加 v
} else { // 再次遇到 x
t.update(1, j, i-1, -v) // 撤销之前对 sum[j:i] 的增加
}
last[x] = i

// 把 i-1 优化成 i-1-ans，因为在下标 > i-1-ans 中搜索是没有意义的，不会把答案变大
j := t.findFirst(1, 0, i-1-ans, curSum)
if j >= 0 {
ans = i - j // 如果找到了，那么答案肯定会变大
}
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n\log n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

方法二：分块

见分块思想。

这个做法没有用到 $\textit{sum}$ 数组的特殊性质，支持区间更新、查询任意值首次出现的位置。

每块维护块内 $\textit{sum}[i]$ 首次出现的位置，以及区间加的 Lazy tag。

###go

func longestBalanced(nums []int) (ans int) {
n := len(nums)
B := int(math.Sqrt(float64(n+1)))/2 + 1
sum := make([]int, n+1)

// === 分块模板开始 ===
// 用分块维护 sum
type block struct {
l, r int // [l,r) 左闭右开
todo int
pos  map[int]int
}
blocks := make([]block, n/B+1)
calcPos := func(l, r int) map[int]int {
pos := map[int]int{}
for j := r - 1; j >= l; j-- {
pos[sum[j]] = j
}
return pos
}
for i := 0; i <= n; i += B {
r := min(i+B, n+1)
pos := calcPos(i, r)
blocks[i/B] = block{i, r, 0, pos}
}

// sum[l:r] 增加 v
rangeAdd := func(l, r, v int) {
for i := range blocks {
b := &blocks[i]
if b.r <= l {
continue
}
if b.l >= r {
break
}
if l <= b.l && b.r <= r { // 完整块
b.todo += v
} else { // 部分块，直接重算
for j := b.l; j < b.r; j++ {
sum[j] += b.todo
if l <= j && j < r {
sum[j] += v
}
}
b.pos = calcPos(b.l, b.r)
b.todo = 0
}
}
}

// 返回 sum[:r] 中第一个 v 的下标
// 如果没有 v，返回 n
findFirst := func(r, v int) int {
for i := range blocks {
b := &blocks[i]
if b.r <= r { // 完整块，直接查哈希表
if j, ok := b.pos[v-b.todo]; ok {
return j
}
} else { // 部分块，暴力查找
for j := b.l; j < r; j++ {
if sum[j] == v-b.todo {
return j
}
}
break
}
}
return n
}
// === 分块模板结束 ===

last := map[int]int{} // nums 的元素上一次出现的位置
for i := 1; i <= n; i++ {
x := nums[i-1]
v := x%2*2 - 1
if j := last[x]; j == 0 { // 首次遇到 x
rangeAdd(i, n+1, v) // sum[i:] 增加 v
} else { // 再次遇到 x
rangeAdd(j, i, -v) // 撤销之前对 sum[j:i] 的增加
}
last[x] = i

s := sum[i] + blocks[i/B].todo // sum[i] 的实际值
ans = max(ans, i-findFirst(i-ans, s)) // 优化右边界
}
return
}

复杂度分析

时间复杂度：$\mathcal{O}(n\sqrt n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
空间复杂度：$\mathcal{O}(n)$。

相似题目

HH 的项链

专题训练

见下面数据结构题单的「§8.4 Lazy 线段树」和「十、根号算法」。

分类题单

如何科学刷题？

我的题解精选（已分类）

LeetCode 每日一题题解
二叉搜索树 -> 数组 -> 二叉搜索树（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2026年1月28日 09:13

二叉搜索树 -> 数组 -> 二叉搜索树（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2026年1月28日 09:13

由于输入的是一棵二叉搜索树，节点值满足 $左子树 < 根 < 右子树$，所以通过一次 94. 二叉树的中序遍历，把遍历到的节点值添加到一个数组中，可以直接得到一个递增数组，无需排序。

然后 108. 将有序数组转换为二叉搜索树，做法见我的题解。

###py

class Solution:
    # 94. 二叉树的中序遍历
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            dfs(node.left)        # 左
            ans.append(node.val)  # 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node.right)       # 右

        ans = []
        dfs(root)
        return ans

    # 108. 将有序数组转换为二叉搜索树
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        m = len(nums) // 2
        left = self.sortedArrayToBST(nums[:m])
        right = self.sortedArrayToBST(nums[m + 1:])
        return TreeNode(nums[m], left, right)

    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        nums = self.inorderTraversal(root)
        return self.sortedArrayToBST(nums)

###py

class Solution:
    # 94. 二叉树的中序遍历
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return
            dfs(node.left)        # 左
            ans.append(node.val)  # 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node.right)       # 右

        ans = []
        dfs(root)
        return ans

    # 108. 将有序数组转换为二叉搜索树
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 把 nums[left:right] 转成平衡二叉搜索树
        def dfs(left: int, right: int) -> Optional[TreeNode]:
            if left == right:
                return None
            m = (left + right) // 2
            return TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))

        return dfs(0, len(nums))

    def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        nums = self.inorderTraversal(root)
        return self.sortedArrayToBST(nums)

###java

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> nums = inorderTraversal(root);
        return sortedArrayToBST(nums);
    }

    // 94. 二叉树的中序遍历
    private List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(ans, root);
        return ans;
    }

    private void dfs(List<Integer> ans, TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(ans, node.left);  // 左
        ans.add(node.val);    // 根（这行代码移到前面就是前序，移到后面就是后序）
        dfs(ans, node.right); // 右
    }

    // 108. 将有序数组转换为二叉搜索树
    private TreeNode sortedArrayToBST(List<Integer> nums) {
        return buildBST(nums, 0, nums.size());
    }

    // 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
    private TreeNode buildBST(List<Integer> nums, int left, int right) {
        if (left == right) {
            return null;
        }
        int m = (left + right) >>> 1;
        return new TreeNode(nums.get(m), buildBST(nums, left, m), buildBST(nums, m + 1, right));
    }
}

###cpp

class Solution {
    // 94. 二叉树的中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;

        // lambda 递归
        auto dfs = [&](this auto&& dfs, TreeNode* node) -> void {
            if (node == nullptr) {
                return;
            }
            dfs(node->left);          // 左
            ans.push_back(node->val); // 根（这行代码移到前面就是前序，移到后面就是后序）
            dfs(node->right);         // 右
        };

        dfs(root);
        return ans;
    }

    // 108. 将有序数组转换为二叉搜索树
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
        auto dfs = [&](this auto&& dfs, int left, int right) -> TreeNode* {
            if (left == right) {
                return nullptr;
            }
            int m = left + (right - left) / 2;
            return new TreeNode(nums[m], dfs(left, m), dfs(m + 1, right));
        };

        return dfs(0, nums.size());
    }

public:
    TreeNode* balanceBST(TreeNode* root) {
        auto nums = inorderTraversal(root);
        return sortedArrayToBST(nums);
    }
};

###c

// 获取树的大小（节点个数）
int getSize(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + getSize(root->left) + getSize(root->right);
}

// 94. 二叉树的中序遍历
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* ans = malloc(getSize(root) * sizeof(int));
    *returnSize = 0;

    void dfs(struct TreeNode* node) {
        if (node == NULL) {
            return;
        }
        dfs(node->left);                  // 左
        ans[(*returnSize)++] = node->val; // 根（这行代码移到前面就是前序，移到后面就是后序）
        dfs(node->right);                 // 右
    }

    dfs(root);
    return ans;
}

// 108. 将有序数组转换为二叉搜索树
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    // 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
    struct TreeNode* dfs(int left, int right) {
        if (left == right) {
            return NULL;
        }
        int m = left + (right - left) / 2;
        struct TreeNode* node = malloc(sizeof(struct TreeNode));
        node->val = nums[m];
        node->left = dfs(left, m);
        node->right = dfs(m + 1, right);
        return node;
    }

    return dfs(0, numsSize);
}

struct TreeNode* balanceBST(struct TreeNode* root) {
    int numsSize;
    int* nums = inorderTraversal(root, &numsSize);
    root = sortedArrayToBST(nums, numsSize);

    free(nums);
    return root;
}

###go

// 94. 二叉树的中序遍历
func inorderTraversal(root *TreeNode) (ans []int) {
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)              // 左
ans = append(ans, node.Val) // 根（这行代码移到前面就是前序，移到后面就是后序）
dfs(node.Right)             // 右
}
dfs(root)
return
}

// 108. 将有序数组转换为二叉搜索树
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
m := len(nums) / 2
return &TreeNode{
Val:   nums[m],
Left:  sortedArrayToBST(nums[:m]),
Right: sortedArrayToBST(nums[m+1:]),
}
}

func balanceBST(root *TreeNode) *TreeNode {
nums := inorderTraversal(root)
return sortedArrayToBST(nums)
}

###js

// 94. 二叉树的中序遍历
var inorderTraversal = function(root) {
    function dfs(node) {
        if (node === null) {
            return;
        }
        dfs(node.left);     // 左
        ans.push(node.val); // 根（这行代码移到前面就是前序，移到后面就是后序）
        dfs(node.right);    // 右
    }

    const ans = [];
    dfs(root);
    return ans;
};

// 108. 将有序数组转换为二叉搜索树
var sortedArrayToBST = function(nums) {
    // 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
    function dfs(left, right) {
        if (left === right) {
            return null;
        }
        const m = Math.floor((left + right) / 2);
        return new TreeNode(nums[m], dfs(left, m), dfs(m + 1, right));
    }
    return dfs(0, nums.length);
};

var balanceBST = function(root) {
    const nums = inorderTraversal(root)
    return sortedArrayToBST(nums)
};

###rust

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    // 94. 二叉树的中序遍历
    fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
            if let Some(node) = node {
                let n = node.borrow();
                dfs(&n.left, ans);  // 左
                ans.push(n.val);    // 根（这行代码移到前面就是前序，移到后面就是后序）
                dfs(&n.right, ans); // 右
            }
        }

        let mut ans = vec![];
        dfs(&root, &mut ans);
        ans
    }

    // 108. 将有序数组转换为二叉搜索树
    fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        fn dfs(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
            if nums.is_empty() {
                return None;
            }
            let m = nums.len() / 2;
            Some(Rc::new(RefCell::new(TreeNode {
                val: nums[m],
                left: dfs(&nums[..m]),
                right: dfs(&nums[m + 1..]),
            })))
        }
        dfs(&nums)
    }
    
    pub fn balance_bst(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let nums = Self::inorder_traversal(root);
        Self::sorted_array_to_bst(nums)
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是二叉树的节点个数。注：Python 的第一种写法有切片的复制开销，二叉树的每一层都需要花费 $\mathcal{O}(n)$ 的时间，一共有 $\mathcal{O}(\log n)$ 层，所以时间复杂度是 $\mathcal{O}(n\log n)$；第二种写法避免了切片的复制开销，时间复杂度是 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(n)$。

专题训练

见下面树题单的「§2.9 二叉搜索树」和「§2.10 创建二叉树」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
【视频】如何灵活运用递归？（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2022年12月10日 18:20

【视频】如何灵活运用递归？（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2022年12月10日 18:20

看完这两期视频，让你对递归的理解更上一层楼！

【基础算法精讲 09】

【基础算法精讲 10】

答疑

问：代码中的 $-1$ 是怎么产生的？怎么返回的？

答：在某次递归中，发现左右子树高度绝对差大于 $1$，我们会返回 $-1$。这个 $-1$ 会一路向上不断返回，直到根节点。

写法一

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_h = get_height(node.left)
            right_h = get_height(node.right)
            if left_h == -1 or right_h == -1 or abs(left_h - right_h) > 1:
                return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        int rightH = getHeight(node.right);
        if (leftH == -1 || rightH == -1 || Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        return Math.max(leftH, rightH) + 1;
    }
}

class Solution {
    int get_height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_h = get_height(node->left);
        int right_h = get_height(node->right);
        if (left_h == -1 || right_h == -1 || abs(left_h - right_h) > 1) {
            return -1;
        }
        return max(left_h, right_h) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }
    int left_h = getHeight(node->left);
    int right_h = getHeight(node->right);
    if (left_h == -1 || right_h == -1 || abs(left_h - right_h) > 1) {
        return -1;
    }
    return MAX(left_h, right_h) + 1;
}

bool isBalanced(struct TreeNode* root) {
    return getHeight(root) != -1;
}

func getHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftH := getHeight(node.Left)
    rightH := getHeight(node.Right)
    if leftH == -1 || rightH == -1 || abs(leftH-rightH) > 1 {
        return -1
    }
    return max(leftH, rightH) + 1
}

func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func abs(x int) int { if x < 0 { return -x }; return x }

function getHeight(node) {
    if (node === null) {
        return 0;
    }
    const leftH = getHeight(node.left);
    const rightH = getHeight(node.right);
    if (leftH === -1 || rightH === -1 || Math.abs(leftH - rightH) > 1) {
        return -1;
    }
    return Math.max(leftH, rightH) + 1;
}

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn get_height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = node {
                let node = node.borrow();
                let left_h = get_height(&node.left);
                let right_h = get_height(&node.right);
                if left_h == -1 || right_h == -1 || (left_h - right_h).abs() > 1 {
                    return -1;
                }
                return left_h.max(right_h) + 1;
            }
            0
        }
        get_height(&root) != -1
    }
}

写法二

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_h = get_height(node.left)
            if left_h == -1:
                return -1  # 提前退出，不再递归
            right_h = get_height(node.right)
            if right_h == -1 or abs(left_h - right_h) > 1:
                return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftH = getHeight(node.left);
        if (leftH == -1) {
            return -1; // 提前退出，不再递归
        }
        int rightH = getHeight(node.right);
        if (rightH == -1 || Math.abs(leftH - rightH) > 1) {
            return -1;
        }
        return Math.max(leftH, rightH) + 1;
    }
}

class Solution {
    int get_height(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int left_h = get_height(node->left);
        if (left_h == -1) {
            return -1; // 提前退出，不再递归
        }
        int right_h = get_height(node->right);
        if (right_h == -1 || abs(left_h - right_h) > 1) {
            return -1;
        }
        return max(left_h, right_h) + 1;
    }

public:
    bool isBalanced(TreeNode* root) {
        return get_height(root) != -1;
    }
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int getHeight(struct TreeNode* node) {
    if (node == NULL) {
        return 0;
    }

    int left_h = getHeight(node->left);
    if (left_h == -1) {
        return -1; // 提前退出，不再递归
    }

    int right_h = getHeight(node->right);
    if (right_h == -1 || abs(left_h - right_h) > 1) {
        return -1;
    }

    return MAX(left_h, right_h) + 1;
}

bool isBalanced(struct TreeNode* root) {
    return getHeight(root) != -1;
}

func getHeight(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftH := getHeight(node.Left)
    if leftH == -1 {
        return -1 // 提前退出，不再递归
    }
    rightH := getHeight(node.Right)
    if rightH == -1 || abs(leftH-rightH) > 1 {
        return -1
    }
    return max(leftH, rightH) + 1
}

func isBalanced(root *TreeNode) bool {
    return getHeight(root) != -1
}

func abs(x int) int { if x < 0 { return -x }; return x }

function getHeight(node) {
    if (node === null) {
        return 0;
    }
    const leftH = getHeight(node.left);
    if (leftH === -1) {
        return -1; // 提前退出，不再递归
    }
    const rightH = getHeight(node.right);
    if (rightH === -1 || Math.abs(leftH - rightH) > 1) {
        return -1;
    }
    return Math.max(leftH, rightH) + 1;
}

var isBalanced = function(root) {
    return getHeight(root) !== -1;
};

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn get_height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            if let Some(node) = node {
                let node = node.borrow();
                let left_h = get_height(&node.left);
                if left_h == -1 {
                    return -1; // 提前退出，不再递归
                }
                let right_h = get_height(&node.right);
                if right_h == -1 || (left_h - right_h).abs() > 1 {
                    return -1;
                }
                return left_h.max(right_h) + 1;
            }
            0
        }
        get_height(&root) != -1
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为二叉树的节点个数。
空间复杂度：$\mathcal{O}(n)$。最坏情况下，二叉树退化成一条链，递归需要 $\mathcal{O}(n)$ 的栈空间。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
前后缀分解，一张图秒懂！（附动态规划）Python/Java/C++/Goendlesscheng
2023年3月5日 22:02

前后缀分解，一张图秒懂！（附动态规划）Python/Java/C++/Go

LeetCode 每日一题题解

作者 endlesscheng

2023年3月5日 22:02

方法一：前后缀分解（两次遍历）

答疑

问：为什么把 if-else 写成 (c - 'a') * 2 - 1 会快很多？

答：CPU 在遇到分支（条件跳转指令）时会预测代码要执行哪个分支，如果预测正确，CPU 就会继续按照预测的路径执行程序。但如果预测失败，CPU 就需要回滚之前的指令并加载正确的指令，以确保程序执行的正确性。

对于本题的数据，字符 $\text{a'}$ 和 $\text{b'}$ 可以认为是随机出现的，在这种情况下分支预测就会有 $50%$ 的概率失败。失败导致的回滚和加载操作需要消耗额外的 CPU 周期，如果能用较小的代价去掉分支，对于本题的情况必然可以带来效率上的提升。

注：这种优化方法会降低可读性，不建议在业务代码中使用。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = delete = s.count('a')
        for c in s:
            delete -= 1 if c == 'a' else -1
            if delete < ans:  # 手动计算 min 会快很多
                ans = delete
        return ans

class Solution {
    public int minimumDeletions(String S) {
        char[] s = S.toCharArray();
        int del = 0;
        for (char c : s) {
            del += 'b' - c; // 统计 'a' 的个数
        }

        int ans = del;
        for (char c : s) {
            // 'a' -> -1    'b' -> 1
            del += (c - 'a') * 2 - 1;
            ans = Math.min(ans, del);
        }
        return ans;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int del = 0;
        for (char c : s) {
            del += 'b' - c; // 统计 'a' 的个数
        }

        int ans = del;
        for (char c : s) {
            // 'a' -> -1    'b' -> 1
            del += (c - 'a') * 2 - 1;
            ans = min(ans, del);
        }
        return ans;
    }
};

func minimumDeletions(s string) int {
del := strings.Count(s, "a")
ans := del
for _, c := range s {
// 'a' -> -1    'b' -> 1
del += int((c-'a')*2 - 1)
ans = min(ans, del)
}
return ans
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(1)$。

方法二：动态规划（一次遍历）

如果你还不熟悉动态规划（包括空间优化），可以先看看动态规划入门。

考虑 $s$ 的最后一个字母：

如果它是 $\text{`b'}$，则无需删除，问题规模缩小，变成「使 $s$ 的前 $n-1$ 个字母平衡的最少删除次数」。
如果它是 $\text{`a'}$：
- 删除它，则答案为「使 $s$ 的前 $n-1$ 个字母平衡的最少删除次数」加上 $1$。
- 保留它，那么前面的所有 $\text{`b'}$ 都要删除；

设 $\textit{cntB}_i$ 为前 $i$ 个字母中 $\text{`b'}$ 的个数。定义 $f_i$ 表示使 $s$ 的前 $i$ 个字母平衡的最少删除次数：

如果第 $i$ 个字母是 $\text{`b'}$，则 $f_i = f_{i-1}$；
如果第 $i$ 个字母是 $\text{`a'}$，则 $f_i = \min(f_{i-1}+1,\textit{cntB}_i)$。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        f = cnt_b = 0
        for c in s:
            if c == 'b':
                cnt_b += 1  # f 值不变
            else:
                f = min(f + 1, cnt_b)
        return f

class Solution {
    public int minimumDeletions(String s) {
        int f = 0;
        int cntB = 0;
        for (char c : s.toCharArray()) {
            if (c == 'b') {
                cntB++; // f 值不变
            } else {
                f = Math.min(f + 1, cntB);
            }
        }
        return f;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int f = 0, cnt_b = 0;
        for (char c : s) {
            if (c == 'b') {
                cnt_b++; // f 值不变
            } else {
                f = min(f + 1, cnt_b);
            }
        }
        return f;
    }
};

func minimumDeletions(s string) int {
    f, cntB := 0, 0
    for _, c := range s {
        if c == 'b' { // f 值不变
            cntB++
        } else {
            f = min(f+1, cntB)
        }
    }
    return f
}

这份代码也可以像方法一那样去掉分支：

如果第 $i$ 个字母是 $\text{b'}$，则 $\textit{cntB}$ 增加 $1$，$f[i] = \min(f[i-1],\textit{cntB})$，这里也考虑全部删除 $\text{b'}$；
如果第 $i$ 个字母是 $\text{`a'}$，则 $\textit{cntB}$ 增加 $0$，$f[i] = \min(f[i-1]+1,\textit{cntB})$。

这两种情况可以合并成：

设当前字母为 $c$，$x=c-\text{`a'}$，则 $\textit{cntB}$ 增加 $x$，$f[i] = \min(f[i-1]+(x\oplus 1),\textit{cntB})$。其中 $\oplus$ 表示异或。

class Solution:
    def minimumDeletions(self, s: str) -> int:
        f = cnt_b = 0
        for c in s:
            x = ord(c) - ord('a')  # ord 很慢
            cnt_b += x
            f = min(f + (x ^ 1), cnt_b)
        return f

class Solution {
    public int minimumDeletions(String s) {
        int f = 0;
        int cntB = 0;
        for (char c : s.toCharArray()) {
            int x = c - 'a';
            cntB += x;
            f = Math.min(f + (x ^ 1), cntB);
        }
        return f;
    }
}

class Solution {
public:
    int minimumDeletions(string s) {
        int f = 0, cnt_b = 0;
        for (char c : s) {
            int x = c - 'a';
            cnt_b += x;
            f = min(f + (x ^ 1), cnt_b);
        }
        return f;
    }
};

func minimumDeletions(s string) int {
    f, cntB := 0, 0
    for _, c := range s {
        x := int(c - 'a')
        cntB += x
        f = min(f+(x^1), cntB)
    }
    return f
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $s$ 的长度。
空间复杂度：$\mathcal{O}(1)$。

专题训练

见下面动态规划题单的「专题：前后缀分解」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

LeetCode 每日一题题解
简洁写法（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2024年12月8日 12:20

简洁写法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2024年12月8日 12:20

操作相当于从下标 $i$ 移动到下标 $i+\textit{nums}[i]$。

如果 $i+\textit{nums}[i]$ 下标越界呢？

需要把 $i+\textit{nums}[i]$ 调整到 $[0,n-1]$ 范围中。具体来说，把下标 $i+\textit{nums}[i]$ 模 $n$。比如 $n=4$，在循环数组中，正数下标 $5,9,13,\ldots$ 都是下标 $1$，负数下标 $-3,-7,-11,\ldots$ 也都是下标 $1$。

不了解取模的同学，请看模运算的世界：当加减乘除遇上取模。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def constructTransformedArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        return [nums[(i + x) % n] for i, x in enumerate(nums)]

###java

class Solution {
    public int[] constructTransformedArray(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
        }
        return result;
    }
}

###cpp

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
        }
        return result;
    }
};

###c

int* constructTransformedArray(int* nums, int numsSize, int* returnSize) {
    int n = numsSize;
    int* result = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
    }
    *returnSize = n;
    return result;
}

###go

func constructTransformedArray(nums []int) []int {
n := len(nums)
result := make([]int, n)
for i, x := range nums {
result[i] = nums[((i+x)%n+n)%n] // 保证结果在 [0,n-1] 中
}
return result
}

###js

var constructTransformedArray = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    for (let i = 0; i < n; i++) {
        result[i] = nums[((i + nums[i]) % n + n) % n]; // 保证结果在 [0,n-1] 中
    }
    return result;
};

###rust

impl Solution {
    pub fn construct_transformed_array(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let m = n as i32;
        let mut result = vec![0; n];
        for i in 0..n {
            let j = ((i as i32 + nums[i]) % m + m) % m; // 保证结果在 [0,n-1] 中
            result[i] = nums[j as usize];
        }
        result
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
空间复杂度：$\mathcal{O}(1)$。返回值不计入。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

普通视图

方法一：BFS

复杂度分析

方法二：数学

分析

情况一：m 是偶数

情况二：m 是奇数

下界可以取到

特殊情况

上取整转成下取整

复杂度分析

分类题单

复杂度分析

分类题单

写法一

写法二

复杂度分析

专题训练

分类题单

方法一：暴力

复杂度分析

方法二：位运算滑窗

复杂度分析

分类题单

复杂度分析

专题训练

分类题单

方法一：暴力枚举

复杂度分析

方法二：上下界数位 DP

复杂度分析

方法三：组合数学

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

专题训练

分类题单

复杂度分析

分类题单

复杂度分析

附：库函数写法

分类题单

写法一

写法二

复杂度分析

分类题单

优化前

优化

复杂度分析

相似题目

分类题单

问题拆解

子串只包含一种字母

子串只包含两种字母

子串包含三种字母

复杂度分析

专题训练

分类题单

写法一：暴力枚举

优化前

复杂度分析

优化

复杂度分析

写法二：枚举右，维护左

复杂度分析

分类题单

前置题目/知识

转化

方法一：Lazy 线段树

复杂度分析

方法二：分块

复杂度分析

相似题目

专题训练

分类题单

复杂度分析