Day10_剑指Offer

package com.sorrymaker.day3410;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 最长不含重复字符的子字符串
 *
 * @Author nextGame
 * @Date 2021/8/22 16:59
 * @Version 1.0
 */
public class LengthOfLongestSubstring {

    @Test
    public void test() {
        System.out.println(lengthOfLongestSubstring("abcabcwertybb"));
    }

    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            // 获取索引 i
            //getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
            int i = dic.getOrDefault(s.charAt(j), -1);
            // 更新哈希表
            dic.put(s.charAt(j), j);
            // dp[j - 1] -> dp[j]
            //第一次存入的哈希表里面的时候，j-i始终会大于tmp。
            // 但是第二次，当i不再是默认值的时候，j-i没办法大于tmp的时候，说明tmp已经是最大值了
            tmp = tmp < j - i ? tmp + 1 : j - i;
            // max(dp[j - 1], dp[j])
            res = Math.max(res, tmp);
        }
        return res;
    }
}

package com.sorrymaker.day3410;

import org.junit.Test;

/**
 * @Author nextGame
 * @Date 2021/8/21 21:54
 * @Version 1.0
 */
public class TranslateNum {

    @Test
    public void test() {
        int num = 12258;
        System.out.println(translateNum(num));
    }

    public int translateNum(int num) {
        String s = String.valueOf(num);
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            //截取两位，看看是否是在   [10,25]的范围内，是的话，这两位数字是可以被当作一个整体来翻译
            String temp = s.substring(i - 2, i);
            //comparTo()，true的话会返回1，否则会返回-1
            if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }

        //返回到最后一位数字的dp。
        return dp[s.length()];

    }
}