LeetCode474. Ones and Zeroes

1、题目链接

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

2、解题思路

这道题的意思是给你m个0和n个1，然后还有一个字符串数组strs，然后让你找出由m个0和n个1拼接成的存在于数组strs中的字符串的最大数量，你最多只能使用m次0和n次1。换句话说，你要尽可能多的拼接成数组中的字符串，并且在有限的0和1。想想看，我们如果能找到字符串数组中的字符个数最小的（又涉及到排序），是不是就可以尽可能多的拼出想要的字符串，但是如果根据字符串个数来的话，那么假如有这么一种情况：

strs = {"11100", "110000", "100000"}
m = 9; n = 3

按照正常来说，我们会先取第1个字符串，但是如果取完第1个字符之后，后面就不能再取了，因为1已经用完了，但是实际上我们是要取第二个和第三个字符串的，所以我们不能这样去给字符串排序，换一种思路，如果是按照字符串当中0或者1比较少的那个来进行升序排列的话，是不是就可以了，用上面的例子来说，第一个字符串最少的是字符0，用0来作为排序的标准，第二个字符串最少的字符是1，用1来作为排序的标准，以此类推；这样子我发现又有一种情况：

strs = {111110, 1100, 11100}
m = 5; n = 5

就是某个字符串中某一个字符比较多，另一个字符比较少，这样的话如果按照上面我们说的那个排序肯定是不行的，又得转变一下，我们用 min((m - 字符串中0的个数),(n - 字符串中1的个数)) 倒叙排列，用上面这个例子，倒叙排列之后就是 {"1100", "11100", "111110"}，第一个字符串中用m/n减法之后取最小值是0，但是我们要降序排列，说明它会被放到最后一个，以此类推。

3、代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (null == strs || strs.length == 0 || (m == 0 && n == 0)) {
            return 0;
        }

        List<OneAndZero> zeroList = new ArrayList<>();   //第一种情况
        List<OneAndZero> oneList = new ArrayList<>();   //第二种情况
        //遍历字符串数组，计算0和1的个数并保存
        for (String s : strs) {
            int countZero = 0, countOne = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '0') {
                    countZero++;
                } else if (s.charAt(i) == '1') {
                    countOne++;
                }
            }
            zeroList.add(new OneAndZero(s, countZero, countOne));
            oneList.add(new OneAndZero(s, countZero, countOne));
        }
        //升序排序
        Collections.sort(zeroList, new Comparator<OneAndZero>() {
            @Override
            public int compare(OneAndZero o1, OneAndZero o2) {
                return Math.min(o1.countZero, o1.countOne) - Math.min(o2.countZero, o2.countOne);
            }
        });
        //降序排序
        Collections.sort(oneList, new Comparator<OneAndZero>() {
            @Override
            public int compare(OneAndZero o1, OneAndZero o2) {
                return Math.min(m - o2.countZero, n - o2.countOne) - Math.min(m - o1.countZero, n - o1.countOne);
            }
        });

        int countZero = findMax(zeroList, m, n);
        int countOne = findMax(oneList, m, n);
        //返回两者中的最大
        return Math.max(countZero, countOne);
    }
    
    public int findMax(List<OneAndZero> list, int m, int n) {
        int count = 0;
        for (int i = 0; i < list.size(); i++) {
            if (m >= list.get(i).countZero && n >= list.get(i).countOne) {
                count++;
                m -= list.get(i).countZero;
                n -= list.get(i).countOne;
            }
        }
        return count;
    }
    
    class OneAndZero {
        String str;
        int countZero;
        int countOne;

        public OneAndZero(String str, int countZero, int countOne) {
            this.str = str;
            this.countZero = countZero;
            this.countOne = countOne;
        }
    }
}

4、结果

QQ20190719-181421@2x.png