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

题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
题目链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

思路

这道题类似于跳台阶，一次可以跳一级，也可以跳两级，只是在这道题中跳两级需要判断是否在0~25的范围内。
动态规划，新建一个dp数组，维护该数字各长度的翻译方法数量；
动态转移方程为：若   和   组成的两位数字可以被翻译，则 ；否则  ，初始状态。
这里使用了String类自带的compareTo() 方法判断截取的数字字符串是否在0~25的范围内，相等返回0，小于则返回一个小于 0 的值，大于则返回一个大于 0 的值。

实现代码 

class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int length = str.length();
        int[] dp = new int[length+1];
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= length; i++){
            String s = str.substring(i - 2, i);
            if(s.compareTo("10") >= 0 && s.compareTo("25") <= 0){
                dp[i] = dp[i-1] + dp[i-2];
            }else{
                dp[i] = dp[i-1];
            }
        }
        return dp[length];
    }
}

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

题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 
输入: "abcabcbb" 输出: 3  解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。

思路

滑动窗口，用一个HashMap 记录出现过的字符及其对应的下标，遍历字符串，如果当前字符已出现过，就将左指针移到重复字符的后一位，但为避免左指针往前移，导致长度计算出错，采用的解决方案是从哈希表中取出重复字符的下标+1，将其与当前的左指针进行比较取两者的最大值。

实现代码 

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0;
        int left = 0;
        int right = 0;
        while(right < s.length()){
            char c = s.charAt(right); //获得当前字符
            if(map.containsKey(c)){ //判断是否已存在于滑动窗口中
                //若存在，需将left移到重复字符的后一位
                //取出字符对应的下标+1与当前left比较，取最大值，避免left往前移
                left = Math.max(left, map.get(c) + 1);
            }
            //不存在就入哈希，已存在的value会被覆盖为新值
            map.put(c, right);
            //更新当前的最长子串
            maxLen = Math.max(maxLen, right - left + 1);
            right++; //移动右指针扩大窗口
        }
        return maxLen;
    }
}