46. 把数字翻译成字符串

思路

每个数字都有两种翻译情况，一种是和前一位数字一起被翻译，一种是单独被翻译。
状态定义：dp[i]表示以xi结尾的数字的翻译方案数量；
状态转移方程：
f(i) = f(i - 2) + f(i - 1), xi-1xi可以被翻译
f(i) = f(i - 1)，xi-1xi不可被翻译
初始化：dp[0] = dp[1] = 1
返回值：dp[n]

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}

48. 最长不含重复字符的子字符串

思路

状态定义：dp[i]表示以字符s[i]结尾的满足条件的子串长度；
状态转移方程：
固定右边界 j ，设字符 s[j]左边距离最近的相同字符为s[i] ，即 s[i] = s[j]。

1. i < 0, s[j]左边没有相同字符， dp[j] = dp[j - 1] + 1
2. dp[j - 1] < j - i， s[i] 在子字符串dp[j - 1]区间之外， 则dp[j] = dp[j - 1] + 1;
3. dp[j - 1] >= j - i， s[i] 在子字符串dp[j - 1]区间之内， 则dp[j] = j - i;
   返回值：max(dp)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}