leetcode-474-一和零

[博客链接]

一个菜🐔的学习之路

[题目描述]

  1. 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
  4.  请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 
  6.  如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
  11.  示例 1： 
  14. 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
  15. 输出：4
  16. 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
  17. 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
  18. n 的值 3 。
  21.  示例 2： 
  24. 输入：strs = ["10", "0", "1"], m = 1, n = 1
  25. 输出：2
  26. 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
  31.  提示： 
  34.  1 <= strs.length <= 600 
  35.  1 <= strs[i].length <= 100 
  36.  strs[i] 仅由 '0' 和 '1' 组成 
  37.  1 <= m, n <= 100 
  39.  Related Topics 动态规划 
  40.  👍 505 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：动态规划(三维)

  • 难点在于如何将此题转化为背包问题，从而使用动态规划求解
  • 本题概念可转化为，每个数组的价值为1 也就是每个背包的价值为1，成本包括两部分组成，一部分为1的数量，一部分为0的数量
  • 也就是说可以定义三维数组dp[i][j][k]使用前i个数组元素，在满足不超过j个1和k个0的情况下价值最大化（最大子集）
  • 由此可推出dp方程
    dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-cnt0(i)][k-cnt1(i) + 1])
  1. public int findMaxForm(String[] strs, int m, int n) {
  2.             //dp数组
  3.             int[][][] dp = new int[strs.length][m + 1][n + 1];
  4.             //成本数组cnt
  5.             int[][] cnt = new int[strs.length][2];
  6.             for (int i = 0; i < strs.length; i++) {
  7.                 int c0 = 0, c1 = 0;
  9.                 for (char c : strs[i].toCharArray()
  10.                 ) {
  11.                     if (c == '1') {
  12.                         c1 += 1;
  13.                     } else {
  14.                         c0 += 1;
  15.                     }
  16.                 }
  17.                 cnt[i][0] = c0;
  18.                 cnt[i][1] = c1;
  19.             }
  21.             //dp边界情况,只处理其中一件
  22.             for (int i = 0; i <= m; i++) {
  23.                 for (int j = 0; j <= n; j++) {
  24.                     dp[0][i][j] = (cnt[0][0] <= i && cnt[0][1] <= j) ? 1 : 0;
  25.                 }
  26.             }
  27.             for (int i = 1; i < strs.length; i++) {
  28.                 int[] temp = cnt[i];
  29.                 for (int j = 0; j <= m; j++) {
  30.                     for (int k = 0; k <= n; k++) {
  31.                         dp[i][j][k] = dp[i - 1][j][k];
  32.                         int b = (j >= temp[0] && k >= temp[1]) ? dp[i - 1][j - temp[0]][k - temp[1]] + 1 : 0;
  33.                         dp[i][j][k] = Math.max(dp[i][j][k], b);
  34.                     }
  35.                 }
  36.             }
  38.             return dp[strs.length - 1][m][n];
  40.         }

时间复杂度O(nml)

思路二：动态规划(二维)

  • 将上述dp方程归纳发现，当前状态之和前置状态有关，所以可以使用滚动数组的方式完成
  1. public int findMaxForm(String[] strs, int m, int n) {
  2.             //dp数组
  3.             int[][][] dp = new int[2][m + 1][n + 1];
  4.             //成本数组cnt
  5.             int[][] cnt = new int[strs.length][2];
  6.             for (int i = 0; i < strs.length; i++) {
  7.                 int c0 = 0, c1 = 0;
  9.                 for (char c : strs[i].toCharArray()
  10.                 ) {
  11.                     if (c == '1') {
  12.                         c1 += 1;
  13.                     } else {
  14.                         c0 += 1;
  15.                     }
  16.                 }
  17.                 cnt[i][0] = c0;
  18.                 cnt[i][1] = c1;
  19.             }
  21.             //dp边界情况,只处理其中一件
  22.             //通过与1去并运算，保证滚动性
  23.             for (int i = 0; i <= m; i++) {
  24.                 for (int j = 0; j <= n; j++) {
  25.                     dp[0][i][j] = (cnt[0][0] <= i && cnt[0][1] <= j) ? 1 : 0;
  26.                 }
  27.             }
  28.             for (int i = 1; i < strs.length; i++) {
  29.                 int[] temp = cnt[i];
  30.                 for (int j = 0; j <= m; j++) {
  31.                     for (int k = 0; k <= n; k++) {
  32.                         dp[i & 1][j][k] = dp[(i - 1) & 1][j][k];
  33.                         int b = (j >= temp[0] && k >= temp[1]) ? dp[(i - 1) & 1][j - temp[0]][k - temp[1]] + 1 : 0;
  34.                         dp[i & 1][j][k] = Math.max(dp[i & 1][j][k], b);
  35.                     }
  36.                 }
  37.             }
  39.             return dp[(strs.length - 1) & 1][m][n];
  41.         }

时间复杂度O(mnl)

思路三：动态规划(一维)

  • 从原先的加法遍历，变成减法遍历，可对维度再次进行优化
  • 将转移方程优化为一维方程
  1. public int findMaxForm(String[] strs, int m, int n) {
  2.             //成本数组cnt
  3.             int[][] cnt = new int[strs.length][2];
  4.             for (int i = 0; i < strs.length; i++) {
  5.                 int c0 = 0, c1 = 0;
  7.                 for (char c : strs[i].toCharArray()
  8.                 ) {
  9.                     if (c == '1') {
  10.                         c1 += 1;
  11.                     } else {
  12.                         c0 += 1;
  13.                     }
  14.                 }
  15.                 cnt[i][0] = c0;
  16.                 cnt[i][1] = c1;
  17.             }
  18.             //二维数组，背包问题
  19.             int[][] f = new int[m + 1][n + 1];
  20.             for (int k = 0; k < strs.length; k++) {
  21.                 int zero = cnt[k][0], one = cnt[k][1];
  22.                 for (int i = m; i >= zero; i--) {
  23.                     for (int j = n; j >= one; j--) {
  24.                         f[i][j] = Math.max(f[i][j], f[i - zero][j - one] + 1);
  25.                     }
  26.                 }
  27.             }
  28.             return f[m][n];
  29.         }

时间复杂度O(k∗m∗n)