【算法与数据结构】474、LeetCode一和零-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法与数据结构】474、LeetCode一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

【算法与数据结构】474、LeetCode一和零,算法,算法

二、解法

思路分析：本题要找strs数组的最大子集，这个子集最多含有 $m$ 个0和 $n$ 个1。本题也可以抽象成一个01背包的问题。其中，strs内的元素就是物品，而 $m$ 和 $n$ 就是背包的维度。 $d p [i] [j]$ 代表最多有i个0和j个1的strs的最大子集的大小。递归数组可以由 $d p [i] [j] = ma x (d p [i] [j], d p [i - zero N u m] [j - o n e N u m] + 1)$ 得出。和文章【算法与数据结构】算法与数据结构知识点中的01背包滚动数组一样，循环需要从后往前进行，否则会将strs重复计算。
程序如下：

class Solution {
public:
	int findMaxForm(vector<string>& strs, int m, int n) {
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));	// 默认初始化为0
		for (string str : strs) {	// 遍历物品
			int oneNum = 0, zeroNum = 0;
			for (char c : str) {
				if (c == '0') zeroNum++;
				else oneNum++;
			}
			for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
				for (int j = n; j >= oneNum; j--) {
					dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
				}
			}
		}
		return dp[m][n];
	}
};

复杂度分析：

时间复杂度： $O (K * m * n)$ ，K为strs的长度。
空间复杂度： $O (m * n)$ 。

三、完整代码

# include <iostream>
# include <vector>
# include <string>
using namespace std;

class Solution {
public:
	int findMaxForm(vector<string>& strs, int m, int n) {
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));	// 默认初始化为0
		for (string str : strs) {	// 遍历物品
			int oneNum = 0, zeroNum = 0;
			for (char c : str) {
				if (c == '0') zeroNum++;
				else oneNum++;
			}
			for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
				for (int j = n; j >= oneNum; j--) {
					dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
				}
			}
		}
		return dp[m][n];
	}
};

int main() {
	Solution s1;
	vector<string> strs = { "10", "0001", "111001", "1", "0" };
	int m = 5;
	int n = 3;
	int result = s1.findMaxForm(strs, m, n);
	cout << result << endl;
	system("pause");
	return 0;
}