美文网首页
474. Ones and Zeroes

474. Ones and Zeroes

作者: becauseyou_90cd | 来源:发表于2018-07-24 02:40 被阅读0次

https://leetcode.com/problems/ones-and-zeroes/description/

解题算法:

  1. 状态转移方程是:newMax[zero][one] = Math.max(1 + max[zeroLeft][oneLeft], max[zero][one]); when zero >= neededZero && one >= neededOne 否则newMax[zero][one] = max[zero][one];

代码:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {

    int[][] max = new int[m + 1][n + 1];
for (int i = 0; i < strs.length; i++) {
    String str = strs[i];
    
    int neededZero = 0;
    int neededOne = 0;
    for (int j = 0; j < str.length(); j++) {
        if (str.charAt(j) == '0') {
            neededZero++;
        } else {
            neededOne++;
        }
    }
    
    int[][] newMax = new int[m + 1][n + 1];
    
    for (int zero = 0; zero <= m; zero++) {
        for (int one = 0; one <= n; one++) {
            if (zero >= neededZero && one >= neededOne) {
                int zeroLeft = zero - neededZero;
                int oneLeft = one - neededOne;
                newMax[zero][one] = Math.max(1 + max[zeroLeft][oneLeft], max[zero][one]);
            } else {
                newMax[zero][one] = max[zero][one];
            }
        }
    }
    
    max = newMax;
}
    return max[m][n];
}

}

相关文章

网友评论

      本文标题:474. Ones and Zeroes

      本文链接:https://www.haomeiwen.com/subject/rmssmftx.html