给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

 

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

 

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

前言

设 $\textit{strs}[i]$ 中 $0$ 的个数为 $\textit{cnt}_0[i]$，$1$ 的个数为 $\textit{cnt}_1[i]$，那么本题相当于：

• 有一个容量为 $(m,n)$ 的背包，至多可以装入 $m$ 个 $0$ 和 $n$ 个 $1$。现在有 $n$ 个物品，每个物品的体积为 $(\textit{cnt}_0[i],\textit{cnt}_1[i])$，表示该物品有 $\textit{cnt}_0[i]$ 个 $0$ 和 $\textit{cnt}_1[i]$ 个 $1$。问：最多可以选多少个物品？

这相当于背包有两种体积（二维），所以在定义状态的时候，相比只有一种体积的 0-1 背包，要多加一个参数。

如果你不了解 0-1 背包，请看【基础算法精讲 18】。

一、记忆化搜索

在一维 0-1 背包的基础上，多加一个参数，即定义 $\textit{dfs}(i,j,k)$ 表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。

考虑 $\textit{strs}[i]$ 选或不选：

• 不选：问题变成在 $[0,i-1]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串，即 $\textit{dfs}(i,j,k) = \textit{dfs}(i-1,j,k)$。
• 选：如果 $j\ge \textit{cnt}_0[i]$ 并且 $k\ge \textit{cnt}_1[i]$ 则可以选。问题变成在 $[0,i-1]$ 中选字符串，在 $0$ 的个数至多为 $j-\textit{cnt}_0[i]$，$1$ 的个数至多为 $k-\textit{cnt}_1[i]$ 的约束下，至多可以选多少个字符串，即 $\textit{dfs}(i,j,k) = \textit{dfs}(i-1,j-\textit{cnt}_0[i],k-\textit{cnt}_1[i]) + 1$。

两种情况取最大值，得

$$
\textit{dfs}(i,j,k) = \max(\textit{dfs}(i-1,j,k), \textit{dfs}(i-1,j-\textit{cnt}_0[i],k-\textit{cnt}_1[i]) + 1)
$$

如果

递归边界：$\textit{dfs}(-1,j,k)=0$。此时没有物品可以选。

递归入口：$\textit{dfs}(k-1,m,n)$，这是原问题，也是答案。其中 $k$ 为 $\textit{strs}$ 的长度。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        cnt0 = [s.count('0') for s in strs]

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, k: int) -> int:
            if i < 0:
                return 0
            res = dfs(i - 1, j, k)  # 不选 strs[i]
            cnt1 = len(strs[i]) - cnt0[i]
            if j >= cnt0[i] and k >= cnt1:
                res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1)  # 选 strs[i]
            return res

        return dfs(len(strs) - 1, m, n)

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int k = strs.length;
        int[] cnt0 = new int[k];
        for (int i = 0; i < k; i++) {
            cnt0[i] = (int) strs[i].chars().filter(ch -> ch == '0').count();
        }

        int[][][] memo = new int[strs.length][m + 1][n + 1];
        for (int[][] mat : memo) {
            for (int[] arr : mat) {
                Arrays.fill(arr, -1); // -1 表示没有计算过
            }
        }
        return dfs(k - 1, m, n, strs, cnt0, memo);
    }

    private int dfs(int i, int j, int k, String[] strs, int[] cnt0, int[][][] memo) {
        if (i < 0) {
            return 0;
        }
        if (memo[i][j][k] != -1) { // 之前计算过
            return memo[i][j][k];
        }
        // 不选 strs[i]
        int res = dfs(i - 1, j, k, strs, cnt0, memo);  
        int cnt1 = strs[i].length() - cnt0[i];
        if (j >= cnt0[i] && k >= cnt1) {
            // 选 strs[i]
            res = Math.max(res, dfs(i - 1, j - cnt0[i], k - cnt1, strs, cnt0, memo) + 1);
        }
        return memo[i][j][k] = res; // 记忆化
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> cnt0(strs.size());
        for (int i = 0; i < strs.size(); i++) {
            cnt0[i] = ranges::count(strs[i], '0');
        }

        vector memo(strs.size(), vector(m + 1, vector<int>(n + 1, -1))); // -1 表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0) {
                return 0;
            }
            int& res = memo[i][j][k]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }
            res = dfs(i - 1, j, k); // 不选 strs[i]
            int cnt1 = strs[i].size() - cnt0[i];
            if (j >= cnt0[i] && k >= cnt1) {
                res = max(res, dfs(i - 1, j - cnt0[i], k - cnt1) + 1); // 选 strs[i]
            }
            return res;
        };
        return dfs(strs.size() - 1, m, n);
    }
};

func findMaxForm(strs []string, m, n int) int {
    k := len(strs)
    cnt0 := make([]int, k)
    for i, s := range strs {
        cnt0[i] = strings.Count(s, "0")
    }

    memo := make([][][]int, k)
    for i := range memo {
        memo[i] = make([][]int, m+1)
        for j := range memo[i] {
            memo[i][j] = make([]int, n+1)
            for k := range memo[i][j] {
                memo[i][j][k] = -1 // -1 表示没有计算过
            }
        }
    }
    var dfs func(int, int, int) int
    dfs = func(i, j, k int) int {
        if i < 0 {
            return 0
        }
        p := &memo[i][j][k]
        if *p != -1 { // 之前计算过
            return *p
        }
        res := dfs(i-1, j, k) // 不选 strs[i]
        cnt1 := len(strs[i]) - cnt0[i]
        if j >= cnt0[i] && k >= cnt1 {
            res = max(res, dfs(i-1, j-cnt0[i], k-cnt1)+1) // 选 strs[i]
        }
        *p = res // 记忆化
        return res
    }
    return dfs(k-1, m, n)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(kmn)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(kmn)$。
• 空间复杂度：$\mathcal{O}(kmn)$。保存多少状态，就需要多少空间。

二、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1][j][k]$ 的定义和 $\textit{dfs}(i,j,k)$ 的定义是一样的，都表示在 $[0,i]$ 中选字符串，在 $0$ 的个数至多为 $j$，$1$ 的个数至多为 $k$ 的约束下，至多可以选多少个字符串。这里 $+1$ 是为了把 $\textit{dfs}(-1,j,k)$ 这个状态也翻译过来，这样我们可以把 $f[0][j][k]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：

$$
f[i+1][j][k] = \max(f[i][j][k], f[i][j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$

初始值 $f[0][j][k]=0$，翻译自递归边界 $\textit{dfs}(-1,j,k)=0$。

答案为 $f[k][m][n]$，翻译自递归入口 $\textit{dfs}(k-1,m,n)$。其中 $k$ 为 $\textit{strs}$ 的长度。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[[0] * (n + 1) for _ in range(m + 1)] for _ in range(len(strs) + 1)]
        for i, s in enumerate(strs):
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            for j in range(m + 1):
                for k in range(n + 1):
                    if j >= cnt0 and k >= cnt1:
                        f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1)
                    else:
                        f[i + 1][j][k] = f[i][j][k]
        return f[-1][m][n]

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] f = new int[strs.length + 1][m + 1][n + 1];
        for (int i = 0; i < strs.length; i++) {
            int cnt0 = (int) strs[i].chars().filter(ch -> ch == '0').count();
            int cnt1 = strs[i].length() - cnt0;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= cnt0 && k >= cnt1) {
                        f[i + 1][j][k] = Math.max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
                    } else {
                        f[i + 1][j][k] = f[i][j][k];
                    }
                }
            }
        }
        return f[strs.length][m][n];
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(strs.size() + 1, vector(m + 1, vector<int>(n + 1)));
        for (int i = 0; i < strs.size(); i++) {
            int cnt0 = ranges::count(strs[i], '0');
            int cnt1 = strs[i].size() - cnt0;
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (j >= cnt0 && k >= cnt1) {
                        f[i + 1][j][k] = max(f[i][j][k], f[i][j - cnt0][k - cnt1] + 1);
                    } else {
                        f[i + 1][j][k] = f[i][j][k];
                    }
                }
            }
        }
        return f.back()[m][n];
    }
};

func findMaxForm(strs []string, m, n int) int {
    k := len(strs)
    f := make([][][]int, k+1)
    for i := range f {
        f[i] = make([][]int, m+1)
        for j := range f[i] {
            f[i][j] = make([]int, n+1)
        }
    }
    for i, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        for j := range m + 1 {
            for k := range n + 1 {
                if j >= cnt0 && k >= cnt1 {
                    f[i+1][j][k] = max(f[i][j][k], f[i][j-cnt0][k-cnt1]+1)
                } else {
                    f[i+1][j][k] = f[i][j][k]
                }
            }
        }
    }
    return f[k][m][n]
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。
• 空间复杂度：$\mathcal{O}(kmn)$。

三、空间优化

观察上面的状态转移方程，在计算 $f[i+1]$ 时，只会用到 $f[i]$，不会用到比 $i$ 更早的状态。

那么去掉第一个维度，把 $f[i+1]$ 和 $f[i]$ 保存到同一个二维数组中。

状态转移方程改为

$$
f[j][k] = \max(f[j][k], f[j-\textit{cnt}_0[i]][k-\textit{cnt}_1[i]] + 1)
$$

初始值 $f[j][k]=0$。

答案为 $f[m][n]$。

