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

Commitc6404c5

Browse files
add 2156
1 parent0aa304f commitc6404c5

File tree

3 files changed

+107
-0
lines changed

3 files changed

+107
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|2156|[Find Substring With Given Hash Value](https://leetcode.com/problems/find-substring-with-given-hash-value/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2156.java)||Medium||
1112
|2155|[All Divisions With the Highest Score of a Binary Array](https://leetcode.com/problems/all-divisions-with-the-highest-score-of-a-binary-array/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2155.java)||Medium||
1213
|2154|[Keep Multiplying Found Values by Two](https://leetcode.com/problems/keep-multiplying-found-values-by-two/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2154.java)||Easy||
1314
|2150|[Find All Lonely Numbers in the Array](https://leetcode.com/problems/find-all-lonely-numbers-in-the-array/)|[Java](../master/src/main/java/com/fishercoder/solutions/_2150.java)||Medium||
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
packagecom.fishercoder.solutions;
2+
3+
publicclass_2156 {
4+
publicstaticclassSolution1 {
5+
/**
6+
* Credit: https://leetcode.com/problems/find-substring-with-given-hash-value/discuss/1730100/Java-rolling-hash(back-to-front)/1242659
7+
* <p>
8+
* We start from the right side and compute rolling hash when moving the window of size k towards the left.
9+
*/
10+
publicStringsubStrHash(Strings,intpower,intmodulo,intk,inthashValue) {
11+
longweight =1;
12+
for (intj =0;j <k -1;j++) {
13+
// calculate the weight which will be the power to the k-1
14+
// this will be used when we start shifting our window of size k to the left from the end of the string
15+
weight = (weight *power) %modulo;
16+
}
17+
/**We'll have to use the above for loop to calculate weight instead of using Math.pow(power, k - 1) which will render wrong results when power and k are big enough.*/
18+
19+
// initialize the result string to empty string and keep updating it as we start from the end of the string, and we need to find the first substring that has the hashvalue
20+
Stringresult ="";
21+
22+
// right bound of the sliding window which starts at the end of the string
23+
intright =s.length() -1;
24+
25+
longhash =0;
26+
for (inti =s.length() -1;i >=0;i--) {
27+
28+
// add the next value of char for the left pointer into the sliding window
29+
intval =s.charAt(i) -'a' +1;
30+
31+
// update the current hash value
32+
hash = (hash *power %modulo +val) %modulo;
33+
34+
// when window is at size k, we need to check if we find a matching hash value
35+
// and update the result, and remove the right most char out of the window to prepare for next iteration
36+
if (right -i +1 ==k) {
37+
if (hash ==hashValue) {
38+
result =s.substring(i,right +1);
39+
}
40+
hash = (hash +modulo - (s.charAt(right--) -'a' +1) *weight %modulo) %modulo;
41+
}
42+
}
43+
44+
returnresult;
45+
}
46+
47+
}
48+
}
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._2156;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
publicclass_2156Test {
10+
privatestatic_2156.Solution1solution1;
11+
privatestaticStrings;
12+
privateintpower;
13+
privateintmodulo;
14+
privatestaticintk;
15+
privatestaticinthashValue;
16+
privatestaticStringexpected;
17+
18+
@BeforeClass
19+
publicstaticvoidsetup() {
20+
solution1 =new_2156.Solution1();
21+
}
22+
23+
@Test
24+
publicvoidtest1() {
25+
s ="leetcode";
26+
power =7;
27+
modulo =20;
28+
k =2;
29+
hashValue =0;
30+
expected ="ee";
31+
assertEquals(expected,solution1.subStrHash(s,power,modulo,k,hashValue));
32+
}
33+
34+
@Test
35+
publicvoidtest2() {
36+
s ="fbxzaad";
37+
power =31;
38+
modulo =100;
39+
k =3;
40+
hashValue =32;
41+
expected ="fbx";
42+
assertEquals(expected,solution1.subStrHash(s,power,modulo,k,hashValue));
43+
}
44+
45+
@Test
46+
publicvoidtest3() {
47+
s ="xmmhdakfursinye";
48+
power =96;
49+
modulo =45;
50+
k =15;
51+
hashValue =21;
52+
expected ="xmmhdakfursinye";
53+
System.out.println(Math.pow(power,k -1));
54+
System.out.println(Math.pow(power,k -1) %modulo);
55+
assertEquals(expected,solution1.subStrHash(s,power,modulo,k,hashValue));
56+
}
57+
58+
}

0 commit comments

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