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:
这次作业不是很那，但是一开始有点掉以轻心了，所以写的不是很好，只用了一个指针。
后来发现，必须得用两个指针。具体说下思路。
我觉得这个也有贪婪的思想在里面。
有两个指针，head 和tail.包含了这样一条字符串，里面没有重复。
当tail指向的字符出现在哈希表里面时，此时，head应该指向该字符(key)所对应的index（value）的下一位。并且把前面已经存在的character从哈希表中删除。
然后再配合一些小操作，保证一些细节被满足。
差不多就这样了。
**
总结： 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.jianshu.com/p/c754b343b8e4Minimum Window Substring -
http://www.jianshu.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/
