474. 一和零 - 已题解语言：Python/C++/Java/C#/JavaScript/Go/Ruby

LeetCode Python, Java, C++ > 动态规划 > 474. 一和零 > 已支持 Python, C++, Java, C#, JavaScript, Go, Ruby > LeetCode GitHub Code 或转发

力扣链接：474. 一和零，难度等级：中等。

给你一个二进制字符串数组 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]' consists only of digits '0' and '1'
1 <= m, n <= 100

思路
上一题 下一题

本题偏难，建议先完成一个同类的简单题目416. 分割等和子集。

在完成了416后，你会发现本题要在两个维度上解决0/1问题。
解决方法是先在一维上解决问题，然后再将其扩展到二维。
没有必要画一个同时考虑两个维度的网格，那太复杂了。我们可以先只考虑0的数量限制。

“动态规划”的模式

“动态规划”，需要用dp数组来保存结果。dp[i][j]的值可以由它的前一个（或多个）值通过公式转化出来。因此，dp[i][j]值是一步一步推导出来的，它和先前的dp记录值都有联系。

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，按顺序填入dp网格数据。
根据dp网格数据，推导出递推公式。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个位置可互换的数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，按顺序填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出递推公式。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个位置可互换的数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

“0/1背包问题”的模式

典型的“0/1背包问题”，指每个“物品”只能使用一次，来填充“背包”。“物品”有“重量”和“价值”属性，求“背包”能存放的“物品”的最大价值。

其特点是：有一组数字，每个数字只能被使用一次，通过某种计算得到另一个数字。问题也可以变成能否得到？有多少种变化？等。

因为“0/1背包问题”属于“动态规划”，所以我会用“动态规划”的模式讲解。

确定数组dp的每个值代表的含义。
- 首选一维滚动数组，代码简洁。
- 确定什么是“物品”，什么是“背包”。
- 如果dp[j]是一个布尔值，则dp[j]表示是否可以前i个物品的和得到j。
- 如果dp[j]是一个数值，则dp[j]表示是利用前i个物品，dp[j]能达到的所求问题的极限值。
初始化数组dp的值。
- 确定“背包”的大小。需要让背包大小再加1，即插入dp[0]做为起始点，方便理解和引用。
- dp[0]有时需要特殊处理。
根据一个示例，“按顺序”填入dp网格数据。
- 先在外层循环中，遍历物品。
- 后在内层循环中，遍历背包大小。
  - 在遍历背包大小时，由于dp[j]取决于dp[j]和dp[j - weights[i]]，因此我们应该从右到左遍历dp数组。
  - 请思考是否可以从从左到右遍历dp数组？
根据dp网格数据，推导出“递推公式”。
- 如果dp[j]是一个布尔值：
```
dp[j] = dp[j] || dp[j - weights[i]]
```
- 如果dp[j]是一个数值：
```
dp[j] = min_or_max(dp[j], dp[j - weights[i]] + values[i])
```
写出程序，并打印dp数组，不合预期就调整。

步骤

确定dp[j]的含义
- 由于我们目前只考虑零计数约束，因此我们可以使用一维dp数组。
- 物品是strs，背包是max_zero_count。
- dp[j]表示最多可以用j个零来选择的最大字符串数。
- dp[j]是一个整数。
确定dp数组的初始值
- 使用一个例子，示例1：输入：strs = ["10","0001","111001","1","0"]，m = 5，n = 3。
- 初始化后：
```
max_zero_count = m
dp = [0] * (max_zero_count + 1)
```
- dp[0] = 0，表示没有零，我们可以选择 0 个字符串。
- dp[j] = 0 作为初始值，因为我们稍后将使用 max 来增加它们。

根据一个示例，“按顺序”填入dp网格数据。

# Initial state
#    0 1 2 3 4 5
#    0 0 0 0 0 0

# After processing "10" (1 zero)
#    0 1 2 3 4 5
#    0 1 1 1 1 1

# After processing "0001" (3 zeros)
#    0 1 2 3 4 5
#    0 1 1 1 2 2

# After processing "111001" (2 zeros)
#    0 1 2 3 4 5
#    0 1 1 2 2 2

# After processing "1" (0 zeros)
#    0 1 2 3 4 5
#    0 2 2 3 3 3

# After processing "0" (1 zero)
#    0 1 2 3 4 5
#    0 2 3 3 4 4

根据dp网格数据，推导出“递推公式”。
```
dp[j] = max(dp[j], dp[j - zero_count] + 1)
```
写出程序，并打印dp数组，不合预期就调整。

只考虑0数量限制的代码是：

class Solution:
    def findMaxForm(self, strs: List[str], max_zero_count: int, n: int) -> int:
        dp = [0] * (max_zero_count + 1)

        for string in strs:
            zero_count = count_zero(string)

            for j in range(len(dp) - 1, zero_count - 1, -1): # must iterate in reverse order!
               dp[j] = max(dp[j], dp[j - zero_count] + 1)

            return dp[-1]


def count_zero(string):
    zero_count = 0

    for bit in string:
        if bit == '0':
            zero_count += 1

    return zero_count

现在，你可以考虑另一个维度：`1`的数量限制。

它应该以与“0”类似的方式处理，只不过是在另一个维度上。请参阅下面的完整代码。

复杂度

时间复杂度

O(N * M * Len)

空间复杂度

O(N * M)

Python #

