Rust·算法基础·暴力递归

 

本文简介

本文简介

暴力递归

  • 尝试
    • 把问题转化为规模更小的同类子问题
    • 有明确的不需要继续进行递归的条件:base case
    • 有得到子问题结果之后的决策过程
    • 不记录每个子问题的解

汉诺塔问题

在一根柱子上从下往上按照大小顺序摞着多个黄金圆盘,把圆盘从下面开始按大小顺序重新摆放在另一根柱子上

fn hanoi(n: usize) {
    hanoi_recurrence(n, "A", "C", "B");
}

fn hanoi_recurrence(n: usize, from:&str, to:&str, mid: &str) {
    if n == 0 {return;}

    hanoi_recurrence(n-1, from, mid, to);
    println!("盘[{}]: {} -> {}", n, from, to);
    hanoi_recurrence(n-1, mid, to, from);
}

打印字符串的子序列

  • 打印一个字符串的所有子序列,包括空串
  • 算法
    • 从左到右依次对每一个字符尝试有和无两种情况
    • 当到达最后一个字符之外,打印这整个字符串
  • 算法实现

    pub fn print_all_sub_sequence(s: &str) {
      let mut ss: Vec<char> = s.to_string().chars().collect();
      sub_sequence(&mut ss, 0);
      println!("");
    }
    
    fn sub_sequence(s: &mut Vec<char>, idx: usize) {
        if idx == s.len() {
            let mut x = String::from_iter(s.iter());
            x.retain(|c| c != ' ');
            print!("{:?}, ", x);
            return;
        }
    
        sub_sequence(s, idx+1);
        let tmp = s[idx];
        s[idx] = ' ';
        sub_sequence(s, idx+1);
        s[idx] = tmp;
    }
    

获取一个字符串的全排列

  • 算法
    • 从左到右全排列
  • 算法实现

    fn permutation(s: &mut Vec<char>, idx: usize, res: &mut Vec<String>) {
      if idx == s.len() {
          res.push(String::from_iter(s.iter()));
          return;
      }
    
      let mut visit = vec![false;26];
      for j in idx..s.len() {
          if  !visit[s[j] as usize - 'a' as usize] {
              visit[s[j] as usize - 'a' as usize] = true;
              s.swap(idx, j);
              permutation(s, idx+1, res);
              s.swap(idx, j);
          }
      }
    }
    
    pub fn print_permutation(s: &str) {
        println!("字符串: {}的全排序为:", s);
        let mut res: Vec<String> = vec![];
        let mut s:Vec<char> = s.to_string().chars().collect();
        permutation(&mut s, 0, &mut res);
        println!("{:?}", res);
    }
    

纸牌

  • 题目
    • 给定一个整形数组,代表数值不同的纸牌排成一条线
    • 玩家A、B依次拿走纸牌
    • 规定A先拿B后拿
    • 每个玩家只能拿走最左或最右的牌
    • 假定A、B都绝顶聪明
    • 返回最后获胜者的分数
  • 举例
    • arr = [1, 2, 100, 3]
    • A先拿1 -> B拿2 -> A拿100
  • 算法实现

    fn frist(card: &Vec<u32>, l: usize, r:usize) -> u32 {
        if l == r { return card[l]; }
    
        std::cmp::max(
            frist(card, l, l) + second(card, l+1, r), 
            frist(card, r, r) + second(card, l, r-1))
    }
    
    fn second(card: &Vec<u32>, l:usize, r:usize) -> u32 {
        if l==r { return 0; }
    
        std::cmp::min(
            frist(card, l+1, r),
            frist(card, l, r-1))
    }
    

逆序一个栈

  • 不能用额外数据结构,用递归实现
  • 实现一个取出栈底元素的函数stack_bottom
  • 算法实现

    fn stack_bottom(stack: &mut Vec<i32>)-> i32 {
        let res = stack.pop().unwrap();
        if stack.is_empty() {
            return res;
        }else{
            let last = stack_bottom(stack);
            stack.push(res);
            return last;
        }
    }
    
    fn reverse_stack(stack: &mut Vec<i32>) {
        if stack.is_empty() {return;}
        let bottom = stack_bottom(stack);
        reverse_stack(stack);
        stack.push(bottom);
    }
    

转换字符

  • 题目
    • 规则
      • 1:A, 2:B, ...
      • 1个数字对应一个字符
      • 111可以是AAA, KA, AK
    • 给定一个数字字符串,返回多种结果
  • 算法
    • 从左到右依次转换
    • 对遇到的数字进行拆分
      • 数字为0
        • 不能转换,有问题
      • 数字为1
        • 可以是A
        • 可以和后面的数字组合
      • 数字为2
        • 可以是B
        • 后面数字是[0:6],可以组合
        • 后面数字是[7:9],不可以组合
      • 数字为[3:9]
        • 直接转换为字母
    • 假设trans_methods(str, i)表示
      • str[..i-1]的转换已经完成
      • str[i..]有多少种转换
  • 算法实现

    // [0..i-1]如何转化已经做过决定
    // [i..]有多少种转化结果
    fn trans_methods(s: &Vec<char>, i:usize) ->i32 {
        let slen = s.len();
        if slen == i {return 1;}
        match s[i] {
            // 进入无效状态,虽然a[..i-1]转化有效,所以整体是0种
          '0' => return 0,
          '1' => {
              // s[i]独立转化,后续a[i+1..]有多少种
              let mut res = trans_methods(s, i+1);
              // s[i]和s[i+1]组合,后续a[i+2..]有多少种
                if i+1 < slen { res += trans_methods(s, i+2); }
                return res;
            },
            '2' => {
                let mut res = trans_methods(s, i+1);
                if i+1 < slen && '0' <= s[i+1] && s[i+1] <= '6' {
                    res += trans_methods(s, i+2);
                }
                return res;
            }
            _ => { return trans_methods(s, i+1); }
        }
    }
    

装袋

  • 给定长度为N的数组:weights, values
  • 给定正数bag,表示载重bag的袋子
  • 问能装下最多的价值是多少?
  • 算法实现

    fn max_value(weight: &mut Vec<i32>, values: &mut Vec<i32>,
              i: usize, alread_weight: i32, bag: i32) -> i32 {
        // 如果超重了,直接返回0
        if alread_weight > bag {return 0;}
        // 没货了,要的货超过了货物数目
        if i == weight.len() {return 0;}
        std::cmp::max(
            // 不选第i件
            max_value(weight, values, i+1, alread_weight, bag),
            // 选第i件
            values[i] + max_value(weight, values, i+1, alread_weight+weight[i], bag)
        )
    }