2020-09-21 OnesAndZeroes

本质上是一个双背包问题，背包问题是一个二维数据，这里采用了一个三维数组。但是效率较低，时间复杂度为o(strs.length*mn)

/**
 * @author liluo
 * @create 2020/9/21
 **/
public class OnesAndZeroes {
    public int findMaxForm(String[] strs, int m, int n) {
        int strLength = strs.length;
        Map<String, Integer> onesMap = new HashMap<>();
        Map<String, Integer> zerosMap = new HashMap<>();
        for (String str: strs) {
            findOnesAndZeros(str, onesMap, zerosMap);
        }


        int[][][] result = new int[strLength+1][m+1][n+1];
        for (int i = 0; i <= strLength; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    if (i == 0 || j+k == 0) {
                        result[i][j][k] = 0;
                    }else {
                        int ones = onesMap.get(strs[i-1]);
                        int zeros = zerosMap.get(strs[i-1]);
                        if (zeros <= j && ones <= k) {
                            result[i][j][k] = Math.max(result[i-1][j][k], result[i-1][j-zeros][k-ones] + 1);
                        }else {
                            result[i][j][k] = result[i-1][j][k];
                        }
                    }
                }
            }
        }
        return result[strLength][m][n];
    }

    private void findOnesAndZeros(String str, Map<String, Integer> onesMap, Map<String, Integer> zerosMap) {
        if (onesMap.containsKey(str)) {
            return;
        }
        int ones = 0, zeros = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                zeros ++;
            }
            if (str.charAt(i) == '1') {
                ones ++;
            }
        }
        onesMap.put(str, ones);
        zerosMap.put(str, zeros);
    }

}