474.一和零

链接：474.一和零
难度：Medium
标签：数组、字符串、动态规划
简介：请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

题解 1 - javascript

• 编辑时间：2021-09-13
• 执行用时：576ms
• 内存消耗：102.2MB
• 编程语言：javascript
• 解法介绍：动态规划。

var findMaxForm = function (strs, m, n) {
  const length = strs.length;
  const dp = new Array(length + 1)
    .fill(0)
    .map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)));
  for (let i = 1; i <= length; i++) {
    const zerosOnes = getZerosOnes(strs[i - 1]);
    let zeros = zerosOnes[0],
      ones = zerosOnes[1];
    for (let j = 0; j <= m; j++) {
      for (let k = 0; k <= n; k++) {
        dp[i][j][k] = dp[i - 1][j][k];
        if (j >= zeros && k >= ones) {
          dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
        }
      }
    }
  }
  return dp[length][m][n];
};
const getZerosOnes = str => {
  const zerosOnes = new Array(2).fill(0);
  const length = str.length;
  for (let i = 0; i < length; i++) {
    zerosOnes[str[i].charCodeAt() - '0'.charCodeAt()]++;
  }
  return zerosOnes;
};

题解 2 - typescript

• 编辑时间：2021-09-13
• 执行用时：260ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：动态规划。

function findMaxForm(strs: string[], m: number, n: number): number {
  const len = strs.length;
  const dp = new Array(2)
    .fill(0)
    .map(_ => new Array(m + 1).fill(0).map(_ => new Array(n + 1).fill(0)));
  for (let i = 1; i <= len; i++) {
    const { count0, count1 } = getCount(strs[i - 1]);
    const idx = i % 2;
    const prevIdx = idx ^ 1;
    for (let j = 0; j <= m; j++) {
      for (let k = 0; k <= n; k++) {
        dp[idx][j][k] = dp[prevIdx][j][k];
        if (count1 <= k && count0 <= j)
          dp[idx][j][k] = Math.max(dp[prevIdx][j][k], dp[prevIdx][j - count0][k - count1] + 1);
      }
    }
  }
  return dp[len % 2][m][n];
  function getCount(str: string): { count0: number; count1: number } {
    let count0 = 0;
    let count1 = 0;
    for (let i = 0, n = str.length; i < n; i++)
      if (str[i] === '0') count0++;
      else count1++;
    return { count0, count1 };
  }
}