class Solution:
    def findMaxForm(self, strs: List[str], max_zero_count: int, max_one_count: int) -> int:
        dp = [[0] * (max_one_count + 1) for _ in range(max_zero_count + 1)]

        for string in strs:
            zero_count, one_count = count_zero_one(string)

            for i in range(len(dp) - 1, zero_count - 1, -1):
                for j in range(len(dp[0]) - 1, one_count - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero_count][j - one_count] + 1)

        return dp[-1][-1]


def count_zero_one(string):
    zero_count = 0
    one_count = 0

    for bit in string:
        if bit == '0':
            zero_count += 1
        else:
            one_count += 1

    return zero_count, one_count

C++ #

class Solution {
public:
    int findMaxForm(vector<string>& strs, int max_zero_count, int max_one_count) {
        vector<vector<int>> dp(max_zero_count + 1, vector<int>(max_one_count + 1, 0));

        for (auto& str : strs) {
            auto zero_count = 0;
            auto one_count = 0;

            for (auto bit : str) {
                if (bit == '0') {
                    zero_count++;
                } else {
                    one_count++;
                }
            }

            for (auto i = max_zero_count; i >= zero_count; i--) {
                for (auto j = max_one_count; j >= one_count; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zero_count][j - one_count] + 1);
                }
            }
        }

        return dp[max_zero_count][max_one_count];
    }
};

Java #

class Solution {
    public int findMaxForm(String[] strs, int maxZeroCount, int maxOneCount) {
        var dp = new int[maxZeroCount + 1][maxOneCount + 1];

        for (var str : strs) {
            var zeroCount = 0;
            var oneCount = 0;

            for (var bit : str.toCharArray()) {
                if (bit == '0') {
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }

            for (var i = maxZeroCount; i >= zeroCount; i--) {
                for (var j = maxOneCount; j >= oneCount; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1);
                }
            }
        }

        return dp[maxZeroCount][maxOneCount];
    }
}

C# #

public class Solution
{
    public int FindMaxForm(string[] strs, int maxZeroCount, int maxOneCount)
    {
        var dp = new int[maxZeroCount + 1, maxOneCount + 1];

        foreach (var str in strs)
        {
            var (zeroCount, oneCount) = CountZeroOne(str);

            for (var i = maxZeroCount; i >= zeroCount; i--)
            {
                for (var j = maxOneCount; j >= oneCount; j--)
                {
                    dp[i, j] = Math.Max(dp[i, j], dp[i - zeroCount, j - oneCount] + 1);
                }
            }
        }

        return dp[maxZeroCount, maxOneCount];
    }

    (int, int) CountZeroOne(string str)
    {
        var zeroCount = 0;
        var oneCount = 0;

        foreach (var bit in str)
        {
            if (bit == '0')
            {
                zeroCount++;
            }
            else
            {
                oneCount++;
            }
        }

        return (zeroCount, oneCount);
    }
}

JavaScript #

var findMaxForm = function (strs, maxZeroCount, maxOneCount) {
  const dp = Array(maxZeroCount + 1).fill().map(
    () => Array(maxOneCount + 1).fill(0)
  )

  for (const str of strs) {
    const [zeroCount, oneCount] = countZeroOne(str)

    for (let i = dp.length - 1; i >= zeroCount; i--) {
      for (let j = dp[0].length - 1; j >= oneCount; j--) {
        dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1)
      }
    }
  }

  return dp.at(-1).at(-1)
};

function countZeroOne(str) {
  let zeroCount = 0
  let oneCount = 0

  for (const bit of str) {
    if (bit === '0') {
      zeroCount++
    } else {
      oneCount++
    }
  }

  return [zeroCount, oneCount]
}

Go #

func findMaxForm(strs []string, maxZeroCount int, maxOneCount int) int {
    dp := make([][]int, maxZeroCount + 1)
    for i := range dp {
        dp[i] = make([]int, maxOneCount + 1)
    }

    for _, str := range strs {
        zeroCount, oneCount := countZeroOne(str)

        for i := len(dp) - 1; i >= zeroCount; i-- {
            for j := len(dp[0]) - 1; j >= oneCount; j-- {
                dp[i][j] = max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1)
            }
        }
    }

    return dp[maxZeroCount][maxOneCount]
}

func countZeroOne(str string) (int, int) {
    zeroCount := 0
    oneCount := 0

    for _, bit := range str {
        if bit == '0' {
            zeroCount++
        } else {
            oneCount++
        }
    }

    return zeroCount, oneCount
}

Ruby #

def find_max_form(strs, max_zero_count, max_one_count)
  dp = Array.new(max_zero_count + 1) do
    Array.new(max_one_count + 1, 0)
  end

  strs.each do |string|
    zero_count, one_count = count_zero_one(string)

    (zero_count...dp.size).reverse_each do |i|
      (one_count...dp[0].size).reverse_each do |j|
        dp[i][j] = [ dp[i][j], dp[i - zero_count][j - one_count] + 1 ].max
      end
    end
  end

  dp[-1][-1]
end

def count_zero_one(string)
  zero_count = 0
  one_count = 0

  string.each_char do |bit|
    if bit == '0'
      zero_count += 1
    else
      one_count += 1
    end
  end

  [ zero_count, one_count ]
end

其它语言

欢迎贡献代码到 LeetCode Python GitHub -> 474. 一和零。感谢！

上一题下一题

游客

全部题解

Welcome !

LeetCode Python, Java, C++ > 动态规划 > 474. 一和零 > 已支持 Python, C++, Java, C#, JavaScript, Go, Ruby > LeetCode GitHub Code 或 转发