下面代码为什么要倒序循环，请看【基础算法精讲 18】。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            for j in range(m, cnt0 - 1, -1):
                for k in range(n, cnt1 - 1, -1):
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1)
        return f[m][n]

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];
        for (String s : strs) {
            int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
            int cnt1 = s.length() - cnt0;
            for (int j = m; j >= cnt0; j--) {
                for (int k = n; k >= cnt1; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return f[m][n];
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(m + 1, vector<int>(n + 1));
        for (string& s : strs) {
            int cnt0 = ranges::count(s, '0');
            int cnt1 = s.size() - cnt0;
            for (int j = m; j >= cnt0; j--) {
                for (int k = n; k >= cnt1; k--) {
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        return f[m][n];
    }
};

func findMaxForm(strs []string, m, n int) int {
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    for _, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        for j := m; j >= cnt0; j-- {
            for k := n; k >= cnt1; k-- {
                f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
            }
        }
    }
    return f[m][n]
}

进一步优化

比如 $n=m=90$，前 $3$ 个字符串总共有 $5$ 个 $0$ 和 $6$ 个 $1$，那么无论我们怎么选，也选不出几十个 $0$ 和 $1$，所以上面的代码中，其实有大量的循环是多余的。

为此，额外用两个变量 $\textit{sum}_0$ 和 $\textit{sum}_1$ 分别维护前 $i$ 个字符串中的 $0$ 的个数和 $1$ 的个数（但不能超过 $m$ 和 $n$）。循环的时候 $j$ 从 $\textit{sum}_0$ 开始，$k$ 从 $\textit{sum}_1$ 开始。

注意这个优化会导致只有一部分 $f[j][k]$ 被更新到，最大值并没有传递给 $f[m][n]$，可能留在二维数组中间的某个位置上。所以最后要遍历 $f$，取其中最大值作为答案。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        f = [[0] * (n + 1) for _ in range(m + 1)]
        sum0 = sum1 = 0
        for s in strs:
            cnt0 = s.count('0')
            cnt1 = len(s) - cnt0
            sum0 = min(sum0 + cnt0, m)
            sum1 = min(sum1 + cnt1, n)
            for j in range(sum0, cnt0 - 1, -1):
                for k in range(sum1, cnt1 - 1, -1):
                    v = f[j - cnt0][k - cnt1] + 1
                    if v > f[j][k]:  # 手写 max，效率更高
                        f[j][k] = v
        return max(map(max, f))

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] f = new int[m + 1][n + 1];
        int sum0 = 0;
        int sum1 = 0;
        for (String s : strs) {
            int cnt0 = (int) s.chars().filter(ch -> ch == '0').count();
            int cnt1 = s.length() - cnt0;
            sum0 = Math.min(sum0 + cnt0, m);
            sum1 = Math.min(sum1 + cnt1, n);
            for (int j = sum0; j >= cnt0; j--) {
                for (int k = sum1; k >= cnt1; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        int ans = 0;
        for (int[] row : f) {
            for (int v : row) {
                ans = Math.max(ans, v);
            }
        }
        return ans;
    }
}

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector f(m + 1, vector<int>(n + 1));
        int sum0 = 0, sum1 = 0;
        for (string& s : strs) {
            int cnt0 = ranges::count(s, '0');
            int cnt1 = s.size() - cnt0;
            sum0 = min(sum0 + cnt0, m);
            sum1 = min(sum1 + cnt1, n);
            for (int j = sum0; j >= cnt0; j--) {
                for (int k = sum1; k >= cnt1; k--) {
                    f[j][k] = max(f[j][k], f[j - cnt0][k - cnt1] + 1);
                }
            }
        }
        int ans = 0;
        for (auto& row : f) {
            ans = max(ans, ranges::max(row));
        }
        return ans;
    }
};

func findMaxForm(strs []string, m, n int) (ans int) {
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    sum0, sum1 := 0, 0
    for _, s := range strs {
        cnt0 := strings.Count(s, "0")
        cnt1 := len(s) - cnt0
        sum0 = min(sum0+cnt0, m)
        sum1 = min(sum1+cnt1, n)
        for j := sum0; j >= cnt0; j-- {
            for k := sum1; k >= cnt1; k-- {
                f[j][k] = max(f[j][k], f[j-cnt0][k-cnt1]+1)
            }
        }
    }
    for _, row := range f {
        ans = max(ans, slices.Max(row))
    }
    return
}

复杂度分析

• 时间复杂度：$\mathcal{O}(kmn+L)$，其中 $k$ 为 $\textit{strs}$ 的长度，$L$ 为 $\textit{strs}$ 中所有字符串的长度之和。
• 空间复杂度：$\mathcal{O}(mn)$。

更多相似题目，见 动态规划题单 中的「§3.1 0-1 背包」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 【本题相关】动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

（多维）01 背包

通常与「背包问题」相关的题考察的是 将原问题转换为「背包问题」的能力。

要将原问题转换为「背包问题」，往往需要从题目中抽象出「价值」与「成本」的概念。

这道题如果抽象成「背包问题」的话，应该是：

每个字符串的价值都是 1（对答案的贡献都是 1），选择的成本是该字符串中 1 的数量和 0 的数量。

问我们在 1 的数量不超过 $m$，0 的数量不超过 $n$ 的条件下，最大价值是多少。

由于每个字符串只能被选一次，且每个字符串的选与否对应了「价值」和「成本」，求解的问题也是「最大价值」是多少。

因此可以直接套用 01 背包的「状态定义」来做：

$f[k][i][j]$ 代表考虑前 k 件物品，在数字 1 容量不超过 $i$，数字 0 容量不超过 $j$ 的条件下的「最大价值」（每个字符串的价值均为 1）。

有了「状态定义」之后，「转移方程」也很好推导：

$$f[k][i][j] = \max(f[k - 1][i][j], f[k - 1][i - cnt[k][0]][j - cnt[k][1]] + 1)$$

其中 $cnt$ 数组记录的是字符串中出现的 $01$ 数量。

代码（为了方便理解，$P1$ 将第一件物品的处理单独抽了出来，也可以不抽出来，只需要将让物品下标从 $1$ 开始即可，见 $P2$）：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 预处理每一个字符包含 0 和 1 的数量
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one}; 
        }

        // 处理只考虑第一件物品的情况
        int[][][] f = new int[len][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;
            }
        }

        // 处理考虑其余物品的情况
        for (int k = 1; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第 k 件物品
                    int a = f[k-1][i][j];
                    // 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）
                    int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len-1][m][n];
    }
}

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zero++;    
                else one++;

            }
            cnt[i] = new int[]{zero, one}; 
        }
        int[][][] f = new int[len + 1][m + 1][n + 1];
        for (int k = 1; k <= len; k++) {
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    int a = f[k - 1][i][j];
                    int b = (i >= zero && j >= one) ? f[k - 1][i - zero][j - one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len][m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(k * m * n)$

---

滚动数组

根据「状态转移」可知，更新某个物品的状态时，只依赖于上一个物品的状态。

因此，可以使用「滚动数组」的方式进行空间优化。

代码（为了方便理解，$P1$ 将第一件物品的处理单独抽了出来，也可以不抽出来，只需要将让物品下标从 $1$ 开始即可，见 $P2$）：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 预处理每一个字符包含 0 和 1 的数量
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zero++;
                } else {
                    one++;
                }
            }
            cnt[i] = new int[]{zero, one}; 
        }

        // 处理只考虑第一件物品的情况
        // 「物品维度」修改为 2 
        int[][][] f = new int[2][m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                f[0][i][j] = (i >= cnt[0][0] && j >= cnt[0][1]) ? 1 : 0;
            }
        }

        // 处理考虑其余物品的情况
        for (int k = 1; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第 k 件物品
                    // 将 k-1 修改为 (k-1)&1
                    int a = f[(k-1)&1][i][j];
                    // 选择第 k 件物品（前提是有足够的 m 和 n 额度可使用）
                    // 将 k-1 修改为 (k-1)&1
                    int b = (i >= zero && j >= one) ? f[(k-1)&1][i-zero][j-one] + 1 : 0;
                    f[k&1][i][j] = Math.max(a, b);
                }
            }
        }
        // 将 len-1 修改为 (len-1)&1
        return f[(len-1)&1][m][n];
    }
}

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zero++;
                else one++; 
            }
            cnt[i] = new int[]{zero, one}; 
        }
        int[][][] f = new int[2][m + 1][n + 1];
        for (int k = 1; k <= len; k++) {
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    int a = f[(k-1) & 1][i][j];
                    int b = (i >= zero && j >= one) ? f[(k-1) & 1][i - zero][j - one] + 1 : 0;
                    f[k&1][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len&1][m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(m * n)$

---

一维空间优化

事实上，我们还能继续进行空间优化。

再次观察我们的「状态转移方程」发现：$f[k][i][j]$ 不仅仅依赖于上一行，还明确依赖于比 $i$ 小和比 $j$ 小的状态。

即可只依赖于「上一行」中「正上方」的格子，和「正上方左边」的格子。

对应到「朴素的 01 背包问题」依赖关系如图：

因此可直接参考「01 背包的空间优化」方式：取消掉「物品维度」，然后调整容量的遍历顺序。

代码：

###Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            int zero = 0, one = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '0') zero++;
                else one++;
            }
            cnt[i] = new int[]{zero, one};
        }
        int[][] f = new int[m + 1][n + 1];
        for (int k = 0; k < len; k++) {
            int zero = cnt[k][0], one = cnt[k][1];
            for (int i = m; i >= zero; i--) {
                for (int j = n; j >= one; j--) {
                    f[i][j] = Math.max(f[i][j], f[i - zero][j - one] + 1);
                }
            }
        }
        return f[m][n];
    }
}

