把数字翻译成字符串

medium 原题连接：把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例：

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

限制：

  • 0 <= num < 231

解题思路

从尾到头进行动态规划，如果最后两位符合26以内的值F(N) = F(N-1)+F(N-2) 否则就只有 F(N) = F(N-1)

将0-25的数字编码为a-z的字符，既可以尝试单个数字去编码，又可以判断是否满足一定条件使得两个数字作为一个参数去编码

要求遍历完整个数字后看看有多少种编码手段。

初见题目的时候，我就觉得很像之前的青蛙跳台阶问题，可以选择一步步走，又或者一次跳两格,不过这一题多了一点条件

请思考这么一个：最后一个数进行编码时，有几种可能？

\1. 单独编码:如果最后两位>25，那最后一位就只能自己编码，所以F(N) = F(N-1)

\2. 联合编码:如果最后两位<26，且最后两位可以分开编码-F(N-1)，也可以一起编码-F(N-2)即F(N) = F(N-1)+F(N-2)

注意：因为0也是被允许的数字，但是0不可作为十位数（没有意义）所以在0作为十位时，只能返回F(N) = F(N-1)

ps：青蛙跳台阶：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

ps2：挂了个自己的题解： Java-动态规划 - 把数字翻译成字符串 - 力扣（LeetCode）

Java代码

class Solution {
    public int translateNum(int num) {
        if(num < 10) return 1;
        if(num % 100 < 26)
            if(num%100 != num%10)
                return translateNum(num/10) + translateNum(num/100);
        return translateNum(num/10);
    }
}

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

medium 原题连接：最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

限制：

  • s.length <= 40000

解题思路

不含重复字符的子串，解决这个问题可以将情况分为以下几类：

  1. 这个字符没有重复过：子串长度+1
  2. 字符重复了，且在当前子串中：子串长度设置为当前重复字符间这一部分加后重复子串，如：abcdb，检查到最后一个b时，原本子串为abcd，这时因为b重复了，且在当前子串中重复，所以将子串调整为cdb，即两个b中间的部分加上后一个b
  3. 字符重复了，但是不在当前子串：子串长度+1，如abbcda，检查到最后的a时，子串应该是bcd，尽管a在整个子符中重复了，对于子串而言还是没重复的

Java代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] str = s.toCharArray();
        HashMap<Character,Integer> lastSameStr = new HashMap<>();
        int ans = 0, mid = 0;
        for(int i=0; i<str.length; i++) {
            if(lastSameStr.get(str[i]) == null) {
                mid++;
            }else {
                if(mid >= i-lastSameStr.get(str[i]))
                    mid = i - lastSameStr.get(str[i]);
                else
                    mid++;
            }
            lastSameStr.put(str[i],i);
            ans = Math.max(ans,mid);
        }
        return ans;
    }
}