LeetCode 474 - Ones and Zeroes


https://leetcode.com/problems/ones-and-zeroes/
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0sand 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Note:
  1. The given numbers of 0s and 1s will both not exceed 100
  2. The size of given string array won't exceed 600.
Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2:


Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
https://leetcode.com/problems/ones-and-zeroes/discuss/95808/0-1-knapsack-in-python
dp(k, x, y) = max(dp(k-1, x-z, y-o) + 1, dp(k-1, x, y))   (z is zeroes in strs[k], o is ones in strs[k])
dp(k, x, y) is the maximum strs we can include when we have x zeros, y ones and only the first k strs are considered.


dp(len(strs), M, N) is the answer we are looking for
https://leetcode.com/problems/ones-and-zeroes/discuss/121876/C%2B%2B-DP-Knapsack-Approach
https://leetcode.com/problems/ones-and-zeroes/discuss/95807/0-1-knapsack-detailed-explanation.
This problem is a typical 0-1 knapsack problem, we need to pick several strings in provided strings to get the maximum number of strings using limited number 0 and 1. We can create a three dimensional array, in which dp[i][j][k] means the maximum number of strings we can get from the first i argument strs using limited j number of '0's and k number of '1's.
For dp[i][j][k], we can get it by fetching the current string i or discarding the current string, which would result in dp[i][j][k] = dp[i-1][j-numOfZero(strs[i])][i-numOfOnes(strs[i])] and dp[i][j][k] = dp[i-1][j][k]; We only need to treat the larger one in it as the largest number for dp[i][j][k].
talking is cheap:
public int findMaxForm(String[] strs, int m, int n) {
    int l = strs.length;
    int[][][] dp = new int[l+1][m+1][n+1];
    
    for (int i = 0; i < l+1; i++) {
        int[] nums = new int[]{0,0};
        if (i > 0) {
            nums = calculate(strs[i-1]);
        }
        for (int j = 0; j < m+1; j++) {
            for (int k = 0; k < n+1; k++) {
                if (i == 0) {
                    dp[i][j][k] = 0;
                } else if (j>=nums[0] && k>=nums[1]) {
                    dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-nums[0]][k-nums[1]]+1);
                } else {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
    }
    
    return dp[l][m][n];
}

private int[] calculate(String str) {
    int[] res = new int[2];
    Arrays.fill(res, 0);
    
    for (char ch : str.toCharArray()) {
        if (ch == '0') {
            res[0]++;
        } else if (ch == '1') {
            res[1]++;
        }
    }
    
    return res;
}
By the way, 0-1 knapsack we cannot decrease the time complexity, but we can decrease the space complexity from ijk to j*k
public int findMaxForm(String[] strs, int m, int n) {
    int l = strs.length;
    int[][] dp = new int[m+1][n+1];
    
    for (int i = 0; i < m+1; i++) {
        Arrays.fill(dp[i], 0);
    }
    
    int[] nums = new int[]{0,0};
    for (String str : strs) {
        nums = calculate(str);
        for (int j = m; j >= nums[0]; j--) {
            for (int k = n; k >= nums[1]; k--) {
                if (j>=nums[0] && k>=nums[1]) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-nums[0]][k-nums[1]]+1);
                } else {
                    dp[j][k] = dp[j][k];
                }
            }
        }
    }
    
    return dp[m][n];
}

https://discuss.leetcode.com/topic/71417/java-iterative-dp-solution-o-mn-space
https://discuss.leetcode.com/topic/71459/java-28ms-solution
Time Complexity: O(kl + kmn), where k is the length of input string array and l is the average length of a string within the array.
The problem can be interpreted as: What's the max number of str can we pick from strs with limitation of m "0"s and n "1"s. Thus we can define dp[i][j] stands for max number of str can we pick from strs with limitation of i "0"s and j "1"s. For each str, assume it has a "0"s and b "1"s, we update the dp array iteratively and set dp[i][j] = Math.max(dp[i][j], dp[i - a][j - b] + 1). So and the end, dp[m][n] is the answer.
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int[] count = count(str);
            for (int i = m; i >= count[0]; i--) {
                for (int j = n; j >= count[1]; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m+1][n+1];
    for (int s = strs.length-1; s>=0;s--) {
        int[] count = count(strs[s]);
        for (int i=m;i>=0;i--) 
            for (int j=n;j>=0;j--) 
                if (i >= count[0] && j >= count[1]) 
                   dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);
    }
    return dp[m][n];
}
    
public int[] count(String str) {
    int[] res = new int[]{0,0};
    for (int i=0;i<str.length();i++) {
        if (str.charAt(i) == '0') res[0]++;
        else res[1]++;
    }
    return res;
 }
