This is the sixth day of my participation in Gwen Challenge
Topic describes
This is 474. One and zero on LeetCode, of medium difficulty.
Tag: “01 knapsack”, “Knapsack problem”, “Multidimensional Knapsack”, “Dynamic Programming”
You are given a binary string array STRS and two integers M and n.
Find and return the size of the largest subset of STRS that has at most m zeros and N ones.
If all the members of x are also members of y, set x is a subset of set y.
Example 1:
Input: STRS = [" 10 ", "0001", "111001", "1", "0"], m = 5, n = 3 output: 4: The largest subset with at most five zeros and three ones is {"10","0001","1","0"}, so the answer is 4. Other, but smaller, subsets that satisfy the question include {"0001","1"} and {"10","1","0"}. {"111001"} does not satisfy the problem because it contains four ones and is greater than the value 3 of n.Copy the codeExample 2:
Input: STRS = ["10", "0", "1"], m = 1, n = 1 Output: 2 Explanation: The largest subset is {"0", "1"}, so the answer is 2.Copy the codeTip:
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- STRS [I] consists only of ‘0’ and ‘1’
- 1 <= m, n <= 100
(Multidimensional) 01 backpack
Questions usually related to the knapsack problem test the ability to turn the original problem into a knapsack problem.
To transform the original problem into a knapsack problem, the concepts of “value” and “cost” are often abstracted from the problem.
A. backpack problem B. backpack problem C. backpack problem D. backpack problem
Each string has a value of 1 (each contributes 1 to the answer), and the cost of the selection is the number of 1s and 0s in the string.
They’re asking us what is the maximum value if the number of 1s is no more than MMM and the number of 0s is no more than NNN.
Since each string can only be selected once, and the selection of each string corresponds to “value” and “cost”, the question is also what is the “maximum value”.
Therefore, it can be directly applied to the “state definition” of 01 backpack:
The represents consider k items before the number 1 capacity does not exceed
The number 0 cannot exceed the capacity limit
The value of each string is 1.
With a “state definition”, the “transition equation” is also easy to derive:
The CNTCNTCNT array records the number 010101 that appears in the string.
Code (P1P1P1 separates the first item from the first item for ease of understanding, or does not need to, just make the item subscript start at 111, see P2P2P2) :
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
// Preprocess the number of 0s and 1s per character
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zero++;
} else {
one++;
}
}
cnt[i] = new int[]{zero, one};
}
// Only the first item is considered
int[][][] f = new int[len][m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[0][i][j] = (i >= cnt[0] [0] && j >= cnt[0] [1])?1 : 0; }}// Take the rest of the items into account
for (int k = 1; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// leave the KTH item unselected
int a = f[k-1][i][j];
// Select the KTH item (provided there are enough m and N quotas available)
int b = (i >= zero && j >= one) ? f[k-1][i-zero][j-one] + 1 : 0; f[k][i][j] = Math.max(a, b); }}}return f[len-1][m][n]; }}Copy the codeclass Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][][] f = new int[len + 1][m + 1][n + 1];
for (int k = 1; k <= len; k++) {
int zero = cnt[k - 1] [0], one = cnt[k - 1] [1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
int a = f[k - 1][i][j];
int b = (i >= zero && j >= one) ? f[k - 1][i - zero][j - one] + 1 : 0; f[k][i][j] = Math.max(a, b); }}}returnf[len][m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗n)O(K * M * n)O(K ∗m∗n) for handling state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(K ∗m∗n)O(K * m * n)O(K ∗m∗n)
Scroll to the array
According to “state transition”, when updating the state of an item, it only depends on the state of the previous item.
Therefore, you can use the “scroll array” approach for spatial optimization.
Code (P1P1P1 separates the first item from the first item for ease of understanding, or does not need to, just make the item subscript start at 111, see P2P2P2) :
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
// Preprocess the number of 0s and 1s per character
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') {
zero++;
} else {
one++;
}
}
cnt[i] = new int[]{zero, one};
}
// Only the first item is considered
// Change the item dimension to 2
int[][][] f = new int[2][m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
f[0][i][j] = (i >= cnt[0] [0] && j >= cnt[0] [1])?1 : 0; }}// Take the rest of the items into account
for (int k = 1; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// leave the KTH item unselected
// Change k-1 to (k-1)&1
int a = f[(k-1) &1][i][j];
// Select the KTH item (provided there are enough m and N quotas available)
// Change k-1 to (k-1)&1
int b = (i >= zero && j >= one) ? f[(k-1) &1][i-zero][j-one] + 1 : 0;
f[k&1][i][j] = Math.max(a, b); }}}// Change len-1 to (len-1)&1
return f[(len-1) &1][m][n]; }}Copy the codeclass Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
String str = strs[i];
int zero = 0, one = 0;
for (char c : str.toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][][] f = new int[2][m + 1][n + 1];
for (int k = 1; k <= len; k++) {
int zero = cnt[k - 1] [0], one = cnt[k - 1] [1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
int a = f[(k-1) & 1][i][j];
int b = (i >= zero && j >= one) ? f[(k-1) & 1][i - zero][j - one] + 1 : 0;
f[k&1][i][j] = Math.max(a, b); }}}return f[len&1][m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗n)O(K * M * n)O(K ∗m∗n) for handling state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(m∗n)O(M * n)O(m∗n)
One-dimensional space optimization
In fact, we can continue to do spatial optimization.
Looking at our “state transition equation” again, we find that f[k][I][j]f[k][I][j]f[k][I][j] not only depends on the previous row, but also explicitly depends on states smaller than III and smaller than JJJ.
You can only rely on the “right above” grid in the “previous row”, and the “right above left” grid.
The dependency relationship corresponding to the “naive 01 knapsack problem” is shown as follows:
Therefore, we can directly refer to the “01 backpack space optimization” method: cancel the “item dimension”, and then adjust the traversal order of capacity.
Code:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][] cnt = new int[len][2];
for (int i = 0; i < len; i++) {
int zero = 0, one = 0;
for (char c : strs[i].toCharArray()) {
if (c == '0') zero++;
else one++;
}
cnt[i] = new int[]{zero, one};
}
int[][] f = new int[m + 1][n + 1];
for (int k = 0; k < len; k++) {
int zero = cnt[k][0], one = cnt[k][1];
for (int i = m; i >= zero; i--) {
for (int j = n; j >= one; j--) {
f[i][j] = Math.max(f[i][j], f[i - zero][j - one] + 1); }}}returnf[m][n]; }}Copy the code- Time complexity: Pretreatment of the complexity of the string is O (∑ I = 0 k – 1 len (STRS) [I]) O (\ sum_ {I = 0} ^ {1} k len (STRS) [I]) O (∑ I = 0 k – 1 len (STRS [I])), O(K ∗m∗n)O(K * M * n)O(K ∗m∗n) for handling state transitions. Is: the overall complexity O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS) [I]) O (k * m * n + \ sum_ ^ {I = 0} {1} k len (STRS) [I]) O (k ∗ ∗ m n + ∑ I = 0 k – 1 len (STRS [I]))
- Space complexity: O(m∗n)O(M * n)O(m∗n)
The last
This is the No.474 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 topics on LeetCode, some of which have locks, so we will finish all the topics without locks first.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.