每日一题 LeetCode 474. 一和零 java题解

题目

https://leetcode-cn.com/problems/ones-and-zeroes/
每日一题 LeetCode 474. 一和零 java题解

1.未优化的动态规划

思路

动态规划。
用dp[i][j][k]表示前i个字符串中 j个0、k个1的最大子集大小 。下标均从1开始计数。
当i=0时,没有字符串,所以dp[i][j][k]=0。

转移方程
这个字符串的0和1个数分别为zeros,ones.
1.j>=zeros&&k>=ones
(1)向子集中加入这个字符串
dp[i][j][k]=dp[i-1][j-zeros][k-ones]+1
(2)不向子集中加入
dp[i][j][k]=dp[i-1][j][k]
综上,dp[i][j][k]=min(dp[i-1][j-zeros][k-ones]+1,dp[i][j][k]=dp[i-1][j][k]);
2.else
dp[i][j][k]=dp[i-1][j][k]

代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len=strs.length;
        if(len==0)
            return 0;
        int[][][] dp=new int[len+1][m+1][n+1];
        /*
        for(int j=0;j<=m;j++){
            for(int k=0;k<=n;k++){
                dp[0][j][k]=0;
            }
        }
        */
        
        for(int i=1;i<=len;i++){
            int zeros=count(strs[i-1]);
            int ones=strs[i-1].length()-zeros;
            
            for(int j=0;j<=m;j++){
                for(int 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-1][j-zeros][k-ones]+1,dp[i][j][k]);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
    //统计0的个数
    public int count(String s){
        int count=0;
        for(char c:s.toCharArray()){
            if(c=='0'){
                count++;
            }
        }
        return count;
    }
}

复杂度

时间复杂度:O(lmn+L),其中 l 是数组 strs 的长度,m 和 n 分别是 0 和 1 的容量,L 是数组 strs 中的所有字符串的长度之和。
空间复杂度 O(lmn)

2.空间优化

复杂度

空间复杂度:O(mn),其中 m 和 n 分别是 0 和 1 的容量。使用空间优化的实现,需要创建 m+1 行 n+1 列的二维数组dp。

代码

由于dp[i][][] 的每个元素值的计算只和dp[i−1][][] 的元素值有关,因此可以使用滚动数组的方式,去掉 dp 的第一个维度,将空间复杂度优化到 O(mn)。
实现时,内层循环需采用倒序遍历的方式,这种方式保证转移来的是dp[i−1][][] 中的元素值。

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int length = strs.length;
        for (int i = 0; i < length; i++) {
            int[] zerosOnes = getZerosOnes(strs[i]);
            int zeros = zerosOnes[0], ones = zerosOnes[1];
            for (int j = m; j >= zeros; j--) {
                for (int k = n; k >= ones; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }

上一篇:一和零


下一篇:算法题:最长公共前缀(题目+思路+代码+注释)