LeetCode题练习与总结：一和零--474

标签：遍历数组 -- strs length 474 字符串 LeetCode dp

一、题目描述

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

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

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

示例 2：

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

提示：

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

二、解题思路

这个问题是一个典型的背包问题，更具体地说，是一个二维背包问题。在这个问题中，每个字符串可以被视为一个物品，而每个物品都有两个维度的重量：包含的’0’的数量和包含的’1’的数量。我们的目标是在不超过给定的m个’0’和n个’1’的限制下，尽可能多地选择字符串。

解题思路如下：

遍历每个字符串，计算每个字符串中’0’和’1’的数量。
使用动态规划的方法来解决问题。定义一个三维数组dp[i][j][k]，表示在前i个字符串中，使用最多j个’0’和k个’1’时可以组成的最大子集的大小。
对于每个字符串，我们需要决定是否将其包含在子集中。如果包含，我们需要更新dp数组以反映这一选择。
最后，dp[strs.length][m][n]将包含我们需要的答案。

三、具体代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j][k] 表示前i个字符串中，最多使用j个0和k个1时的最大子集大小
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        
        // 遍历每个字符串
        for (int i = 1; i <= strs.length; i++) {
            // 计算当前字符串中0和1的数量
            int zeros = 0, ones = 0;
            for (char c : strs[i - 1].toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            
            // 遍历所有的0和1的容量
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // 如果当前容量可以容纳当前字符串
                    if (j >= zeros && k >= ones) {
                        // 选择当前字符串和不选择当前字符串的最大值
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    } else {
                        // 如果不能选择当前字符串，继承上一个状态
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        
        // 返回最大子集的大小
        return dp[strs.length][m][n];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

遍历字符串数组：代码中有一个三层嵌套循环，分别对应字符串数组strs的遍历、m的遍历和n的遍历。
- 字符串数组strs的长度为strs.length，所以外层循环的次数为strs.length。
- 第二层循环变量j从0遍历到m，所以循环次数为m + 1。
- 第三层循环变量k从0遍历到n，所以循环次数为n + 1。
计算字符串中0和1的数量：对于每个字符串，需要遍历其所有字符来计算0和1的数量。最坏情况下，每个字符串的长度为100，所以对于每个字符串，这个步骤的时间复杂度为O(100)。

综合以上两点，代码的时间复杂度为： O(strs.length * m * n) * O(字符串最大长度) = O(strs.length * m * n * 100)

2. 空间复杂度

动态规划数组dp：代码中定义了一个三维数组dp，其维度分别为strs.length + 1、m + 1和n + 1。
- 因此，dp数组总共包含(strs.length + 1) * (m + 1) * (n + 1)个元素。
临时变量：代码中使用了几个临时变量来存储每个字符串中0和1的数量，这些变量的空间复杂度为O(1)。

综合以上两点，代码的空间复杂度为： O(strs.length * m * n)

五、总结知识点

动态规划（Dynamic Programming）：动态规划是一种用于解决优化问题的算法技术，它通过将问题分解为更小的子问题并存储这些子问题的解（即状态）来避免重复计算。
三维数组：代码中使用了一个三维数组dp来存储子问题的解，其中dp[i][j][k]表示在前i个字符串中，最多使用j个0和k个1时的最大子集大小。
嵌套循环：代码中使用了三层嵌套循环来遍历字符串数组以及可能的0和1的容量。
字符串处理：通过toCharArray()方法将字符串转换为字符数组，然后遍历这个数组来计算字符串中0和1的数量。
条件判断：使用if语句来判断当前容量是否足够容纳当前字符串中的0和1。
状态转移方程：代码中的dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1);是动态规划中的状态转移方程，它描述了如何从前一个状态推导出当前状态。
递推关系：递推关系是动态规划的核心，它定义了如何根据子问题的解来构建更大问题的解。
数学运算：使用Math.max()函数来比较并选择最大值。
问题建模：将问题建模为背包问题，其中每个字符串是一个物品，0和1的数量分别是物品的两个维度重量。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：遍历,数组,--,strs,length,474,字符串,LeetCode,dp
From： https://blog.csdn.net/weixin_62860386/article/details/144510548