• 时间复杂度：预处理字符串的复杂度为 $O(\sum_{i = 0}^{k - 1}len(strs[i]))$，处理状态转移的 $O(k * m * n)$。整体复杂度为：$O(k * m * n + \sum_{i = 0}^{k - 1}len(strs[i]))$
• 空间复杂度：$O(m * n)$

---

其他「背包」问题

看不懂「背包」解决方案？

以下是公主号讲过的「背包专题」系列目录，欢迎 关注 🍭🍭🍭 ：

1. 01背包 : 背包问题 第一讲

   1. 【练习】01背包 : 背包问题 第二讲

   2. 【学习&练习】01背包 : 背包问题 第三讲

   3. 【加餐/补充】01 背包：背包问题 第二十一讲

2. 完全背包 : 背包问题 第四讲

   1. 【练习】完全背包 : 背包问题 第五讲

   2. 【练习】完全背包 : 背包问题 第六讲

   3. 【练习】完全背包 : 背包问题 第七讲

3. 多重背包 : 背包问题 第八讲

4. 多重背包（优化篇）

   1. 【上】多重背包（优化篇）: 背包问题 第九讲

   2. 【下】多重背包（优化篇）: 背包问题 第十讲

5. 混合背包 : 背包问题 第十一讲

6. 分组背包 : 背包问题 第十二讲

   1. 【练习】分组背包 : 背包问题 第十三讲

7. 多维背包

   1. 【练习】多维背包 : 背包问题 第十四讲

   2. 【练习】多维背包 : 背包问题 第十五讲

8. 树形背包 : 背包问题 第十六讲

   1. 【练习篇】树形背包 : 背包问题 第十七讲

   2. 【练习篇】树形背包 : 背包问题 第十八讲

9. 背包求方案数

   1. 【练习】背包求方案数 : 背包问题 第十九讲

   2. 【练习】背包求方案数 : 背包问题 第十五讲

   [注：因为之前实在找不到题，这道「求方案数」题作为“特殊”的「多维费用背包问题求方案数」讲过]

10. 背包求具体方案

    1. 【练习】背包求具体方案 : 背包问题 第二十讲

11. 泛化背包

    1. 【练习】泛化背包

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

思路：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。

---

动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。

定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
状态转移方程：
$$dp[i][j][k]=
\begin{cases}
dp[i - 1][j][k], & 不选择当前考虑的字符串，至少是这个数值\
dp[i - 1][j - 当前字符串使用 ;0; 的个数][k - 当前字符串使用 ;1; 的个数] + 1 & 选择当前考虑的字符串
\end{cases}
$$
初始化：为了避免分类讨论，通常多设置一行。这里可以认为，第 $0$ 个字符串是空串。第 $0$ 行默认初始化为 $0$。
输出：输出是最后一个状态，即：dp[len][m][n]。

参考代码1：

###Java

public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];

        for (int i = 1; i <= len; i++) {
            // 注意：有一位偏移
            int[] count = countZeroAndOne(strs[i - 1]);
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // 先把上一行抄下来
                    dp[i][j][k] = dp[i - 1][j][k];
                    int zeros = count[0];
                    int ones = count[1];
                    if (j >= zeros && k >= ones) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    private int[] countZeroAndOne(String str) {
        int[] cnt = new int[2];
        for (char c : str.toCharArray()) {
            cnt[c - '0']++;
        }
        return cnt;
    }
}

第 5 步：思考优化空间

因为当前行只参考了上一行的值，因此可以使用「滚动数组」，也可以「从后向前赋值」。

参考代码2：这里选用「从后向前赋值」

###Java

public class Solution {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (String s : strs) {
            int[] zeroAndOne = calcZeroAndOne(s);
            int zeros = zeroAndOne[0];
            int ones = zeroAndOne[1];
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int[] calcZeroAndOne(String str) {
        int[] res = new int[2];
        for (char c : str.toCharArray()) {
            res[c - '0']++;
        }
        return res;
    }
}

给你一个大小为 n 的 非负 整数数组 nums 。你的任务是对该数组执行若干次（可能为 0 次）操作，使得 所有 元素都变为 0。

在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），将该子数组中所有 最小的非负整数 的设为 0。

返回使整个数组变为 0 所需的最少操作次数。

一个 子数组 是数组中的一段连续元素。

 

示例 1：

示例 2：

示例 3：

 

提示:

• 1 <= n == nums.length <= 105
• 0 <= nums[i] <= 105

分治

回顾示例 3 $\textit{nums}=[1,2,1,2,1,2]$ 的操作过程：

• 首先，只需要一次操作（选择整个数组），就可以把所有的最小值 $1$ 都变成 $0$。现在数组是 $[0,2,0,2,0,2]$。
• 这些被 $0$ 分割开的 $2$，无法合在一起操作（因为子数组会包含 $0$，导致 $2$ 无法变成 $0$），只能一个一个操作。

一般地：

1. 先通过一次操作，把 $\textit{nums}$ 的最小值都变成 $0$（如果最小值已经是 $0$ 则跳过这步）。
2. 此时 $\textit{nums}$ 被这些 $0$ 划分成了若干段，后续操作只能在每段内部，不能跨段操作（否则子数组会包含 $0$）。每一段是规模更小的子问题，可以用第一步的方法解决。这样我们可以写一个递归去处理。递归边界：如果操作后全为 $0$，直接返回。

找最小值可以用 ST 表或者线段树，但这种做法很麻烦。有没有简单的做法呢？

单调栈

从左往右遍历数组，只在「必须要操作」的时候，才把答案加一。

什么时候必须要操作？

示例 3 $\textit{nums}=[1,2,1,2,1,2]$，因为 $2$ 左右两侧都有小于 $2$ 的数，需要单独操作。

又例如 $\textit{nums}=[1,2,3,2,1]$：

• 遍历到第二个 $2$ 时，可以知道 $3$ 左右两侧都有小于 $3$ 的数，所以 $3$ 必须要操作一次，答案加一。注意这不表示第一次操作的是 $3$，而是某次操作会把 $3$ 变成 $0$。
• 遍历到末尾 $1$ 时，可以知道中间的两个 $2$，左边有 $1$，右边也有 $1$，必须操作一次，答案加一。比如选择 $[2,3,2]$ 可以把这两个 $2$ 都变成 $0$。
• 最后，数组中的 $1$ 需要操作一次都变成 $0$。

我们怎么知道「$3$ 左右两侧都有小于 $3$ 的数」？

遍历数组的同时，把遍历过的元素用栈记录：

• 如果当前元素比栈顶大（或者栈为空），那么直接入栈。
• 如果当前元素比栈顶小，那么对于栈顶来说，左边（栈顶倒数第二个数）比栈顶小（原因后面解释），右边（当前元素）也比栈顶小，所以栈顶必须操作一次。然后弹出栈顶。
• 如果当前元素等于栈顶，可以在同一次操作中把当前元素与栈顶都变成 $0$，所以无需入栈。注意这保证了栈中没有重复元素。

如果当前元素比栈顶小，就弹出栈顶，我们会得到一个底小顶大的单调栈，这就保证了「对于栈顶来说，左边（栈顶倒数第二个数）比栈顶小」。

遍历结束后，因为栈是严格递增的，所以栈中每个非零数字都需要操作一次。

代码实现时，可以直接把 $\textit{nums}$ 当作栈。

具体请看 视频讲解，欢迎点赞关注~

###py

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        st = []
        for x in nums:
            while st and x < st[-1]:
                st.pop()
                ans += 1
            # 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
            if not st or x != st[-1]:
                st.append(x)
        return ans + len(st) - (st[0] == 0)  # 0 不需要操作

###py

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        top = -1  # 栈顶下标（把 nums 当作栈）
        for x in nums:
            while top >= 0 and x < nums[top]:
                top -= 1  # 出栈
                ans += 1
            # 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
            if top < 0 or x != nums[top]:
                top += 1
                nums[top] = x  # 入栈
        return ans + top + (nums[0] > 0)

###java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        int top = -1; // 栈顶下标（把 nums 当作栈）
        for (int x : nums) {
            while (top >= 0 && x < nums[top]) {
                top--; // 出栈
                ans++;
            }
            // 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
            if (top < 0 || x != nums[top]) {
                nums[++top] = x; // 入栈
            }
        }
        return ans + top + (nums[0] > 0 ? 1 : 0);
    }
}

###cpp

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        int top = -1; // 栈顶下标（把 nums 当作栈）
        for (int x : nums) {
            while (top >= 0 && x < nums[top]) {
                top--; // 出栈
                ans++;
            }
            // 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
            if (top < 0 || x != nums[top]) {
                nums[++top] = x; // 入栈
            }
        }
        return ans + top + (nums[0] > 0);
    }
};

###go

