Java Solution


  • 0
    Z
    public int findMaxForm(String[] strs, int m, int n) {
            int[][] str = countNums(strs);
            sort(str, m, n);
            int max = 0;
            for (int i = 0; i < str.length; i++) {
                if (str.length - i < max) {
                    return max;
                }
                int one = n, zero = m;
                int j = i;
                for (; j < str.length; j++) {
                    if (str[j][0] <= zero && str[j][1] <= one) {
                        zero -= str[j][0];
                        one -= str[j][1];
                    } else {
                        break;
                    }
                }
                max = Math.max(j - i, max);
            }
            return max;
        }
        private int[][] countNums(String[] strs) {
            int[][] str = new int[strs.length][2];
            for (int i = 0; i < strs.length; i++) {
                for (int j = 0; j < strs[i].length(); j++) {
                    char c = strs[i].charAt(j);
                    if (c == '1') {
                        str[i][1]++;
                    } else {
                        str[i][0]++;
                    }
                }
            }
            return str;
        }
        private void sort(int[][] str, int m, int n) {
            if (m == n) {
                Arrays.sort(str, new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        if (o1[0] + o1[1] - o2[0] - o2[1] == 0) {
                            return Math.min(o1[0], o1[1]) - Math.min(o2[0], o2[1]);
                        }
                        return o1[0] + o1[1] - o2[0] - o2[1];
                    }
                });
            } else if (m < n) {
                Arrays.sort(str, new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        if (o1[0] == o2[0]) {
                            return o1[1] - o2[1];
                        }
                        return o1[0] - o2[0];
                    }
                });
            } else {
                Arrays.sort(str, new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        if (o1[1] == o2[1]) {
                            return o1[0] - o2[0];
                        }
                        return o1[1] - o2[1];
                    }
                });
            }
        }
    

    The idea here is sort array based on the relation between m and n, then check all possible optimal combinations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.