Question:
My code:
import java.util.HashMap;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
int max = 1;
int length = 0;
HashMap<Character, Integer> c = new HashMap<Character, Integer>();
int tail = 0;
int head = 0;
while (tail < s.length()) {
if (!c.containsKey(s.charAt(tail))) {
length++;
c.put(s.charAt(tail), tail);
tail++;
if (max < length)
max = length;
}
else {
int tempHead = head;
head = c.get(s.charAt(tail));
length = length - (head + 1 - tempHead);
for (int i = tempHead; i < head; i++)
c.remove(s.charAt(i));
c.put(s.charAt(head), tail);
head++;
tail++;
length++;
}
}
return max;
}
public static void main(String[] args) {
String s = "dvdf";
Solution test = new Solution();
System.out.println(test.lengthOfLongestSubstring(s));
}
}
My test result:
這次作業(yè)不是很那陪每，但是一開始有點掉以輕心了躏筏，所以寫的不是很好哀峻，只用了一個指針。
后來發(fā)現适袜，必須得用兩個指針讲仰。具體說下思路。
我覺得這個也有貪婪的思想在里面痪蝇。
有兩個指針，head 和tail.包含了這樣一條字符串冕房，里面沒有重復躏啰。
當tail指向的字符出現在哈希表里面時，此時耙册，head應該指向該字符(key)所對應的index（value）的下一位给僵。并且把前面已經存在的character從哈希表中刪除。
然后再配合一些小操作详拙，保證一些細節(jié)被滿足帝际。
差不多就這樣了。
**
總結： HashMap HashSet
貪心的想法饶辙。即保證每一步都奔著更大去的蹲诀，那些更大也都小于最大的情況，就可以直接排除了弃揽。
**
女朋友的父親到底是怎么樣的一個人脯爪？
如果真的是因為那樣的小事而為難自己的女兒则北，那這人的心胸該有多么狹窄啊。我一直覺得我的父親度量小痕慢，但那都是可以忍受的尚揣，正常的。但是如果是那樣狹窄的心胸掖举，我是不能忍受的快骗，也絕對不會和這樣的人的女兒最后在一起。再看吧塔次。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
int max = 0;
int start = 0;
HashMap<Character, Integer> tracker = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (tracker.containsKey(curr) && tracker.get(curr) > 0) { // if current map contains such character
while (tracker.get(curr) > 0) {
char pre = s.charAt(start);
tracker.put(pre, tracker.get(pre) - 1);
start++;
}
tracker.put(curr, 1);
max = Math.max(max, i - start + 1);
}
else {
tracker.put(curr, 1);
max = Math.max(max, i - start + 1);
}
}
return max;
}
}
其實就是sliding window 的思想方篮。
Substring with Concatenation of All Words -
http://www.reibang.com/p/c754b343b8e4Minimum Window Substring -
http://www.reibang.com/p/d4745ac61b4f
維持一個window，進行操作俺叭。
HashMap 可以改成用HashSet 來做恭取。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int i = 0;
int max = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
while (i < s.length()) {
char curr = s.charAt(i);
if (!map.containsKey(curr)) {
map.put(curr, i);
i++;
max = Math.max(max, map.size());
}
else {
int pre = map.get(curr);
i = pre + 1;
map.clear();
}
}
return max;
}
}
這是我自己的code，看起來還是很低效冗雜的熄守。
這道題目考的其實是 sliding window,看了參考：
My code：
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int i = 0;
int j = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int maxLen = 0;
for (; i < s.length(); i++) {
char curr = s.charAt(i);
if (map.containsKey(curr)) {
j = Math.max(j, map.get(curr) + 1);
}
maxLen = Math.max(maxLen, i - j + 1);
map.put(curr, i);
}
return maxLen;
}
}
這里的蜈垮，就簡潔多了。下面介紹下裕照， j = Math.max(j, map.get(curr) + 1) 這個操作
當 i 的character重復出現時攒发，這時候需要更新窗口。
如果晋南，i這個character惠猿，在j之前出現，那么负间，對當前的窗口沒影響偶妖，仍然沒有重復。不更新j
如果政溃，在j之后出現趾访，那么，當前窗口就存在重復董虱，需要更新 j
j = i + 1
差不多就這個思路扼鞋。
reference:
https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation
然后這篇文章寫得也不錯：
https://leetcode.com/articles/longest-substring-without-repeating-characters/
