lintcode、最長重複文字のないサブ列
3908 ワード
文字列を指定します.重複文字のない長男文字列を見つけてください.例として、例えば、「abcabcbb」において、重複文字のない最長文字列は「abc」であり、その長さは3である.場合、「bbbb」は、重複文字のない最長子文字列が「b」であり、長さが1である.
acの下のリンクの中で説明するのがとてもはっきりしていないで、参考にすることができます
http://blog.csdn.net/imabluefish/article/details/38662827 ブラシにacがないのか、map.get(ch)>=startで間違っているのか.mapストレージ文字と位置を確立すると、重複した文字に遭遇すると、最初に重複した文字が現れた次の文字に戻って再カウントを開始する.
考え方2:mapを再構築するたびに、開始インデックスを1つのstartで記録することを避けるために.長さをlenで記録し、文字列を巡る過程でmapに文字が含まれているかどうかを判断するたびに、含まれている文字がstartの後に初めて現れた場合(startはますます大きくなるに違いないから)、startを繰り返し現れる文字の次の文字にリセットし、そのときのlenを計算し、最大かどうかを判断する.
acの下のリンクの中で説明するのがとてもはっきりしていないで、参考にすることができます
http://blog.csdn.net/imabluefish/article/details/38662827 ブラシにacがないのか、map.get(ch)>=startで間違っているのか.mapストレージ文字と位置を確立すると、重複した文字に遭遇すると、最初に重複した文字が現れた次の文字に戻って再カウントを開始する.
public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
HashMap map = new HashMap();
int res = 0;
int len = 0;
for(int i = 0; i < s.length(); i++){
if(map.containsKey(s.charAt(i))){
i = map.get(s.charAt(i));
map.clear();
len = 0;
continue;
}
len++;
map.put(s.charAt(i),i);
res = Math.max(res,len);
}
return res;
}
}
考え方2:mapを再構築するたびに、開始インデックスを1つのstartで記録することを避けるために.長さをlenで記録し、文字列を巡る過程でmapに文字が含まれているかどうかを判断するたびに、含まれている文字がstartの後に初めて現れた場合(startはますます大きくなるに違いないから)、startを繰り返し現れる文字の次の文字にリセットし、そのときのlenを計算し、最大かどうかを判断する.
public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
HashMap map = new HashMap();
int res = 0;
int len = 0;
int start = 0;
for(int i = 0; i < s.length(); i++){
if(map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) >= start){
start = map.get(s.charAt(i)) + 1;
}
len = i - start + 1;
map.put(s.charAt(i),i);
res = Math.max(res,len);
}
return res;
}
}