2022-11-30：小红拿到了一个仅由r、e、d组成的字符串她定义一个字符e为“好e“ : 当且仅当这个e字

moonfdd 的个人博客 / 8 / 0 / 创建于 1年前

2022-11-30：小红拿到了一个仅由r、e、d组成的字符串
她定义一个字符e为”好e” : 当且仅当这个e字符和r、d相邻
例如”reeder”只有一个”好e”，前两个e都不是”好e”，只有第三个e是”好e”
小红每次可以将任意字符修改为任意字符，即三种字符可以相互修改
她希望”好e”的数量尽可能多
小红想知道，自己最少要修改多少次
输入一个只有r、e、d三种字符的字符串
长度 <= 2 * 10^5。
输出最小修改次数。
来自网易。

答案2022-11-30：

动态规划。
奇数，1,3,5,7一定是e。

代码用rust编写。代码如下：

use std::iter::repeat;

fn main() {
    let str = "rrredrr";
    let ans = min_cost(str); //dereder
    println!("ans = {}", ans);
}

fn min_cost(str: &str) -> i32 {
    let n = str.len() as i32;
    if n < 3 {
        return -1;
    }
    let mut arr: Vec<i32> = repeat(0).take(n as usize).collect();
    // d认为是0，e认为是1，r认为是2
    let strc: Vec<char> = str.chars().collect();
    for i in 0..n {
        let cur = strc[i as usize];
        if cur == 'd' {
            arr[i as usize] = 0;
        } else if cur == 'e' {
            arr[i as usize] = 1;
        } else {
            arr[i as usize] = 2;
        }
    }
    // 通过上面的转化，问题变成了：
    // 1的左右，一定要被0和2包围，这个1才是"好1"
    // 请让"好1"的尽量多，返回最少的修改代价
    let mut max_good = 0;
    let mut min_cost = i32::MAX;
    for prepre in 0..3 {
        for pre in 0..3 {
            let mut cost = if arr[0] == prepre { 0 } else { 1 };
            cost += if arr[1] == pre { 0 } else { 1 };
            let cur = process(&mut arr, 2, prepre, pre);
            if cur.max_good > max_good {
                max_good = cur.max_good;
                min_cost = cur.min_cost + cost;
            } else if cur.max_good == max_good {
                min_cost = get_min(min_cost, cur.min_cost + cost);
            }
        }
    }
    return min_cost;
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}
struct Info {
    max_good: i32,
    min_cost: i32,
}

impl Info {
    fn new(a: i32, b: i32) -> Self {
        Self {
            max_good: a,
            min_cost: b,
        }
    }
}
// 暴力递归
// 可以自己改成动态规划
// arr[index-2]位置的数值是prepre
// arr[index-1]位置的数值是pre
// 在这种情况下，请让arr[index...]上的好1尽量多
// 返回:
// 尽量多的"好1"，是多少？
// 得到尽量多的"好1"，最小代价是多少?
fn process(arr: &mut Vec<i32>, index: i32, prepre: i32, pre: i32) -> Info {
    if index == arr.len() as i32 {
        return Info::new(0, 0);
    }
    // 可能性1，arr[index]，变成0
    let mut p1_value = if prepre == 2 && pre == 1 { 1 } else { 0 };
    let mut p1_cost = if arr[index as usize] == 0 { 0 } else { 1 };
    let mut info = process(arr, index + 1, pre, 0);
    p1_value += info.max_good;
    p1_cost += info.min_cost;
    // 可能性2，arr[index]，变成1
    let mut p2_value = 0;
    let mut p2_cost = if arr[index as usize] == 1 { 0 } else { 1 };
    info = process(arr, index + 1, pre, 1);
    p2_value += info.max_good;
    p2_cost += info.min_cost;
    // 可能性3，arr[index]，变成2
    let mut p3_value = if prepre == 0 && pre == 1 { 1 } else { 0 };
    let mut p3_cost = if arr[index as usize] == 2 { 0 } else { 1 };
    info = process(arr, index + 1, pre, 2);
    p3_value += info.max_good;
    p3_cost += info.min_cost;
    // 开始决策，选出三种可能性中的最优解
    let mut max_good = 0;
    let mut min_cost = i32::MAX;
    if p1_value > max_good {
        max_good = p1_value;
        min_cost = p1_cost;
    } else if p1_value == max_good {
        min_cost = get_min(min_cost, p1_cost);
    }
    if p2_value > max_good {
        max_good = p2_value;
        min_cost = p2_cost;
    } else if p2_value == max_good {
        min_cost = get_min(min_cost, p2_cost);
    }
    if p3_value > max_good {
        max_good = p3_value;
        min_cost = p3_cost;
    } else if p3_value == max_good {
        min_cost = get_min(min_cost, p3_cost);
    }
    return Info::new(max_good, min_cost);
}