LeetCode_122_OnesAndZeroes

LeetCode

发布日期: 2022-06-21

更新日期: 2022-06-21

文章字数: 982

阅读时长: 4 分

阅读次数:

1. question: 一和零（中等）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/ones-and-zeroes

示例 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：

1
2
3

输入：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

2. answers

这道题最开始没有想出来，参考题解。因为不知道如何转换成01背包问题，按理说应该是将限制条件转换为背包容量，比如k个0，那么背包容量为k，定义数组dp[k]，表示在当前背包容量下，所能形成的最长子集。此时，对于当前元素，要么添加到子集中（回退到满足空间之后的状态，计算添加后的子集数量），要么不添加到子集中（采用上个元素形成的子集），只需要比较二者之后的子集数量即可。

但是这里限制了两个条件，不超过m个0，n个1。其实就是将背包做了两层限制，相当于限制了背包的长度和宽度，而不再限制重量。

我们动态规划的时候，只需要对两种限制分别遍历即可。p个0，q个1等等。因此递归公式和上面一样，仍然是是否添加本元素，注意回退后的空间，要满足01限制。最终的结果就是dp[m][n]。代码如下所示：

public class Solution_0122 {

    // 计算字符串中01数量
    public int[] get01Num(String strs) {

        int[] result = new int[2];

        for (int i = 0; i < strs.length(); i++) {
            if(strs.charAt(i) == '0') result[0]++;
            else result[1]++;
        }

        return result;
    }

    public int findMaxForm(String[] strs, int m, int n) {

        int[][] dp = new int[m + 1][n + 1];

        // 初始化，即加入第一个元素时，在对应的01限制下，所形成的最长子集数量。
        // 计算得到字符串中01的数量。
        int[] result = get01Num(strs[0]);
        for (int i = 0; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                if(result[0] <= i && result[1] <= j) dp[i][j] = 1;
            }
        }

        // 动态规划，遍历后续dp数组中的每个元素
        // 和一维动态数组一样，因为每个元素所使用到的上面状态的左上角元素，即逆序遍历，才不会导致覆盖前面状态的值
        for (int i = 1; i < strs.length; i++) {

            int[] temp = get01Num(strs[i]);

            for (int j = m; j >= temp[0]; j--) {

                for (int k = n; k >= temp[1]; k--) {

                    // 注意，这里有两种情况，即是否添加本元素
                    dp[j][k] = Math.max(dp[j][k], dp[j-temp[0]][k-temp[1]] + 1);
                }
            }

        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println();

        String[] strs = {"10", "0001", "111001", "1", "0"};
        int m = 5, n = 3;

//        String[] strs = {"10", "0", "1"};
//        int m = 1, n = 1;

        Solution_0122 s = new Solution_0122();

        System.out.println(s.findMaxForm(strs, m, n));
    }
}