求字符串的最大分数

网易没做出来的一题
给定一个全是小写字母的字符串，如果字符串中相邻的两个字母相等或者在字母表中的位置相邻，那么他们两个可以贡献分数。其中’a’贡献1分，’b’贡献2分…..’z’贡献26分。每个字母只能使用一次。
输入 “aca” 输出0 因为相邻的字母没有在字母表中相邻 也不相等
输入 “abb” 输出4 因为ab分值是3，bb分值是4，但是每个字母只能使用一次，因此选择bb

这一题最开始做错就是因为我固执的在探索，两个字符必须相同或者相差1上面了，这直接导致的是：

  1. 对于每一个状态来说，我同时考虑两个元素
  2. 在考虑两个元素的时候，上一次以及下一次状态并不清晰
  3. 定义的DP变成了DP[len][2]使用第二维来表示是否标识

实际上这一题的思路就是，当前这个元素选还是不选，定义DP[i]为0..=i的最大值

  1. 如果选，那么显然就是num[i]-num[i-1]满足条件，因此上一个状态是DP[i-2]即递推过程为：DP[i] = DP[i-2] + num[i]*score + num[i-1]*score
  2. 如果不选，那么就是DP[i] = DP[i-1]

二者比大小就可以了

  1. pub fn signal(num: &mut Vec<char>) -> i32 {
  2.     if num.len() == 0 { return 0; }
  3.     let mut dp = vec![0; num.len() + 1];
  5.     for i in 1..=num.len() {
  6.         match num[i-1] as i32 - num[i] as i32 {
  7.             0|1|-1 => {
  8.                 let temp = num[i-1] as i32 + num[i] as i32 - 2 * ('a' as i32);
  9.                 // 选或者不选两种情况
  10.                 dp[i] = std::cmp::max(dp[i-1], temp + dp[i - 2]);
  11.             }
  12.             (_) => {
  13.                 dp[i] = dp[i-1];
  14.             }
  15.         }
  16.     }
  18.     dp[num.len()]
  19. }

剑指 Offer 46. 把数字翻译成字符串

这一题和网易那题几乎一样，都是对于两个数字同时进行判断
思路还是一样的，就是当前数是否考虑的问题，如果考虑的话，就是需要考虑两个数，那么上一个状态就是dp[n-2]否则就是不考虑（这一题为考虑一个数），那么上一个状态就是dp[n-1]。
image.png
这么一看还是小青蛙跳台阶的改版。
需要注意的就是条件的书写：
image.png
其中比较难想到的就是0..10
看代码以及优化：

  1. // 很丑，因为需要考虑n-2的情况，所以得加1那么i就错开了
  2. // 还容易出错
  3. pub fn translate_num(num: i32) -> i32 {
  4.     // 学一下，string是默认支持UTF8的，因此我们只能使用bytes才能取出每一个u8，
  5.     // 否则是不可预测的，因为chars不一定是啥样
  6.     let ss = num.to_string().bytes().map(|c| c - b'0').collect::<Vec<_>>();
  7.     // 定义dp[i]为ss[i-1]结尾的字符串数量
  8.     let mut dp = vec![0; ss.len() + 1];
  9.     dp[0] = 1;
  10.     dp[1] = 1;
  11.     for i in 1..ss.len() {
  12.         let dup = ss[i-1] * 10 + ss[i];
  13.         if dup >= 10 && dup <= 25 {
  14.             dp[i+1] = dp[i-1] + dp[i];
  15.         }else {
  16.             dp[i+1] = dp[i];
  17.         }
  18.     }
  19.     dp[ss.len()]
  20. }
  21. // 不如直接优化为只考虑前面的两个状态
  22. // 因为我们的dp其实只有两个状态之一
  23. pub fn translate_num(num: i32) -> i32 {
  24.     // 学一下，string是默认支持UTF8的，因此我们只能使用bytes才能取出每一个u8，
  25.     // 否则是不可预测的，因为chars不一定是啥样
  26.     let ss = num.to_string().bytes().map(|c| c - b'0').collect::<Vec<_>>();
  27.     // first就是i-2
  28.     let (mut first, mut second) = (1, 1);
  29.     ss.windows(2).for_each(|n| {
  30.         // 简单一些
  31.         let mut temp = 0;
  32.         if n[0] == 1 || (n[0] == 2 && n[1] <= 5) {
  33.             temp = first + second;
  34.             first = second;
  35.             second = temp;
  36.         } else { 
  37.             // 画图理解，如果当前值不能构成两位数的化，就是dp[i-1]
  38.             // 因此，first代表i-2变为second，而second还是i-1不变
  39.             first = second;
  40.         }
  41.     });
  42.     second
  43. }

剑指 Offer 49. 丑数

这一题的做法比较特殊，其实就是丑数的性质：
丑数只包含2,3,5，那么最关键的就是对于丑数a一定有其下一个丑数b满足：
a = b * (2,3,5)中任何一个
因此天然存在一个递推关系：
对于下一个丑数，满足条件只是因为前面的三个丑数可以递推到他
image.png
核心的问题就是abc究竟在哪？
image.png
不等式最右边很难想到，其实就是对于任何一个前面的丑数a，可以递推到下一个丑数，必然满足大于当前最大的丑数，而且需要大于其上一个丑数a-1乘以同样的值。为什么是同样的值呢？
其实看初始化就行了，初始化全为一，那么就是2,3,5三条线同时再走，找三条线的丑数，这也是更新abc的关键，必须在走向下一步的时候正确更新。
那么既然是这么推过来的，我们通过abc保留状态位置，其实a-1这种情况就不用体现了
OK，可以写代码了：

/// 丑数
pub fn nth_ugly_number(n: i32) -> i32 {
    use std::cmp::min;
    let n = n as usize;
    let (mut a, mut b, mut c) = (0, 0, 0);
    // 定义dp[i]为第i+1个丑数的值
    let mut dp = vec![1; n as usize];
    for i in 1..n {
        let (na, nb, nc) = (dp[a] * 2, dp[b] * 3, dp[c] * 5);
        dp[i] = min(na, min(nb, nc));
        // 注意！！！abc是三条路径，在更新之后不能直接走到i，而是往后走一步，在自己的路径上
        if dp[i] == na { a+=1; }
        if dp[i] == nb { b+=1; }
        if dp[i] == nc { c+=1; }
    }
    dp[n - 1]
}