func minOperations(nums []int) (ans int) {
st := nums[:0] // 原地
for _, x := range nums {
for len(st) > 0 && x < st[len(st)-1] {
st = st[:len(st)-1]
ans++
}
// 如果 x 与栈顶相同，那么 x 与栈顶可以在同一次操作中都变成 0，x 无需入栈
if len(st) == 0 || x != st[len(st)-1] {
st = append(st, x)
}
}
if st[0] == 0 { // 0 不需要操作
ans--
}
return ans + len(st)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。每个元素至多入栈出栈各一次，所以二重循环的循环次数是 $\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$ 或 $\mathcal{O}(1)$。原地做法可以做到 $\mathcal{O}(1)$ 空间。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

解法：贪心 & 单调栈

首先，由于每次操作只能把一种元素变成 $0$，因此答案至少是元素种数。那为什么答案不一定等于元素种数呢？考虑题目中的样例 nums = [1, 2, 1, 2, 1, 2]，当我们把所有 $1$ 都变成 $0$ 后，nums = [0, 2, 0, 2, 0, 2]，这时候的三个 $2$ 被更小的 $0$ 隔开了，无法在同一次操作内处理掉。

也就是说，我们每次只考虑一种元素。如果两元素之间有其它更小的元素，那么这两个元素无法在同一次操作内处理掉，答案加 $1$。

怎么知道两个元素之间有没有更小的元素呢？我们可以用单调栈求出每个元素右边最近的更小元素。假设下标 $i$ 右边最近的更小元素下标为 $f_i$，那么考虑下标 $i$ 和 $j$ 之间有没有更小元素时，只要检查是否 $f_i < j$ 即可。不熟悉单调栈的读者可以学习 leetcode 496. 下一个更大元素 I 的单调栈解法。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        
        // f[i]：下标 i 右边最近的更小元素下标
        int f[n];
        for (int i = 0; i < n; i++) f[i] = n;
        // 用单调栈求
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && nums[stk.top()] > nums[i]) {
                f[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
        
        // 把下标按值分类，每次只考虑一种元素
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < n; i++) mp[nums[i]].push_back(i);
        int ans = 0;
        for (auto &p : mp) {
            auto &vec = p.second;
            // 除了 0 以外，每种元素至少一次操作
            if (p.first > 0) ans++;
            // 两元素之间有更小元素，无法在一次操作内处理，答案再加 1
            for (int i = 0; i + 1 < vec.size(); i++) if (f[vec[i]] < vec[i + 1]) ans++;
        }
        return ans;
    }
};

给你两个 非负 整数 num1 和 num2 。

每一步 操作 中，如果 num1 >= num2 ，你必须用 num1 减 num2 ；否则，你必须用 num2 减 num1 。

• 例如，num1 = 5 且 num2 = 4 ，应该用 num1 减 num2 ，因此，得到 num1 = 1 和 num2 = 4 。然而，如果 num1 = 4且 num2 = 5 ，一步操作后，得到 num1 = 4 和 num2 = 1 。

返回使 num1 = 0 或 num2 = 0 的 操作数 。

 

示例 1：

输入：num1 = 2, num2 = 3
输出：3
解释：
- 操作 1 ：num1 = 2 ，num2 = 3 。由于 num1 < num2 ，num2 减 num1 得到 num1 = 2 ，num2 = 3 - 2 = 1 。
- 操作 2 ：num1 = 2 ，num2 = 1 。由于 num1 > num2 ，num1 减 num2 。
- 操作 3 ：num1 = 1 ，num2 = 1 。由于 num1 == num2 ，num1 减 num2 。
此时 num1 = 0 ，num2 = 1 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 3 。

示例 2：

输入：num1 = 10, num2 = 10
输出：1
解释：
- 操作 1 ：num1 = 10 ，num2 = 10 。由于 num1 == num2 ，num1 减 num2 得到 num1 = 10 - 10 = 0 。
此时 num1 = 0 ，num2 = 10 。由于 num1 == 0 ，不需要再执行任何操作。
所以总操作数是 1 。

 

提示：

• 0 <= num1, num2 <= 105

方法一：辗转相除

思路与算法

我们可以按要求模拟两数比较后相减的操作，但在两数差距十分悬殊时，会有大量连续且相同的相减操作，因此我们可以对模拟的过程进行优化。

不妨假设 $\textit{num}_1 \ge \textit{num}_2$，则我们需要用 $\textit{num}_1$ 减 $\textit{num}_2$，直到 $\textit{num}_1 < \textit{num}_2$ 为止。当上述一系列操作结束之后，$\textit{num}_1$ 的新数值即为 $\textit{num}_1 \bmod \textit{num}_2$，在这期间进行了 $\lfloor \textit{num}_1 / \textit{num}_2 \rfloor$ 次相减操作，其中 $\lfloor\dots\rfloor$ 代表向下取整。

容易发现，题目中的过程即为求两个数最大公约数的「辗转相减」方法，而我们需要将它优化为时间复杂度更低的「辗转相除」法，同时利用前文的方法统计对应相减操作的次数。

具体而言，在模拟的过程中，我们用 $\textit{res}$ 来统计相减操作的次数。在每一步模拟开始前，我们需要保证 $\textit{num}_1 \ge \textit{num}_2$；在每一步中，两个数 $(\textit{num}_1, \textit{num}_2)$ 变为 $(\textit{num}_1 \bmod \textit{num}_2, \textit{num}_2)$，同时我们将 $\textit{res}$ 加上该步中相减操作的次数 $\lfloor \textit{num}_1 / \textit{num}_2 \rfloor$；最后，我们还需要交换 $\textit{num}_1$ 与 $\textit{num}_2$ 的数值，以保证下一步模拟的初始条件。当 $\textit{num}_1$ 或 $\textit{num}_2$ 中至少有一个数字为零时，循环结束，我们返回 $\textit{res}$ 作为答案。

细节

在第一步模拟（进入循环）之前，我们事实上不需要保证 $\textit{num}_1 \ge \textit{num}_2$，因为我们可以通过额外的一步模拟将 $(\textit{num}_1, \textit{num}_2)$ 变为 $(\textit{num}_2, \textit{num}_1)$，而这一步贡献的相减次数为 $0$。

代码

###C++

class Solution {
public:
    int countOperations(int num1, int num2) {
        int res = 0;   // 相减操作的总次数
        while (num1 && num2) {
            // 每一步辗转相除操作
            res += num1 / num2;
            num1 %= num2;
            swap(num1, num2);
        }
        return res;
    }
};

###Python

class Solution:
    def countOperations(self, num1: int, num2: int) -> int:
        res = 0   # 相减操作的总次数
        while num1 and num2:
            # 每一步辗转相除操作
            res += num1 // num2
            num1 %= num2
            num1, num2 = num2, num1
        return res

###Java

class Solution {
    public int countOperations(int num1, int num2) {
        int res = 0;   // 相减操作的总次数
        while (num1 != 0 && num2 != 0) {
            // 每一步辗转相除操作
            res += num1 / num2;
            num1 %= num2;
            // 交换两个数
            int temp = num1;
            num1 = num2;
            num2 = temp;
        }
        return res;
    }
}

###C#

public class Solution {
    public int CountOperations(int num1, int num2) {
        int res = 0;   // 相减操作的总次数
        while (num1 != 0 && num2 != 0) {
            // 每一步辗转相除操作
            res += num1 / num2;
            num1 %= num2;
            // 交换两个数
            (num1, num2) = (num2, num1);
        }
        return res;
    }
}

###Go

func countOperations(num1 int, num2 int) int {
    res := 0   // 相减操作的总次数
    for num1 != 0 && num2 != 0 {
        // 每一步辗转相除操作
        res += num1 / num2
        num1 %= num2
        // 交换两个数
        num1, num2 = num2, num1
    }
    return res
}

###C

int countOperations(int num1, int num2) {
    int res = 0;   // 相减操作的总次数
    while (num1 && num2) {
        // 每一步辗转相除操作
        res += num1 / num2;
        num1 %= num2;
        // 交换两个数
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }
    return res;
}

###JavaScript

var countOperations = function(num1, num2) {
    let res = 0;   // 相减操作的总次数
    while (num1 && num2) {
        // 每一步辗转相除操作
        res += Math.floor(num1 / num2);
        num1 %= num2;
        // 交换两个数
        [num1, num2] = [num2, num1];
    }
    return res;
};

###TypeScript

function countOperations(num1: number, num2: number): number {
    let res = 0;   // 相减操作的总次数
    while (num1 && num2) {
        // 每一步辗转相除操作
        res += Math.floor(num1 / num2);
        num1 %= num2;
        // 交换两个数
        [num1, num2] = [num2, num1];
    }
    return res;
};

###Rust

