474-一和零.md

题目描述

一和零

题目简述

给你一个二进制字符串数组 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 。

分类

中等 动态规划

思路

思路1

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
  // [[ones, zeros]]
  strs = strs.map(i => statistics(i))
  // dp[i][j][k]
  // 0 - i(不含i) 的字符串中，最大为0 -> j 1 -> k的[ones, zeros]
  let dp = new Array(strs.length + 1).fill()
    .map(() => new Array(m + 1).fill()
    .map(() => new Array(n + 1).fill(0)))
  for (let i = 1; i <= strs.length; i ++) {
    const [ones, zeros] = strs[i - 1]
    for (let j = 0; j <= m; j ++) {
      for (let k = 0; k <= n; k ++) {
        // 不满足
        if (zeros > j || ones > k) {
          dp[i][j][k] = dp[i - 1][j][k]
        } else {
          // (不添加该字符， 添加该字符)
          dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - zeros][k - ones] + 1)
        }
      }
    }
  }
  return dp[strs.length][m][n]
  function statistics (str) {
    const oneLen = Array.from(str).filter(i => i === '1').length
    return [oneLen, str.length - oneLen]
  }
};

• 问题分析
  • 首先统计出每个字符串的一和零，记录为[ones, zeros]，这个任务交给statistics来执行。
  • dp[i][j][k]代表0 - i(不含i) 的字符串中，最大为1 -> j 0 -> k的[ones, zeros]。
  • 对字符顺序i，我们顺序进行遍历，拿到该字符strs[i]的一的个数ones，零的个数zeros.
  • j代表零的个数最大值，k代表一的个数最大值，如果当前字符的一或零已经超出限制，则不应该添加该字符，所以dp[i][j][k] = dp[i - 1][j][k]。否则满足条件，但是又分为两种情况，dp[i - 1][j - zeros][k - ones] + 1(添加该字符)或dp[i - 1][j][k](不添加该字符)，取两个值中更大的值。
  • 最终结果是dp[strs.length][m][n]
  • 需要注意初始化时候，留了个初始的边界来储存初始值为0