本文简介
暴力递归
- 尝试
- 把问题转化为规模更小的同类子问题
- 有明确的不需要继续进行递归的条件: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]
- 直接转换为字母
- 数字为0
- 假设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) ) }