impl Solution {
    pub fn count_operations(mut num1: i32, mut num2: i32) -> i32 {
        let mut res = 0;   // 相减操作的总次数
        while num1 != 0 && num2 != 0 {
            // 每一步辗转相除操作
            res += num1 / num2;
            num1 %= num2;
            // 交换两个数
            std::mem::swap(&mut num1, &mut num2);
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(\log \max(\textit{num}_1, \textit{num}_2))$。即为模拟辗转相除并统计操作次数的时间复杂度。

• 空间复杂度：$O(1)$。

下文把 $\textit{num}_1$ 和 $\textit{num}_2$ 分别记作 $x$ 和 $y$。

根据题意，如果 $x\ge y$，那么 $x$ 要不断减去 $y$，直到小于 $y$。这和商的定义是一样的，所以把 $x$ 减少到小于 $y$ 的操作数为 $\left\lfloor\dfrac{x}{y}\right\rfloor$。

$x<y$ 后，$x$ 变成 $x\bmod y$。

我们可以交换 $x$ 和 $y$，重复上述过程，这样无需实现 $x<y$ 时把 $y$ 变小的逻辑。

循环直到 $y=0$ 为止。

累加所有操作数，即为答案。

class Solution:
    def countOperations(self, x: int, y: int) -> int:
        ans = 0
        while y > 0:
            ans += x // y  # x 变成 x%y
            x, y = y, x % y
        return ans

class Solution {
    public int countOperations(int x, int y) {
        int ans = 0;
        while (y > 0) {
            ans += x / y;
            int r = x % y; // x 变成 r
            x = y; // 交换 x 和 y
            y = r;
        }
        return ans;
    }
}

class Solution {
public:
    int countOperations(int x, int y) {
        int ans = 0;
        while (y > 0) {
            ans += x / y;
            x %= y;
            swap(x, y);
        }
        return ans;
    }
};

int countOperations(int x, int y) {
    int ans = 0;
    while (y > 0) {
        ans += x / y;
        int r = x % y; // x 变成 r
        x = y; // 交换 x 和 y
        y = r;
    }
    return ans;
}

func countOperations(x, y int) (ans int) {
for y > 0 {
ans += x / y // x 变成 x%y
x, y = y, x%y
}
return
}

var countOperations = function(x, y) {
    let ans = 0;
    while (y > 0) {
        ans += Math.floor(x / y); // x 变成 x%y
        [x, y] = [y, x % y];
    }
    return ans;
};

impl Solution {
    pub fn count_operations(mut x: i32, mut y: i32) -> i32 {
        let mut ans = 0;
        while y > 0 {
            ans += x / y; // x 变成 x%y
            (x, y) = (y, x % y);
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(\log\max(x,y))$。当 $x$ 和 $y$ 为斐波那契数列中的相邻两项时，达到最坏情况。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

 

示例 1：

输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。

示例 2：

输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。

 

提示：

• 0 <= n <= 109

九连环，玩具也，以铜制之。欲使九环同贯于柱上，则先上第一环，再上第二环，而下其第一环，更上第三环，而下其第一二环，再上第四环，如是更迭上下，凡八十一次，而九环毕上矣。解之之法，先下其第一环，次下其第三环，更上第一环，而并下其第一二环，又下其第三环，如是更迭上下，凡八十一次，而九环毕下矣。

——《清稗类钞》

下文的 $n$ 均为二进制。

题意解读：第二种操作，翻转的是 $n$ 最低的 $1$ 左侧相邻的比特位。例如 $10010$ 操作后是 $10110$。注意操作是可逆的，$10110$ 执行第二种操作得到 $10010$。

逆向思维，从 $0$ 开始操作，我们依次得到的数字是什么？

由于连续两次相同操作后数字不变，如果要最小化操作次数，不能连续执行相同的操作，所以只能第一种操作和第二种操作交替执行。这意味着最优操作方案是唯一的，如下：

$$
0\to 1\to 11\to 10\to 110\to 111\to 101 \to 100 \to 1100\to \cdots
$$

从特殊到一般，考察从 $0$ 到 $2^k$ 的操作次数：

• 从 $0$ 到 $10$ 需要操作 $3$ 次。
• 从 $0$ 到 $100$ 需要操作 $7$ 次。
• 从 $0$ 到 $1000$ 需要操作多少次？

仔细考察从 $0$ 到 $100$ 的过程，其中后半段从 $110$ 到 $100$ 的过程是 $110\to 111\to 101 \to 100$，只看低 $2$ 位是 $10\to 11\to 01 \to 00$，倒过来看是 $00\to 01\to 11\to 10$，这和 $0$ 到 $10$ 的过程是完全一样的！

定义 $f(n)$ 表示把 $0$ 变成 $n$ 的最小操作次数，这也等于把 $n$ 变成 $0$ 最小操作次数。那么有

$$
0 \xrightarrow{操作\ f(10)\ 次} 10 \xrightarrow{操作\ 1\ 次} 110 \xrightarrow{操作\ f(10)\ 次} 100
$$

同理可得

$$
0 \xrightarrow{操作\ f(100)\ 次} 100 \xrightarrow{操作\ 1\ 次} 1100 \xrightarrow{操作\ f(100)\ 次} 1000
$$

所以从 $0$ 到 $1000$ 需要操作 $f(100) + 1 + f(100) = 7+1+7=15$ 次。

一般地，我们有

$$
f(2^k) = 2f(2^{k-1}) + 1
$$

两边同时加一，得

$$
f(2^k) + 1 = 2(f(2^{k-1}) + 1)
$$

所以 $f(2^k) + 1$ 是个等比数列，公比为 $2$，初始值为 $f(1)+1 = 2$，得

$$
f(2^k) + 1 = 2^{k+1}
$$

即

$$
f(2^k) = 2^{k+1} - 1
$$

注：另一种理解角度是，从 $0$ 到 $2^k$ 的过程中，恰好访问了 $[0,2^{k+1}-1]$ 中的每个整数各一次，所以需要操作 $2^{k+1}-1$ 次。

我们解决了 $n$ 是 $2$ 的幂的情况。下面考虑一般情况。

再来看这个过程

$$
0\to 1\to 11\to 10\to 110\to 111\to 101 \to 100
$$

其中从 $0$ 到 $111$ 需要操作多少次？

• 先计算从 $0$ 到 $100$ 的操作次数 $f(100)$。
• 然后减去从 $111$ 到 $100$ 的操作次数。这等于从 $11$ 到 $00$ 的操作次数，即 $f(11)$。

所以 $f(111) = f(100) - f(11)$。

一般地，设 $n$ 的二进制长度为 $k$，我们有

$$
\begin{aligned}
f(n) &= f(2^{k-1}) - f(n - 2^{k-1}) \
&= 2^k - 1 - f(n - 2^{k-1}) \
\end{aligned}
$$

其中 $n - 2^{k-1}$ 表示 $n$ 去掉最高的 $1$ 后的值。

递归边界：$f(0) = 0$。

注：九连环需要 $f(2^9-1) = 341$ 次操作。开头那段文言由于把多次操作算作一次，给出的操作次数比实际的少。

写法一：自顶向下

###py

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0
        k = n.bit_length()
        return (1 << k) - 1 - self.minimumOneBitOperations(n - (1 << (k - 1)))

###java

class Solution {
    public int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }
        int k = 32 - Integer.numberOfLeadingZeros(n);
        return (1 << k) - 1 - minimumOneBitOperations(n - (1 << (k - 1)));
    }
}

###java

class Solution {
    public int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }
        int hb = Integer.highestOneBit(n);
        return (hb << 1) - 1 - minimumOneBitOperations(n - hb);
    }
}

###cpp

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }
        int k = bit_width((uint32_t) n);
        return (1 << k) - 1 - minimumOneBitOperations(n - (1 << (k - 1)));
    }
};

###c

int minimumOneBitOperations(int n) {
    if (n == 0) {
        return 0;
    }
    int k = 32 - __builtin_clz(n);
    return (1 << k) - 1 - minimumOneBitOperations(n - (1 << (k - 1)));
}

###go

func minimumOneBitOperations(n int) int {
if n == 0 {
return 0
}
k := bits.Len(uint(n))
return 1<<k - 1 - minimumOneBitOperations(n-1<<(k-1))
}

###js

var minimumOneBitOperations = function(n) {
    if (n === 0) {
        return 0;
    }
    let k = 32 - Math.clz32(n);
    return (1 << k) - 1 - minimumOneBitOperations(n - (1 << (k - 1)));
};

###rust

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        if n == 0 {
            return 0;
        }
        let k = 32 - n.leading_zeros();
        (1 << k) - 1 - Self::minimum_one_bit_operations(n - (1 << (k - 1)))
    }
}

写法二：自底向上

递归是从高到低遍历 $n$ 的值为 $1$ 的比特位。

也可以从低到高遍历这些 $1$。

初始化答案 $\textit{ans}= 0$，即递归边界。

计算 $n$ 的最低位的 $1$，即 $\text{lowbit}$，原理见 从集合论到位运算，常见位运算技巧分类总结！

这里 $\text{lowbit}$ 相当于上面的 $2^{k-1}$。

然后更新 $\textit{ans}$ 为 $\text{lowbit}\cdot 2 - 1 - \textit{ans}$，相当于去掉递归的「递」，只在「归」的过程中计算答案。

###py

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n > 0:
            lb = n & -n  # n 的最低 1
            ans = (lb << 1) - 1 - ans
            n ^= lb  # 去掉 n 的最低 1
        return ans

###java

class Solution {
    public int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n > 0) {
            int lb = n & -n; // n 的最低 1
            ans = (lb << 1) - 1 - ans;
            n ^= lb; // 去掉 n 的最低 1
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n > 0) {
            int lb = n & -n; // n 的最低 1
            ans = (lb << 1) - 1 - ans;
            n ^= lb; // 去掉 n 的最低 1
        }
        return ans;
    }
};

###c

