You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
rust_basic_code/md_file/2379. 得到 K 个黑块的最少涂色次数.md

2.7 KiB

2379. 得到 K 个黑块的最少涂色次数

description:

给你一个正整数数组 nums,请你移除 最短子数组(可以为空),使得剩余元素的和能被 p 整除。 不允许 将整个数组都移除。请你返回你需要移除的最短子数组的长度,如果无法满足题目要求,返回 -1 。子数组定义为原数组中连续的一组元素。

代码: minimum_recolors为正确写法。

fn main() {
    let blocks = String::from("WWBWWBBWBW");
    let nums = 7usize;

    let res = minimum_recolors(&blocks, nums);
    println!("minimum_recolors {}", res);
    let res = minimum_recolors1(&blocks, nums);
    println!("minimum_recolors1 {}", res);
}

// 错误代码
fn minimum_recolors1(blocks: &str, nums: usize) -> usize{
    let mut l = 0usize;
    let mut r = 0usize;
    let mut cnt = 0usize;
    let mut blocks = blocks.chars();  // Chars() 为一个字符串类型的迭代器,不是字符数组。没有len方法、
    // blocks.len()  -- no method named `len` found for struct `Chars` in the current scope
    blocks.as_str().len(); //这样可以。
    println!("blocks.len() is {}", blocks.as_str().len());
    while r < nums {
        cnt += if blocks.next() == Some('W')  {1} else { 0 };
        r += 1;
    }
    println!("blocks.len() is {}", blocks.as_str().len());
    // 使用向量 此时的blocks为字符串迭代器。 如果为字符串应该写成 blocks.chars().collect::<Vec<char>>();
    let mut blocks = blocks.collect::<Vec<char>>();

    // 当使用一个 usize 类型的值作为数组索引时,需要将它转换为整数类型,例如 i32,可以使用 as 关键字进行强制类型转换:

    let mut res= cnt;

    while r < blocks.len() {
        print!("不会执行,因为迭代器只剩下(WBW)三个元素!故而此时向量长度为3,小于r");
        cnt += if blocks[r] == 'W'  {1} else { 0 };
        cnt -= if blocks[l] == 'W'  {1} else { 0 };
        res = res.min(cnt);
        l += 1;
        r += 1;
    }
    // 而此时已经失去了原始blocks, 可知此种情况应该在一开始转为向量!除了遍历,别用什么迭代器。
    res
}

pub fn minimum_recolors(blocks: &str, k: usize) -> usize {
    let blocks_chars = blocks.chars().collect::<Vec<char>>();
    let mut l = 0usize;
    let mut r = 0usize;
    let mut cnt = 0usize;
    while r < k {
        if blocks_chars[r] == 'W' {
            cnt += 1;
        }
        r += 1;
    }
    let mut res = cnt;

    while r < blocks_chars.len() {
        if blocks_chars[r] == 'W' {
            cnt += 1;
        }
        if blocks_chars[l] == 'W' {
            cnt -= 1;
        }
        res = res.min(cnt);
        l += 1;
        r += 1;
    }
    res
}