题目：
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
数据范围: s.length≤40000

解法一：暴力法

两层遍历，在内层使用集合存储，一旦出现重复，就终止内层循环，这样能找到以每一个下标开始的最长子字符串，然后求其最大值即可。

public int lengthOfLongestSubstring (String s) {Integer[] arr = new Integer[s.length()];char[] chars = s.toCharArray();int max = 0;for (int i = 0; i < s.length(); i++) {List list = new ArrayList<>();for (int j = i; j < s.length(); j++) {if (list.contains(chars[j])) {break;} else {list.add(chars[j]);}}arr[i] = list.size();max = Math.max(max, arr[i]);}return max;
}

解法二：滑动窗口+哈希表

滑动窗口：是指在数组、字符串、链表等线性结构上连续的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

哈希表：是一种根据关键码（key）直接访问值（value）的一种数据结构。常用来统计频率、快速检验某个元素是否出现过等。

public static int lengthOfLongestSubstring (String s) {Map map = new HashMap<>();int res=0;for(int left=0,right=0;rightif(map.containsKey(s.charAt(right))){map.put(s.charAt(right),map.get(s.charAt(right))+1);}else{map.put(s.charAt(right),1);}// 移动窗口左边界while(map.get(s.charAt(right))>1){map.put(s.charAt(left),map.get(s.charAt(left++))-1);}res=Math.max(res,right-left+1);}return res;
}

解法三：动态规划+哈希表

动态规划方程：

不重复： dp[i] = dp[i - 1] + 1;

重复： dp[i] = Math.min(dp[i - 1] + 1, i - (map.get(s.charAt(i - 1))));

map的value值是字符串数组下标，使用 i - value 就可以消除本元素的重复，但是如果在本元素与重复元素之间还有其他元素的重复，那么便不能消除。因此需要和 dp[i - 1] + 1取小值。

public static int lengthOfLongestSubstring (String s) {Map map = new HashMap<>();int[] dp = new int[s.length() + 1];int res = 0;for (int i = 1; i <= s.length(); i++) {if (map.containsKey(s.charAt(i - 1))) {dp[i] = Math.min(dp[i - 1] + 1, i - (map.get(s.charAt(i - 1))));} else {dp[i] = dp[i - 1] + 1;}map.put(s.charAt(i - 1), i);res = Math.max(res, dp[i]);}return res;
}

总结：
本题十分经典，涉及到动态规划和滑动窗口两种算法，可作为复习的重点。

涉及数据结构：数组、集合
涉及算法：动态规划、滑动窗口

JZ46 把数字翻译成字符串

题目：
有一种将字母编码成数字的方式：‘a’->1, ‘b->2’, … , ‘z->26’。
现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0

解法一：动态规划

动态规划：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

有多少种解码方式，影响它的不仅有当前位，还有前一位，例如12，可以是1,2和12两种而32只能是3,2。

分析：

字母到数字分别为1-26映射，没有0
输入的数字是字符串，故非常大，超过了long long的表示范围
但凡出现11-19，21-26的就可能出现两种译码结果
求总后的译码结果种类

对于普通数组1-9，译码方式只有一种，但是对于11-19，21-26，译码方式有可选择的两种方案，10和20很特殊，也只有一种，因此我们使用动态规划将三种方案累计。

对于0开头的以及30、40…90等特殊的则无法解码，返回0。

public int solve (String nums) {if (nums.startsWith("0")) {return 0;}for (int i = 1; i < nums.length(); i++) {if (nums.charAt(i) == '0' && nums.charAt(i - 1) != '1' &&nums.charAt(i - 1) != '2') {return 0;}}int[] dp = new int[nums.length() + 1];Arrays.fill(dp, 1);for (int i = 2; i <= nums.length(); i++) {if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') ||(nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' &&nums.charAt(i - 1) < '7')) {dp[i] = dp[i - 2] + dp[i - 1];} else if ((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) == '0') ||(nums.charAt(i - 2) == '2' && nums.charAt(i - 1) == '0' )) {dp[i] = dp[i - 2];} else {dp[i] = dp[i - 1];}}return dp[nums.length()];
}