Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit148e371

Browse files
committed
feat: add 003
1 parent6773610 commit148e371

File tree

8 files changed

+180
-54
lines changed

8 files changed

+180
-54
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,7 @@
4747
|#|Title|Tag|
4848
|:-------------|:-------------|:-------------|
4949
|2|[Add Two Numbers][002]|Linked List, Math|
50+
|3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|
5051
|8|[String to Integer (atoi)][008]|Math, String|
5152
|19|[Remove Nth Node From End of List][019]|Linked List, Two Pointers|
5253

@@ -97,6 +98,7 @@
9798
[122]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/122/README.md
9899

99100
[002]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/002/README.md
101+
[003]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/003/README.md
100102
[008]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
101103
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
102104

‎note/003/README.md

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
#[Longest Substring Without Repeating Characters][title]
2+
3+
##Description
4+
5+
Given a string, find the length of the**longest substring** without repeating characters.
6+
7+
**Examples:**
8+
9+
Given`"abcabcbb"`, the answer is`"abc"`, which the length is 3.
10+
11+
Given`"bbbbb"`, the answer is`"b"`, with the length of 1.
12+
13+
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.
14+
15+
**Tags:** Hash Table, Two Pointers, String
16+
17+
18+
##思路
19+
20+
题意是计算不带重复字符的最长子字符串的长度，开辟一个hash数组来存储该字符上次出现的位置，比如`hash[a] = 3`就是代表`a`字符前一次出现的索引在3，遍历该字符串，获取到上次出现的最大索引（只能向前，不能退后），与当前的索引做差获取的就是本次所需长度，从中迭代出最大值就是最终答案。
21+
22+
```java
23+
classSolution {
24+
publicintlengthOfLongestSubstring(Strings) {
25+
int len;
26+
if (s==null|| (len= s.length())==0)return0;
27+
int preP=0, max=0;
28+
int[] hash=newint[128];
29+
for (int i=0; i< len;++i) {
30+
char c= s.charAt(i);
31+
if (hash[c]> preP) {
32+
preP= hash[c];
33+
}
34+
int l= i- preP+1;
35+
hash[c]= i+1;
36+
if (l> max) max= l;
37+
}
38+
return max;
39+
}
40+
}
41+
```
42+
43+
44+
##结语
45+
46+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
47+
48+
49+
50+
[title]:https://leetcode.com/problems/longest-substring-without-repeating-characters
51+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎project/leetcode/.idea/workspace.xml

Lines changed: 69 additions & 47 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.
Binary file not shown.
Binary file not shown.
Binary file not shown.

‎project/leetcode/src/com/blankj/medium/_002/Solution.java

Lines changed: 22 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,6 @@
22

33
importcom.blankj.structure.ListNode;
44

5-
importjava.util.Arrays;
6-
75
/**
86
* <pre>
97
* author: Blankj
@@ -13,15 +11,32 @@
1311
* </pre>
1412
*/
1513
publicclassSolution {
16-
1714
publicListNodeaddTwoNumbers(ListNodel1,ListNodel2) {
18-
15+
ListNodenode =newListNode(0);
16+
ListNoden1 =l1,n2 =l2,t =node;
17+
intsum =0;
18+
while (n1 !=null ||n2 !=null) {
19+
sum /=10;
20+
if (n1 !=null) {
21+
sum +=n1.val;
22+
n1 =n1.next;
23+
}
24+
if (n2 !=null) {
25+
sum +=n2.val;
26+
n2 =n2.next;
27+
}
28+
t.next =newListNode(sum %10);
29+
t =t.next;
30+
}
31+
if (sum /10 !=0)t.next =newListNode(1);
32+
returnnode.next;
1933
}
2034

21-
2235
publicstaticvoidmain(String[]args) {
2336
Solutionsolution =newSolution();
24-
25-
System.out.println(Arrays.toString(solution.addTwoNumbers(nums,target)));
37+
ListNode.print(solution.addTwoNumbers(
38+
ListNode.createTestData("[2,4,3]"),
39+
ListNode.createTestData("[5,6,4]")
40+
));
2641
}
2742
}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
packagecom.blankj.medium._003;
2+
3+
/**
4+
* <pre>
5+
* author: Blankj
6+
* blog : http://blankj.com
7+
* time : 2017/10/11
8+
* desc :
9+
* </pre>
10+
*/
11+
publicclassSolution {
12+
publicintlengthOfLongestSubstring(Strings) {
13+
intlen;
14+
if (s ==null || (len =s.length()) ==0)return0;
15+
intpreP =0,max =0;
16+
int[]hash =newint[128];
17+
for (inti =0;i <len; ++i) {
18+
charc =s.charAt(i);
19+
if (hash[c] >preP) {
20+
preP =hash[c];
21+
}
22+
intl =i -preP +1;
23+
hash[c] =i +1;
24+
if (l >max)max =l;
25+
}
26+
returnmax;
27+
}
28+
29+
publicstaticvoidmain(String[]args) {
30+
Solutionsolution =newSolution();
31+
System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));
32+
System.out.println(solution.lengthOfLongestSubstring("bbbbb"));
33+
System.out.println(solution.lengthOfLongestSubstring("pwwkew"));
34+
System.out.println(solution.lengthOfLongestSubstring("Abcabcbb"));
35+
}
36+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp