【020-week4】第二周总结

[lcfgrn]

写了几个简单的递归，递归的边界条件以及退出条件，在写之前需要好好考虑清楚。

最长子字符串的算法题总结
题目
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
我的解法：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int maxCount = 0;
int count = 0;
char[] chars = s.toCharArray();
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < chars.length; i++) {
if (map.containsKey(chars[i])) {
//找到相同字符后，将找到的上一个值的索引值赋值给i，从i+1开始，重新计算子字符串
i = map.get(chars[i]);
map.clear();
maxCount = Math.max(maxCount, count);
count = 0;
} else {
count++;
map.put(chars[i], i);
}
}
maxCount = Math.max(maxCount, count);
return maxCount;
}
}
最优解法：
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
//这里使用Math.max比较，如果在数组index中找到重复字符，则应为这个索引值，
//如果没找到，则应该为上一次找到重复字符的索引值
i = Math.max(index[s.charAt(j)],i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
总体印象：
1.最优解法的实现很优雅，但比较难懂；
2.特别是这里的Math.max方法很是难懂