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

Commitaed3eab

Browse files
add a solution for 424
1 parent3f36ab4 commitaed3eab

File tree

2 files changed

+54
-13
lines changed

2 files changed

+54
-13
lines changed

‎src/main/java/com/fishercoder/solutions/_424.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,8 @@
11
packagecom.fishercoder.solutions;
22

3+
importjava.util.HashSet;
4+
importjava.util.Set;
5+
36
publicclass_424 {
47

58
publicstaticclassSolution1 {
@@ -21,4 +24,46 @@ public int characterReplacement(String s, int k) {
2124
returnmaxLength;
2225
}
2326
}
27+
28+
publicstaticclassSolution2 {
29+
/**
30+
* My original solution using Sliding Window technique:
31+
* I try to use each character as the possible candidate to find all solutions and compare.
32+
*/
33+
publicintcharacterReplacement(Strings,intk) {
34+
Set<Character>set =newHashSet<>();
35+
for (charc :s.toCharArray()) {
36+
set.add(c);
37+
}
38+
intans =0;
39+
for (charc :set) {
40+
ans =Math.max(ans,slidingWindow(c,s,k));
41+
}
42+
returnans;
43+
}
44+
45+
privateintslidingWindow(charc,Strings,intk) {
46+
intleft =0;
47+
intright =0;
48+
intans =0;
49+
while (right <s.length()) {
50+
if (s.charAt(right) !=c) {
51+
if (k >0) {
52+
k--;
53+
right++;
54+
}else {
55+
while (left <s.length() &&s.charAt(left) ==c) {
56+
left++;
57+
}
58+
left++;
59+
k++;
60+
}
61+
}else {
62+
right++;
63+
}
64+
ans =Math.max(ans,right -left);
65+
}
66+
returnans;
67+
}
68+
}
2469
}

‎src/test/java/com/fishercoder/_424Test.java

Lines changed: 9 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -8,67 +8,63 @@
88

99
publicclass_424Test {
1010
privatestatic_424.Solution1solution1;
11+
privatestatic_424.Solution2solution2;
1112
privatestaticStrings;
1213
privatestaticintk;
13-
privatestaticintactual;
1414
privatestaticintexpected;
1515

1616
@BeforeClass
1717
publicstaticvoidsetup() {
1818
solution1 =new_424.Solution1();
19+
solution2 =new_424.Solution2();
1920
}
2021

2122
@Test
2223
publicvoidtest1() {
2324
s ="ABAB";
2425
k =2;
25-
actual =solution1.characterReplacement(s,k);
2626
expected =4;
27-
assertEquals(expected,actual);
27+
assertEquals(expected,solution1.characterReplacement(s,k));
28+
assertEquals(expected,solution2.characterReplacement(s,k));
2829
}
2930

3031
@Test
3132
publicvoidtest2() {
3233
s ="AABABBA";
3334
k =1;
34-
actual =solution1.characterReplacement(s,k);
3535
expected =4;
36-
assertEquals(expected,actual);
36+
assertEquals(expected,solution1.characterReplacement(s,k));
3737
}
3838

3939
@Test
4040
publicvoidtest3() {
4141
s ="AAAA";
4242
k =2;
43-
actual =solution1.characterReplacement(s,k);
4443
expected =4;
45-
assertEquals(expected,actual);
44+
assertEquals(expected,solution1.characterReplacement(s,k));
4645
}
4746

4847
@Test
4948
publicvoidtest4() {
5049
s ="AAAB";
5150
k =0;
52-
actual =solution1.characterReplacement(s,k);
5351
expected =3;
54-
assertEquals(expected,actual);
52+
assertEquals(expected,solution1.characterReplacement(s,k));
5553
}
5654

5755
@Test
5856
publicvoidtest5() {
5957
s ="AABA";
6058
k =0;
61-
actual =solution1.characterReplacement(s,k);
6259
expected =2;
63-
assertEquals(expected,actual);
60+
assertEquals(expected,solution1.characterReplacement(s,k));
6461
}
6562

6663
@Test
6764
publicvoidtest6() {
6865
s ="ABBB";
6966
k =2;
70-
actual =solution1.characterReplacement(s,k);
7167
expected =4;
72-
assertEquals(expected,actual);
68+
assertEquals(expected,solution1.characterReplacement(s,k));
7369
}
7470
}

0 commit comments

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