LeetCode 474. 一和零

1、题目

一和零 - 力扣（LeetCode） https://leetcode-cn.com/problems/ones-and-zeroes/submissions/

2、题解

这道题真的是折磨我好久了，一开始我以为很简单，不就是看看消耗了多少1和0吗？记录一下以每个字符串为首的消耗情况，比较一下不就可以了。后来发现，这样的话，如果strs数组的中间有很多大消耗的字符串，得到的结果就会有误。所以我进行了排序，先按照长度排序，后来又是按照字符中的某个数字的多少进行排序。【借鉴自根哥。】但是我直接对strs数组进行升降序就是不对。怎么都不对。我暂时没有想明白是为什么？这部分错误代码之后部分贴出。
之后我回到最开始的那个思路，不就是看消耗了多少个1和0吗？如果这个消耗太大部划算就不把这个放进去不就行了。

这是一个非常典型的二维0/1背包问题，相当于是在问我们有一个背包的空间大小为m，最大载重为n，给定k个物品，已知每个物品的大小和重量，试问最多能放进多少个物品（每个物品只能放一次）。
该问题的状态方程为
f(m,n,k)=max(f(m,n,k−1),1+f(m−i,n−j,k−1))f(m,n,k)=max(f(m,n,k−1),1+f(m−i,n−j,k−1))

f(m,n,k)f(m,n,k)是指在限制为(m,n)(m,n)的情况下，考虑前k个字符串所能得到的最多字符串的个数。
这个式子的意思是，我们从放第1个字符串开始考虑，直到第k个字符串，如果在限制为(m,n)(m,n)的情况下，放这个字符串进去比不放这个字符串得到的个数要多，那么我们就放这个字符串进去，否则不放。
这是借鉴别人的思路，我认为非常精彩，所以就采取了这个解决方法。

3、

正确题解：

class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m+1][n+1];

            for(String str : strs){
                int count1 = 0;
                int count0 = 0;
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i) == '1'){
                        count1 ++;
                    }else{
                        count0 ++;  
                    }
                }
                if (count0 > m || count1 > n){
                    continue;
                }
                for (int i = m; i >= count0 ; i--) {
                    for (int j = n; j >= count1 ; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-count0][j-count1] + 1);
                    }
                }

            }
            return dp[m][n];
        }
    }

错误题解：

class Solution1 {
        public int findMaxForm(String[] strs, int m, int n) {
            int result=0;//当前最大的结果数
            int upResult=0;
            int downResult=0;
            //升序排列
            Arrays.sort(strs, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return Math.min(getCharNum(o1,"0"),getCharNum(o1,"1"))-Math.min(getCharNum(o2,"0"),getCharNum(o2,"1"));
                }
            });
            for (int i = 0; i < strs.length; i++) {
                int maxNow = getMaxNow(i, strs, m, n);
                if(maxNow>upResult){
                    upResult=maxNow;
                }
            }
            //降序排列
            Arrays.sort(strs, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return Math.min(getCharNum(o2,"0"),getCharNum(o2,"1"))-Math.min(getCharNum(o1,"0"),getCharNum(o1,"1"));
                }
            });
            for (int i = 0; i < strs.length; i++) {
                int maxNow = getMaxNow(i, strs, m, n);
                if(maxNow>downResult){
                    downResult=maxNow;
                }
            }
             result= upResult > downResult ? upResult : downResult;
         
            return result;

        }
        //以i为首，得到当前最大
        //0 1 2 3 4%2=0 1 0(2) 1 0(2)
        private int getMaxNow(int i, String[] strs, int m, int n) {
            int maxNow=0;
            int length = strs.length;
            for (int j = i; j < length+i; j++) {
                int target = j % length;
                String str = strs[target];
                //当下0和1的个数；
                int charNum0 = getCharNum(str, "0");
                int charNum1 = getCharNum(str, "1");
                if(m>=charNum0&&n>=charNum1){
                    maxNow++;
                    m=m-charNum0;
                    n=n-charNum1;
                }else{
                  return maxNow;
                }
            }
           return maxNow;
        }
        // 5 length
        // 0到4 i
        public int getCharNum(String st,String M) {
            int count = (st.length()-st.replace(M, "").length())/M.length();
            return count;
        }
    }

4、执行结果

image.png