http://bookshadow.com/weblog/2016/12/11/leetcode-ones-and-zeroes/
二维01背包问题(Knapsack Problem)
状态转移方程:
for s in strs:
    zero, one = s.count('0'), s.count('1')
    for x in range(m, zero - 1, -1):
        for y in range(n, one - 1, -1):
            dp[x][y] = max(dp[x - zero][y - one] + 1, dp[x][y])
上式中,dp[x][y]表示至多使用x个0,y个1可以组成字符串的最大数目
public int findMaxForm(String[] strs, int m, int n) { int dp[][] = new int[m + 1][n + 1]; int ans = dp[0][0] = 0; for (String s : strs) { int zero = 0, one = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '0') { zero++; } else { one++; } } for (int i = m; i > zero - 1; i--) { for (int j = n; j > one - 1; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1); } } } return dp[m][n]; }

X. DP 2
https://discuss.leetcode.com/topic/71432/java-memoization-and-accepted-dp-solutions-with-explanations
A state of my DP (int i, int numOfZeros, int numOfOnes) describes the maximum number of strings we can construct starting from index 'i' by having numOfZeros zeros and numOfOnes ones.
There are two simple transition functions from upper state to lower state.
  • First transition is skipping the ith string and just taking the maximum value we can construct starting from i-1 th string.
  • Second transition is constructing current string (ith string) then adding maximum number of strings that can be constructed starting from i-1 th string by the rest of ones and zeros (numOfZeros - pair[i][0] and numOfOnes-pair[i][1]).
The value for the current state is the maximum of values of the two transaction. Finally the answer is the value of state that describes the number of strings that can be constructed starting from the last(or the first,actually does not matter) index of the input string by m zeros and n ones. In other words just return dp[strs.length-1][m][n];
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs == null || strs.length == 0 || (m == 0 && n == 0)) return 0;
        int dp [][][] = new int[strs.length][m+1][n+1];
        int [][] pairs = new int[strs.length][2];
        for(int i = 0;i<strs.length;i++){
            for(int j = 0;j<strs[i].length();j++){
                char ch  = strs[i].charAt(j);
                if(ch == '0') pairs[i][0]++;
                else pairs[i][1]++;
            }
        }
        for(int zeros =  pairs[0][0];zeros<=m;zeros++){
               for(int ones = pairs[0][1];ones<=n;ones++){
                   dp[0][zeros][ones] = 1;
               }
        } 
        for(int i  = 1;i<strs.length;i++){
           for(int zeros =  0;zeros<=m;zeros++){
               for(int ones = 0;ones<=n;ones++){
                   dp[i][zeros][ones] = dp[i-1][zeros][ones];
               }
           }
           for(int zeros =  pairs[i][0];zeros<=m;zeros++){
               for(int ones = pairs[i][1];ones<=n;ones++){
                   dp[i][zeros][ones] = Math.max(dp[i-1][zeros][ones], 1+dp[i-1][zeros-pairs[i][0]][ones-pairs[i][1]]);
               }
           }
        }
        return dp[strs.length-1][m][n];
    }

X. dfs + cache
https://discuss.leetcode.com/topic/71432/java-memoization-and-accepted-dp-solutions-with-explanations
https://leetcode.com/problems/ones-and-zeroes/discuss/95845/Easy-to-understand-Recursive-Solutions-in-Java-with-Explanation
the first thing we have to do, is to turn the array of string into array of pairs. The ith pair contains number of zeros and ones in ith string. Next step is to determine how many pairs from the array we can cover by m and n;
The strightforward idea is backtracking. So we can just try out covering strings starting from different positions and maximize the result
Time and space complexity of the solution is O(n*m*pairs.length)
    Integer memo[][][];
    public int findMaxForm(String[] strs, int m, int n) {
        if(strs == null || strs.length == 0 || (m == 0 && n == 0)) return 0;
        memo = new Integer[m+1][n+1][strs.length];
        int [][] pairs = new int[strs.length][2];
        for(int i = 0;i<strs.length;i++){
            for(int j = 0;j<strs[i].length();j++){
                char ch  = strs[i].charAt(j);
                if(ch == '0') pairs[i][0]++;
                else pairs[i][1]++;
            }
        }
        return go(pairs, 0, m, n);
    }
    
    public int go(int pairs[][], int s, int m, int n){
        if(s >= pairs.length) return 0;
        if(memo[m][n][s] != null) return memo[m][n][s];
        int count = 0;
        for(int i = s;i<pairs.length;i++){
            int dm = m - pairs[i][0];
            int dn = n - pairs[i][1];
            if(dm >= 0 && dn >=0) {
                count = Math.max(count, 1+go(pairs, i+1, dm, dn));
            }
        }
        memo[m][n][s] = count;
        return count;
    }

https://leetcode.com/problems/ones-and-zeroes/discuss/95851/4-Python-solution-with-detailed-explanation

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts