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

Commit9b1793f

Browse files
committed
159 (1) two pointers window
1 parentaa5fdff commit9b1793f

File tree

4 files changed

+219
-0
lines changed

4 files changed

+219
-0
lines changed
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
***************************************************************************
3+
* Description:
4+
*
5+
* Given a string, find the length of the longest substring T that contains
6+
* at most 2 distinct characters.
7+
*
8+
* For example, Given s = “eceba”, T is "ece" which its length is 3.
9+
*
10+
***************************************************************************
11+
* @tag : Hash Table; Two Pointers; String
12+
* {@link https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ }
13+
*/
14+
package_159_LongestSubstringWithAtMostTwoDistinctCharacters;
15+
16+
/** see test {@link _159_LongestSubstringWithAtMostTwoDistinctCharacters.PracticeTest } */
17+
publicclassPractice {
18+
19+
publicintlengthOfLongestSubstringTwoDistinct(Strings) {
20+
// TODO Auto-generated method stub
21+
return0;
22+
}
23+
24+
}
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag : Hash Table; Two Pointers; String
4+
* @by : Steven Cooks
5+
* @date: Sep 30, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Given a string, find the length of the longest substring T that contains
10+
* at most 2 distinct characters.
11+
*
12+
* For example, Given s = “eceba”, T is "ece" which its length is 3.
13+
*
14+
***************************************************************************
15+
* {@link https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/ }
16+
*/
17+
package_159_LongestSubstringWithAtMostTwoDistinctCharacters;
18+
19+
importjava.util.HashMap;
20+
importjava.util.Map;
21+
22+
/** see test {@link _159_LongestSubstringWithAtMostTwoDistinctCharacters.SolutionTest } */
23+
publicclassSolution {
24+
25+
publicintlengthOfLongestSubstringTwoDistinct(Strings) {
26+
intres =0;
27+
// char, first appearance after the other char in current window
28+
Map<Character,Integer>map =newHashMap<>();
29+
intstart =0;
30+
for (inti =0;i <s.length();i++) {
31+
charch =s.charAt(i);
32+
if (map.size() <2) {
33+
// less than two characters in current window
34+
if (!map.containsKey(ch)) {
35+
map.put(ch,i);
36+
}
37+
}elseif (map.containsKey(ch)) {
38+
// duplicates appears, update index
39+
if (s.charAt(i -1) !=ch) {
40+
map.put(ch,i);
41+
}
42+
}else {
43+
// 3rd character appears
44+
start =map.get(s.charAt(i -1));
45+
map =newHashMap<>();
46+
map.put(s.charAt(i -1),start);
47+
map.put(ch,i);
48+
}
49+
// update global result
50+
if (i -start +1 >res) {
51+
res =i -start +1;
52+
}
53+
}
54+
returnres;
55+
}
56+
57+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package_159_LongestSubstringWithAtMostTwoDistinctCharacters;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassPracticeTest {
12+
13+
/** Test method for {@link _159_LongestSubstringWithAtMostTwoDistinctCharacters.Practice } */
14+
Practicesolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newPractice();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
@Test
30+
publicvoidTest1() {
31+
Strings ="eceba";
32+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
33+
intexpected =3;
34+
assertEquals(expected,actual);
35+
}
36+
37+
@Test
38+
publicvoidTest2() {
39+
Strings ="aaaa";
40+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
41+
intexpected =4;
42+
assertEquals(expected,actual);
43+
}
44+
45+
@Test
46+
publicvoidTest3() {
47+
Strings ="bbaabb";
48+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
49+
intexpected =6;
50+
assertEquals(expected,actual);
51+
}
52+
53+
@Test
54+
publicvoidTest4() {
55+
Strings ="bbaabbc";
56+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
57+
intexpected =6;
58+
assertEquals(expected,actual);
59+
}
60+
61+
@Test
62+
publicvoidTest5() {
63+
Strings ="bbacabbc";
64+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
65+
intexpected =3;
66+
assertEquals(expected,actual);
67+
}
68+
69+
}
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package_159_LongestSubstringWithAtMostTwoDistinctCharacters;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassSolutionTest {
12+
13+
/** Test method for {@link _159_LongestSubstringWithAtMostTwoDistinctCharacters.Solution } */
14+
Solutionsolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newSolution();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
@Test
30+
publicvoidTest1() {
31+
Strings ="eceba";
32+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
33+
intexpected =3;
34+
assertEquals(expected,actual);
35+
}
36+
37+
@Test
38+
publicvoidTest2() {
39+
Strings ="aaaa";
40+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
41+
intexpected =4;
42+
assertEquals(expected,actual);
43+
}
44+
45+
@Test
46+
publicvoidTest3() {
47+
Strings ="bbaabb";
48+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
49+
intexpected =6;
50+
assertEquals(expected,actual);
51+
}
52+
53+
@Test
54+
publicvoidTest4() {
55+
Strings ="bbaabbc";
56+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
57+
intexpected =6;
58+
assertEquals(expected,actual);
59+
}
60+
61+
@Test
62+
publicvoidTest5() {
63+
Strings ="bbacabbc";
64+
intactual =solution.lengthOfLongestSubstringTwoDistinct(s);
65+
intexpected =3;
66+
assertEquals(expected,actual);
67+
}
68+
69+
}

0 commit comments

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