int minimumOneBitOperations(int n) {
    int ans = 0;
    while (n > 0) {
        int lb = n & -n; // n 的最低 1
        ans = (lb << 1) - 1 - ans;
        n ^= lb; // 去掉 n 的最低 1
    }
    return ans;
}

###go

func minimumOneBitOperations(n int) (ans int) {
for n > 0 {
lb := n & -n // n 的最低 1
ans = lb<<1 - 1 - ans
n ^= lb // 去掉 n 的最低 1
}
return
}

###js

var minimumOneBitOperations = function(n) {
    let ans = 0;
    while (n > 0) {
        const lb = n & -n; // n 的最低 1
        ans = (lb << 1) - 1 - ans;
        n ^= lb; // 去掉 n 的最低 1
    }
    return ans;
};

###rust

impl Solution {
    pub fn minimum_one_bit_operations(mut n: i32) -> i32 {
        let mut ans = 0;
        while n > 0 {
            let lb = n & -n; // n 的最低 1
            ans = (lb << 1) - 1 - ans;
            n ^= lb; // 去掉 n 的最低 1
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$。循环次数为 $n$ 的二进制中的 $1$ 的个数。特别地，如果 $n$ 是 $2$ 的幂，这个做法只需循环一次。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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

照例先上代码：

# 从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。直到最低位。
# 依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if not n:return 0
        head = 1<<int(math.log2(n))
        return head + self.minimumOneBitOperations((n^head)^(head>>1))

这是周赛上用来凑数的，用位运算优化一下是这样：

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if not n:return 0
        return n^self.minimumOneBitOperations(n>>1)

参考资料：

英文维基：

https://en.wikipedia.org/wiki/Gray_code

百度百科：

https://baike.baidu.com/item/%E6%A0%BC%E9%9B%B7%E7%A0%81/6510858#3

格雷码简介：

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）.

另外,格雷码的最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。

运算规则：

枚举（与题解有关）：

以二进制为0值的格雷码为第零项，

• 第一项改变最右边的位元，
• 第二项改变右起第一个为1的位元的左边位元，
  第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。
  

def gray_iter(gray):
    while(True):
        yield gray
        gray^=1
        yield gray
        gray^=(gray&-gray)<<1

编码：

• 对n位二进制的码字，从右到左，以0到n-1编号
• 如果二进制码字的第i位和i+1位相同，则对应的格雷码的第i位为0，否则为1（当i+1=n时，二进制码字的第n位被认为是0，即第n-1位不变）
  

def gray_encode(bytenum):
    return bytenum^(bytenum>>1)

解码（与题解有关）：

• 从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。直到最低位。
• 依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
  

def gray_decode(gray):
        if not gray:return 0
        head = 1<<int(math.log2(gray))
        return head + gray_decode((gray^head)^(head>>1))

题解

仔细看题目的表述：

• 翻转 n 的最右侧位（第 0 位）。
• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的第 i 位。

本质上对应的就是格雷码的枚举规则。

本题的求解目标等于是“一个格雷码需要向零的方向枚举多少次才会变成0”，即“格雷码->二进制码”。
于是乎，只需要将上述解码规则直译成代码就好了。

# 从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。直到最低位。
# 依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if not n:return 0
        head = 1<<int(math.log2(n))
        return head + self.minimumOneBitOperations((n^head)^(head>>1))

优化

用位运算优化，时间复杂度在Int范围里是O(logN)：

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if not n:return 0
        return n^self.minimumOneBitOperations(n>>1)

位运算对于大数会退化，所以补充大数版本：

gray_to_byte8 = [0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 8, 9, 11, 10, 31, 30, 28, 29, 24, 25, 27, 26, 16, 17, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, 57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, 36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121, 123, 122, 112, 113, 115, 114, 119, 118, 116, 117, 96, 97, 99, 98, 103, 102, 100, 101, 111, 110, 108, 109, 104, 105, 107, 106, 64, 65, 67, 66, 71, 70, 68, 69, 79, 78, 76, 77, 72, 73, 75, 74, 95, 94, 92, 93, 88, 89, 91, 90, 80, 81, 83, 82, 87, 86, 84, 85, 255, 254, 252, 253, 248, 249, 251, 250, 240, 241, 243, 242, 247, 246, 244, 245, 224, 225, 227, 226, 231, 230, 228, 229, 239, 238, 236, 237, 232, 233, 235, 234, 192, 193, 195, 194, 199, 198, 196, 197, 207, 206, 204, 205, 200, 201, 203, 202, 223, 222, 220, 221, 216, 217, 219, 218, 208, 209, 211, 210, 215, 214, 212, 213, 128, 129, 131, 130, 135, 134, 132, 133, 143, 142, 140, 141, 136, 137, 139, 138, 159, 158, 156, 157, 152, 153, 155, 154, 144, 145, 147, 146, 151, 150, 148, 149, 191, 190, 188, 189, 184, 185, 187, 186, 176, 177, 179, 178, 183, 182, 180, 181, 160, 161, 163, 162, 167, 166, 164, 165, 175, 174, 172,
 173, 168, 169, 171, 170]
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if not n:return 0
        head = 0
        ls = []
        for i in int(n).to_bytes(int((math.log2(n))//8+1),"big"):
            ls.append(gray_to_byte8[i^(head<<7)])
            head = ls[-1]&1
        return int.from_bytes(ls,'big')

↙ 求赞qwq

本场周赛题解 | 我的LeetCode比赛题解

方法一：递归

要注意到的是，因为必须首先将高位的$1$翻转为$0$，所以本题其实只存在一种合法的操作顺序，我们只要按照这一顺序进行操作即可。

手算几个数，可以发现$F(2^n)=2^{n+1}-1$，因此我们可以将其作为一个捷径。

我们需要考虑两种情况：

1. 把当前数变为$0$。我们首先要找到最高位的$1$，找到之后，我们需要的翻转次数，就是将之后的位置变为$10\dots0$，再将最高位翻转，然后将剩下的数变为$0$。因为剩下的数必然是$2$的幂次，就可以使用上面的捷径。
2. 把当前数变为$10\dots 0$。如果$1$对应的位置已经是$1$，我们只需要将后面的数变为$0$；否则，我们需要先把后面变为$10\dots0$，将最高位翻转，再将剩下的数变为$0$。

实现这两个函数，递归计算即可。

###cpp

class Solution {
    int f(int n) {
        if (n <= 1)
            return n;
        int t = 32 - __builtin_clz(n) - 1;
        return (1 << t) + g(n ^ (1 << t), t - 1);
    }
    
    int g(int n, int t) {
        if (t == 0)
            return 1 - n;
        if (n & (1 << t))
            return f(n ^ (1 << t));
        return (1 << t) + g(n, t - 1);
    }
public:
    int minimumOneBitOperations(int n) {
        return f(n);
    }
};

方法二：格雷码

如果进一步观察，可以发现，题目中给出的操作，实际上就是从Gray(n)变换为Gray(n-1)的操作。所以我们可以直接套用求逆格雷码的方法来进行求解。

时间复杂度$O(\log N)$。

###cpp

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n) {
            ans ^= n;
            n >>= 1;    
        } 
        return ans;
    }
};

给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

• |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。

这 k 座供电站可以建在多个城市。

 

示例 1：

输入：stations = [1,2,4,5,0], r = 1, k = 2
输出：5
解释：
最优方案之一是把 2 座供电站都建在城市 1 。
每座城市的供电站数目分别为 [1,4,4,5,0] 。
- 城市 0 的供电站数目为 1 + 4 = 5 。
- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。
- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。
- 城市 3 的供电站数目为 5 + 4 = 9 。
- 城市 4 的供电站数目为 5 + 0 = 5 。
供电站数目最少是 5 。
无法得到更优解，所以我们返回 5 。

示例 2：

输入：stations = [4,4,4,4], r = 0, k = 3
输出：4
解释：
无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。

 

提示：

• n == stations.length
• 1 <= n <= 105
• 0 <= stations[i] <= 105
• 0 <= r <= n - 1
• 0 <= k <= 109

2528. 最大化城市的最小供电站数目

[TOC]

思路

  由于我们要求的是某个值的最大值，所以我们可以采用 <二分查找> 的方式来“猜”结果。

  对于每次猜测，创建函数 $f(c)$ ，返回该数是否合法。

  我们可以采用<差分数组>的形式记录差值，差分数组相关内容参考本文补充部分。从左到右遍历，设本次猜的数为 $c$ ，遇到位置为 $i$ 处的电站小于 $c$ ，则在 $\min(i + r, n - 1)$ 处<临时>添加电站，也就是位于 $[i, \min(i + 2 * r, n - 1)]$ 的城市都增加了临时电站的覆盖。若在本次猜测中，剩余可加的电站不足，则返回 $False$，若最后剩余电站数大于等于0，则返回 $True$。

代码

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        # 差分数组
        diff = defaultdict(int)
        n = len(stations)
        for i, val in enumerate(stations):
            left = max(0, i - r)
            right = min(n, i + r + 1)
            diff[left] += val
            diff[right] -= val

        # 判断猜的数字是否合法
        def f(c):
            # 临时电站的差分数组
            td = defaultdict(int)
            # 本次猜测剩余可加电站数
            tk = k
            # 当前位置覆盖的电站数
            cnt = 0
            for i in range(n):
                # i 处的电站数
                cnt += diff[i] + td[i]
                if cnt < c:
                    # 将该位置电站数补充到 c
                    tk -= c - cnt
                    if tk < 0:
                        # 剩余可加电站不足
                        return False
                    # 补充的电站放在 min(n - 1, i * 2 * r) 处
                    td[min(n, i + 2 * r + 1)] -= c - cnt
                    # 更新该位置的电站数
                    cnt = c
            return True

        #预估上下界
        a, b = min(stations), sum(stations) + k
        # 维护左边界合法
        while a + 1 < b:
            c = a + (b - a) // 2
            if f(c):
                a = c
            else:
                b = c - 1
        if f(b):
            return b
        return a

复杂度分析

• 时间复杂度：$O(n \log D)$。每次猜测的时间复杂度为 $O(n)$，需要进行$D = sum(stations) + k - min(stations)$次猜测，总复杂度为 $O(n \log D)$.
• 空间复杂度：$O(n)$.

补充：差分数组

  给定边界 $S \geq 0$，数组 $arr$，其中 $arr[i] = [a_{i}, b_{i}],\ (0 \leq a_{i} \leq b_{i} \leq S)$，表示在 $[a_{i}, b_{i}]$ 内每个整数位置都放一个小球，返回每个坐标下的小球数量列表。

  若采用暴力方法，时间复杂度为 $O(nS)\ (n = len(arr))$。

def function(arr: list[list[int]], S: int) -> list[int]:
    ans = [0] * (S + 1)
    for a, b in arr:
        for i in range(a, b + 1):
            ans[i] += 1
    return ans

  实际上，我们只要记录每个坐标和前一个坐标的差值，即可在 $O(S)$ 的时间内计算出每个位置最后的小球数。

  创建数组 $diff$，其中 $diff[i]$ 表示 $i$ 位置和 $i - 1$位置的差值，则 $ans[i] = ans[i - 1] + diff[i]$，其中$ans[0] = 0 + diff[0]$.

  那么如何建立差分数组 $diff$ 呢？对于 $arr[i] = [a_{i}, b_{i}]$，表面含义是在 $[a_{i}, b_{i}]$ 内每个整数位置都放一个小球，我们可以从另一个角度理解：

• 位置 $a_{i}$ 相对于位置 $a_{i} - 1$来说，多增加了一个球，所以差值 $diff[a_{i}] += 1$
• 位置 $b_{i} + 1$ 相对于位置 $b_{i}$来说，少增加了一个球，所以 $diff[b_{i} + 1] -= 1$
• 对于 $[a_{i} + 1, b_{i}]$ 内的位置来说，和前一个位置一样，都增加了一个小球，所以差值没变，不需要修改差分数组 $diff$

  调整差分数组的时间复杂度为$O(n)\ (n = len(arr))$，根据差分数组求每个位置小球数的时间复杂度为 $O(S)$，则总时间复杂度为 $O(n) + O(S) = O(\min(n, S))$.

def function(arr: list[list[int]], S: int) -> list[int]:
    # 建立差分数组
    diff = defaultdict(int)
    # 调整差分数组
    for a, b in arr:
        diff[a] += 1
        diff[b] -= 1
    # 根据差分数组求各个位置的小球数
    ans = [0] * (S + 1)
    ans[i] = diff[0]
    for i in range(1, S + 1):
        ans[i] = ans[i - 1] + diff[i]
    return ans

END

  码字不易，点个赞再走呗！

转化

如果存在一种方案，可以让所有城市的电量都 $\ge \textit{low}$，那么也可以 $\ge \textit{low}-1$ 或者更小的值（要求更宽松）。

如果不存在让所有城市的电量都 $\ge \textit{low}$ 的方案，那么也不存在 $\ge \textit{low}+1$ 或者更大的方案（要求更苛刻）。

据此，可以二分猜答案。关于二分算法的原理，请看 二分查找 红蓝染色法【基础算法精讲 04】。

现在问题转化成一个判定性问题：

• 给定 $\textit{low}$，是否存在建造 $k$ 座额外电站的方案，使得所有城市的电量都 $\ge \textit{low}$？

如果存在，说明答案 $\ge \textit{low}$，否则答案 $<\textit{low}$。

思路

由于已经建造的电站是可以发电的，我们需要在二分之前，用 $\textit{stations}$ 计算每个城市的初始电量 $\textit{power}$。这可以用前缀和或者滑动窗口做，具体后面解释。

然后从左到右遍历 $\textit{power}$，挨个处理。如果 $\textit{power}[i] < \textit{low}$，就需要建造电站，额外提供 $\textit{low} - \textit{power}[i]$ 的电力。

在哪建造电站最好呢？

由于我们是从左到右遍历的，在 $i$ 左侧的城市已经处理好了，所以建造的电站越靠右越好，尽可能多地覆盖没遍历到的城市。具体地，$i$ 应当恰好在电站供电范围的边缘上，也就是把电站建在 $i+r$ 的位置，使得电站覆盖范围为 $[i,i+2r]$。

我们要建 $m = \textit{low} - \textit{power}[i]$ 个供电站，也就是把下标在 $[i,i+2r]$ 中的城市的电量都增加 $m$。

这里有一个「区间增加 $m$」的需求，用差分数组实现，原理见 差分数组原理讲解。

我们要一边做差分更新，一边计算差分数组的前缀和，以得到当前城市的实际电量。

遍历的同时，累计额外建造的电站数量，如果超过 $k$，不满足要求，可以提前跳出循环。

细节

下面代码采用开区间二分，这仅仅是二分的一种写法，使用闭区间或者半闭半开区间都是可以的，喜欢哪种写法就用哪种。

• 开区间左端点初始值：$\min(\textit{power}) + \left\lfloor\dfrac{k}{n}\right\rfloor$。把 $k$ 均摊，即使 $r=0$，每个城市都能至少分到 $\left\lfloor\dfrac{k}{n}\right\rfloor$ 的额外电量，所以 $\textit{low} = \min(\textit{power}) + \left\lfloor\dfrac{k}{n}\right\rfloor$ 时一定满足要求。
• 开区间右端点初始值：$\min(\textit{power}) + k + 1$。即使把所有额外电站都建给电量最小的城市，也无法满足要求。

对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，更简单。推荐使用开区间写二分。

写法一：前缀和

能覆盖城市 $i$ 的电站下标范围是 $[i-r,i+r]$。注意下标不能越界，所以实际范围是 $[\max(i-r,0),\min(i+r,n-1)]$。

我们需要计算 $\textit{stations}$ 的这个范围（子数组）的和。

计算 $\textit{stations}$ 的 前缀和 数组后，可以 $\mathcal{O}(1)$ 计算 $\textit{stations}$ 的任意子数组的和。

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        # 前缀和
        s = list(accumulate(stations, initial=0))
        # 初始电量
        power = [s[min(i + r + 1, n)] - s[max(i - r, 0)] for i in range(n)]

        def check(low: int) -> bool:
            diff = [0] * n  # 差分数组
            sum_d = built = 0
            for i, p in enumerate(power):
                sum_d += diff[i]  # 累加差分值
                m = low - (p + sum_d)
                if m <= 0:
                    continue
                # 需要在 i+r 额外建造 m 个供电站
                built += m
                if built > k:  # 不满足要求
                    return False
                # 把区间 [i, i+2r] 增加 m
                sum_d += m  # 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                if (right := i + r * 2 + 1) < n:
                    diff[right] -= m
            return True

        # 开区间二分
        mn = min(power)
        left, right = mn + k // n, mn + k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        # 前缀和
        s = list(accumulate(stations, initial=0))
        # 初始电量
        power = [s[min(i + r + 1, n)] - s[max(i - r, 0)] for i in range(n)]

        def check(low: int) -> bool:
            low += 1  # 二分最小的不满足要求的 low（符合库函数），这样最终返回的就是最大的满足要求的 low
            diff = [0] * n  # 差分数组
            sum_d = built = 0
            for i, p in enumerate(power):
                sum_d += diff[i]  # 累加差分值
                m = low - (p + sum_d)
                if m <= 0:
                    continue
                # 需要在 i+r 额外建造 m 个供电站
                built += m
                if built > k:  # 不满足要求
                    return True
                # 把区间 [i, i+2r] 增加 m
                sum_d += m  # 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                if (right := i + r * 2 + 1) < n:
                    diff[right] -= m
            return False

        mn = min(power)
        left, right = mn + k // n, mn + k
        return bisect_left(range(right), True, lo=left, key=check)

class Solution {
    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;
        // 前缀和
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + stations[i];
        }

        // 初始电量
        long[] power = new long[n];
        long mn = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            power[i] = sum[Math.min(i + r + 1, n)] - sum[Math.max(i - r, 0)];
            mn = Math.min(mn, power[i]);
        }

