LeetCode 474 - Ones and Zeroes

作者 QIFAN 日期 2017-01-04
LeetCode 474 - Ones and Zeroes

原题链接: 474. Ones and Zeroes


题干

给定一个字符串数组,其中元素为只由 0 和 1 构成。 另给一个数字 m 与数字 n ,求用 m 个 0 和 n 个 1 最多可以构成数组内的多少元素?

说明

  • m 和 n 都不超过 100
  • 数组长度不大于 600

例子 1
输入:[“10”, “0001”, “111001”, “1”, “0”] , m = 5 , n = 3
输出:4
解释:5 个 0 和 3 个 1 最多可以构成 4 个数组内的字符串,分别是 “10” , “0001” , “1” , “0”

例子 2
输入:[“10”, “0”, “1”], m = 1, n = 1
输出:2
解释:最多可组成两个,分别是 ”0“ , ”1“

思路

首先排序,这里可以用三种排序方法:按长度,按 0 的个数,按 1 的个数。我先试一试按长度。

联想到动态规划 + 递归(自上而下),因为下一个字符串是否选择与上一步剩下的 0 和 1 有着直接关系。

假设选择了 a[i - 1] = x0y1 , 还剩 m 个 0 与 n 个 1 ,a[i] = x’0y’1
case 1: m ≥ x’ && n ≥ y’ ,选还是不选?
case 2: m ≤ x’ || n ≤ y’ ,选还是不选?

感觉每一种情况都会有几种不同的子情况。如果全部列举,最差情况需要 $O(2^n)$ 。思考一下有哪些信息没有利用,哪一些步骤是多余的。

至少应该确定,我们需要有一个数据结构来记录选择的状态。观察发现,状态仅仅与 当前位置,剩余 0 的个数,与剩余 1 的个数有关,当这三个参数相同,不管前面选择了什么,对后面都是一样的。

想法慢慢浮现出来了,设置一个三维数组,长度分别是:数组长度,m + 1 , n + 1 。因为还要计算字符串中 0 和 1 的数量,避免多次运算,干脆用一个二维数组存起来。后面就是常规的方法了。时间复杂度为 $O(length m n)$ ,空间复杂度为 $O(length m n)$ 。

代码(cr:Java memoization and accepted DP solutions with explanations):

public int findMaxForm(String[] strs, int m, int n) {
if(strs == null || strs.length == 0 || (m == 0 && n == 0)) {
return 0;
}
int dp [][][] = new int[strs.length][m + 1][n + 1];
int [][] pairs = new int[strs.length][2];
for(int i = 0;i < strs.length;i++){
for(int j = 0; j < strs[i].length(); j++){
char ch = strs[i].charAt(j);
if(ch == '0') {
pairs[i][0]++;
}
else {
pairs[i][1]++;
}
}
}
// 对 dp 数组进行初始化,对于 i = 0 ,0 和 1 只要多于 字符串中的值,都可以有 1 个。
for(int zeros = pairs[0][0]; zeros <= m; zeros++){
for(int ones = pairs[0][1]; ones <= n; ones++){
dp[0][zeros][ones] = 1;
}
}
for(int i = 1; i < strs.length; i++){
for(int zeros = 0; zeros <= m; zeros++){
for(int ones = 0; ones <= n; ones++){
dp[i][zeros][ones] = dp[i - 1][zeros][ones];
}
}
// 更新
for(int zeros = pairs[i][0]; zeros <= m; zeros++){
for(int ones = pairs[i][1]; ones <= n; ones++){
dp[i][zeros][ones] = Math.max(dp[i - 1][zeros][ones], 1 + dp[i - 1][zeros-pairs[i][0]][ones - pairs[i][1]]);
}
}
}
return dp[strs.length-1][m][n];
}

有一道类似的题:Coin on the Table Redux