摘要：用來記錄字母出現(xiàn)的可以快速查找出字母是否重復(fù)出現(xiàn)，并定位到它出現(xiàn)的位置，方便做刪除之前字母的操作。然后把這個(gè)字母的更新。
題目：
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
解法1：
核心思想是當(dāng)發(fā)現(xiàn)有重復(fù)的字母，就把重復(fù)字母第一次出現(xiàn)位置以及之前的字母都刪掉，這樣就保證剩下的string中沒有重復(fù)的字母了。用hashmap來記錄字母出現(xiàn)的index,可以快速查找出字母是否重復(fù)出現(xiàn)，并定位到它出現(xiàn)的位置，方便做刪除之前字母的操作。
代碼1：
public void deletePrevious(Map map, String s, int start, int end) {
for (int i = start; i <= end; i++) {
char c = s.charAt(i);
map.remove(c);
}
}
public int lengthOfLongestSubstring(String s) {
int result = 0;
if (s.length() == 0) return result;
Map map = new HashMap();
int start = 0;
int len = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
int index = map.get(c);
//把從重復(fù)的index開始，前面所有的數(shù)都在map里去掉，并記下新的start
deletePrevious(map, s, start, index);
start = index + 1;
map.put(c, i);
//刪掉后的len是當(dāng)前i減去刪掉數(shù)的index
len = i - index;
} else {
map.put(c, i);
len++;
}
result = Math.max(result, len);
}
return result;
}
又看了其他人的解法，感覺有很好的思路就拷貝過來了。
解法2:
我用j, i來記錄最后不重復(fù)string的開始點(diǎn)和當(dāng)前點(diǎn)，當(dāng)我找到一個(gè)重復(fù)出現(xiàn)的字母，我判斷一下j是否要更新，如果這個(gè)重復(fù)字母出現(xiàn)第一次的位置比j小，那么說明至少?gòu)膉開始才能保證沒有重復(fù)字母；如果這個(gè)重復(fù)字母出現(xiàn)第一次的位置比j大，那么將j更新到這個(gè)位置的后一位，作為新的開始點(diǎn)。然后把這個(gè)字母的index更新。這里省去了我上面說的刪除之前所以map中的值，因?yàn)榫退愠霈F(xiàn)了重復(fù)的值，我也還是從j開始算，并且我更新這個(gè)值的新index后，原來那個(gè)就相當(dāng)于自動(dòng)刪除了。
代碼2:
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap map = new HashMap();
int max=0;
for (int i = 0, j = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
//這里j是記錄滿足條件的start，當(dāng)發(fā)現(xiàn)有重復(fù)的數(shù)時(shí)，應(yīng)從重復(fù)數(shù)第一次出現(xiàn)的位置向后一位開始記，但同時(shí)要保持從j開始向后所有數(shù)都不重復(fù)，就得取最大值
j = Math.max(j, map.get(s.charAt(i)) + 1);
}
//更新重復(fù)出現(xiàn)數(shù)的index值
map.put(s.charAt(i), i);
max = Math.max(max, i - j + 1);
}
return max;
}
解法3:
這里思路跟解法2一樣，只不過他巧妙利用cache，因?yàn)樗宰帜妇?27個(gè)，那個(gè)我用256的空間就肯定能記錄所有的點(diǎn)。比如就算最極端，cache(0)是‘a(chǎn)"，一直到cache(255)才雙出現(xiàn)‘a(chǎn)’，我的空間也是夠的。
public int lengthOfLongestSubstring(String s) {
int result = 0;
int[] cache = new int[256];
for (int i = 0, j = 0; i < s.length(); i++) {
j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
//注意因?yàn)閟tirng的index是從0開始，但是我們判斷這個(gè)字母是否在cache里也用這個(gè)字母的cache值是否來判斷，所以我們把每個(gè)存進(jìn)cache里的字母的index + 1, 這樣存的就是它的下一個(gè)數(shù)的index。
cache[s.charAt(i)] = i + 1;
result = Math.max(result, i - j + 1);
}
return result;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64862.html
