0474.一和零.md

解题关键点

• 很典型的动态规划问题，但是多了一个维度

代码

// 计算 0 和 1 出现的数量
fn count01(s: String) -> (usize, usize) {
    let mut ms = 0;
    let mut ns = 0;
    for i in s.chars() {
        // rust 中，单引号表示字符，是基本类型，一对单引号中只能有一个字符。双引号表示字符串，是 String 类型
        if i == '0' {
            ms += 1;
        } else if i == '1' {
            ns += 1;
        }
    }
    (ms, ns)
}


impl Solution {
    pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
        // 因为数组的长度是 uszie，所以需要转一下类型
        let m = m as usize;
        let n = n as usize;

        // 动态规划，collection[i][j] 表示 i 个 0 和 j 个 1 的最优解
        let mut collection = vec![vec![0; n + 1]; m + 1];
        for s in strs {
            let (c0, c1) = count01(s);
            // 直接跳过不符合条件的项
            if c0 > m || c1 > n {
                continue;
            }
            // 这两个循环需要反转顺序，否则会造成重复累加的问题
            for i in (c0..=m).rev() {
                for j in (c1..=n).rev() {
                    // 背包问题
                    collection[i][j] = collection[i][j].max(collection[i - c0][j - c1] + 1);
                }
            }
        }
        collection[m][n]
    }
}

测试用例

assert_eq!(find_max_form(vec!["10".to_string(),"0001".to_string(),"111001".to_string(),"1".to_string(),"0".to_string()], 5, 3), 4);
assert_eq!(find_max_form(vec!["10".to_string(),"0001".to_string(),"111001".to_string(),"1".to_string(),"0".to_string()], 4, 6), 4);
assert_eq!(find_max_form(vec!["10".to_string(),"1".to_string(),"0".to_string()], 1, 1), 2);
assert_eq!(find_max_form(vec!["10".to_string(),"1".to_string(),"0".to_string()], 2, 1), 2);
assert_eq!(find_max_form(vec!["10".to_string(),"1".to_string(),"0".to_string()], 1, 2), 2);
assert_eq!(find_max_form(vec!["10".to_string(),"1".to_string(),"0".to_string()], 2, 2), 3);