        // 开区间二分
        long left = mn + k / n;
        long right = mn + k + 1;
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(mid, power, r, k)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long low, long[] power, int r, int k) {
        int n = power.length;
        long[] diff = new long[n + 1];
        long sumD = 0;
        long built = 0;
        for (int i = 0; i < n; i++) {
            sumD += diff[i]; // 累加差分值
            long m = low - (power[i] + sumD);
            if (m <= 0) {
                continue;
            }
            // 需要在 i+r 额外建造 m 个供电站
            built += m;
            if (built > k) { // 不满足要求
                return false;
            }
            // 把区间 [i, i+2r] 增加 m
            sumD += m; // 由于 diff[i] 后面不会再访问，我们直接加到 sumD 中
            diff[Math.min(i + r * 2 + 1, n)] -= m;
        }
        return true;
    }
}

class Solution {
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        // 前缀和
        vector<long long> sum(n + 1);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + stations[i];
        }

        // 初始电量
        vector<long long> power(n);
        long long mn = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            power[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)];
            mn = min(mn, power[i]);
        }

        auto check = [&](long long low) -> bool {
            vector<long long> diff(n + 1);
            long long sum_d = 0, built = 0;
            for (int i = 0; i < n; i++) {
                sum_d += diff[i]; // 累加差分值
                long long m = low - (power[i] + sum_d);
                if (m <= 0) {
                    continue;
                }
                // 需要在 i+r 额外建造 m 个供电站
                built += m;
                if (built > k) { // 不满足要求
                    return false;
                }
                // 把区间 [i, i+2r] 增加 m
                sum_d += m; // 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                diff[min(i + r * 2 + 1, n)] -= m;
            }
            return true;
        };

        // 开区间二分
        long long left = mn + k / n, right = mn + k + 1;
        while (left + 1 < right) {
            long long mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

func maxPower(stations []int, r int, k int) int64 {
n := len(stations)
// 前缀和
sum := make([]int, n+1)
for i, x := range stations {
sum[i+1] = sum[i] + x
}

// 初始电量
power := make([]int, n)
mn := math.MaxInt
for i := range power {
power[i] = sum[min(i+r+1, n)] - sum[max(i-r, 0)]
mn = min(mn, power[i])
}

// 二分答案
left := mn + k/n
right := mn + k
ans := left + sort.Search(right-left, func(low int) bool {
// 这里 +1 是为了二分最小的不满足要求的 low（符合库函数），这样最终返回的就是最大的满足要求的 low
low += left + 1
diff := make([]int, n+1) // 差分数组
sumD, built := 0, 0
for i, p := range power {
sumD += diff[i] // 累加差分值
m := low - (p + sumD)
if m <= 0 {
continue
}
// 需要在 i+r 额外建造 m 个供电站
built += m
if built > k { // 不满足要求
return true
}
// 把区间 [i, i+2r] 增加 m
sumD += m // 由于 diff[i] 后面不会再访问，我们直接加到 sumD 中
diff[min(i+r*2+1, n)] -= m
}
return false
})
return int64(ans)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log k)$，其中 $n$ 是 $\textit{stations}$ 的长度。二分 $\mathcal{O}(\log k)$ 次，每次 $\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$。

写法二：滑动窗口

用 滑动窗口 计算 $\textit{power}$。

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        # 滑动窗口
        s = sum(stations[:r])  # 先计算 [0, r-1] 的发电量，为第一个窗口做准备
        power = [0] * n
        for i in range(n):
            # 右边进
            if (right := i + r) < n:
                s += stations[right]
            # 左边出
            if (left := i - r - 1) >= 0:
                s -= stations[left]
            power[i] = s

        def check(low: int) -> bool:
            diff = [0] * n  # 差分数组
            sum_d = built = 0
            for i, p in enumerate(power):
                sum_d += diff[i]  # 累加差分值
                m = low - (p + sum_d)
                if m <= 0:
                    continue
                # 需要在 i+r 额外建造 m 个供电站
                built += m
                if built > k:  # 不满足要求
                    return False
                # 把区间 [i, i+2r] 增加 m
                sum_d += m  # 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                if (right := i + r * 2 + 1) < n:
                    diff[right] -= m
            return True

        # 开区间二分
        mn = min(power)
        left, right = mn + k // n, mn + k + 1
        while left + 1 < right:
            mid = (left + right) // 2
            if check(mid):
                left = mid
            else:
                right = mid
        return left

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        # 滑动窗口
        s = sum(stations[:r])  # 先计算 [0, r-1] 的发电量，为第一个窗口做准备
        power = [0] * n
        for i in range(n):
            # 右边进
            if (right := i + r) < n:
                s += stations[right]
            # 左边出
            if (left := i - r - 1) >= 0:
                s -= stations[left]
            power[i] = s

        def check(low: int) -> bool:
            low += 1  # 二分最小的不满足要求的 low（符合库函数），这样最终返回的就是最大的满足要求的 low
            diff = [0] * n  # 差分数组
            sum_d = built = 0
            for i, p in enumerate(power):
                sum_d += diff[i]  # 累加差分值
                m = low - (p + sum_d)
                if m <= 0:
                    continue
                # 需要在 i+r 额外建造 m 个供电站
                built += m
                if built > k:  # 不满足要求
                    return True
                # 把区间 [i, i+2r] 增加 m
                sum_d += m  # 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                if (right := i + r * 2 + 1) < n:
                    diff[right] -= m
            return False

        mn = min(power)
        left, right = mn + k // n, mn + k
        return bisect_left(range(right), True, lo=left, key=check)

class Solution {
    public long maxPower(int[] stations, int r, int k) {
        int n = stations.length;
        // 滑动窗口
        // 先计算 [0, r-1] 的发电量，为第一个窗口做准备
        long sum = 0;
        for (int i = 0; i < r; i++) {
            sum += stations[i];
        }
        long[] power = new long[n];
        long mn = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // 右边进
            if (i + r < n) {
                sum += stations[i + r];
            }
            // 左边出
            if (i - r - 1 >= 0) {
                sum -= stations[i - r - 1];
            }
            power[i] = sum;
            mn = Math.min(mn, sum);
        }

        // 开区间二分
        long left = mn + k / n;
        long right = mn + k + 1;
        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(mid, power, r, k)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check(long low, long[] power, int r, int k) {
        int n = power.length;
        long[] diff = new long[n + 1];
        long sumD = 0;
        long built = 0;
        for (int i = 0; i < n; i++) {
            sumD += diff[i]; // 累加差分值
            long m = low - (power[i] + sumD);
            if (m <= 0) {
                continue;
            }
            // 需要在 i+r 额外建造 m 个供电站
            built += m;
            if (built > k) { // 不满足要求
                return false;
            }
            // 把区间 [i, i+2r] 增加 m
            sumD += m; // 由于 diff[i] 后面不会再访问，我们直接加到 sumD 中
            diff[Math.min(i + r * 2 + 1, n)] -= m;
        }
        return true;
    }
}

class Solution {
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        // 滑动窗口
        // 先计算 [0, r-1] 的发电量，为第一个窗口做准备
        long long sum = reduce(stations.begin(), stations.begin() + r, 0LL);
        vector<long long> power(n);
        long long mn = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            // 右边进
            if (i + r < n) {
                sum += stations[i + r];
            }
            // 左边出
            if (i - r - 1 >= 0) {
                sum -= stations[i - r - 1];
            }
            power[i] = sum;
            mn = min(mn, sum);
        }

        auto check = [&](long long low) -> bool {
            vector<long long> diff(n + 1);
            long long sum_d = 0, built = 0;
            for (int i = 0; i < n; i++) {
                sum_d += diff[i]; // 累加差分值
                long long m = low - (power[i] + sum_d);
                if (m <= 0) {
                    continue;
                }
                // 需要在 i+r 额外建造 m 个供电站
                built += m;
                if (built > k) { // 不满足要求
                    return false;
                }
                // 把区间 [i, i+2r] 增加 m
                sum_d += m; // 由于 diff[i] 后面不会再访问，我们直接加到 sum_d 中
                diff[min(i + r * 2 + 1, n)] -= m;
            }
            return true;
        };

        // 开区间二分
        long long left = mn + k / n, right = mn + k + 1;
        while (left + 1 < right) {
            long long mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

func maxPower(stations []int, r int, k int) int64 {
n := len(stations)
// 滑动窗口
// 先计算 [0, r-1] 的发电量，为第一个窗口做准备
sum := 0
for _, x := range stations[:r] {
sum += x
}
power := make([]int, n)
mn := math.MaxInt
for i := range power {
// 右边进
if i+r < n {
sum += stations[i+r]
}
// 左边出
if i-r-1 >= 0 {
sum -= stations[i-r-1]
}
power[i] = sum
mn = min(mn, sum)
}

// 二分答案
left := mn + k/n
right := mn + k
ans := left + sort.Search(right-left, func(low int) bool {
// 这里 +1 是为了二分最小的不满足要求的 low（符合库函数），这样最终返回的就是最大的满足要求的 low
low += left + 1
diff := make([]int, n+1) // 差分数组
sumD, built := 0, 0
for i, p := range power {
sumD += diff[i] // 累加差分值
m := low - (p + sumD)
if m <= 0 {
continue
}
// 需要在 i+r 额外建造 m 个供电站
built += m
if built > k { // 不满足要求
return true
}
// 把区间 [i, i+2r] 增加 m
sumD += m // 由于 diff[i] 后面不会再访问，我们直接加到 sumD 中
diff[min(i+r*2+1, n)] -= m
}
return false
})
return int64(ans)
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n\log k)$，其中 $n$ 是 $\textit{stations}$ 的长度。二分 $\mathcal{O}(\log k)$ 次，每次 $\mathcal{O}(n)$。
• 空间复杂度：$\mathcal{O}(n)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

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