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

Commitb4af8e7

Browse files
refactor 936
1 parent699e86c commitb4af8e7

File tree

3 files changed

+86
-0
lines changed

3 files changed

+86
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -395,6 +395,7 @@ _If you like this project, please leave me a star._ ★
395395
|941|[Valid Mountain Array](https://leetcode.com/problems/valid-mountain-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_941.java)||Easy|
396396
|938|[Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_938.java) | |Medium| BST, recursion, DFS
397397
|937|[Reorder Log Files](https://leetcode.com/problems/reorder-log-files/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_937.java)||Easy|
398+
|936|[Stamping The Sequence](https://leetcode.com/problems/stamping-the-sequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_936.java) | |Hard| String, Greedy
398399
|935|[Knight Dialer](https://leetcode.com/problems/knight-dialer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_935.java)||Medium|
399400
|933|[Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_933.java)||Easy|
400401
|931|[Minimum Falling Path Sum](https://leetcode.com/problems/minimum-falling-path-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_931.java) | |Medium|Dynamic Programming
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.List;
5+
6+
publicclass_936 {
7+
publicstaticclassSolution1 {
8+
/**
9+
* credit: https://leetcode.com/problems/stamping-the-sequence/discuss/201546/12ms-Java-Solution-Beats-100
10+
* <p>
11+
* Think reversely!
12+
* How to change target to ****?!
13+
*/
14+
publicint[]movesToStamp(Stringstamp,Stringtarget) {
15+
List<Integer>moves =newArrayList<>();
16+
char[]s =stamp.toCharArray();
17+
char[]t =target.toCharArray();
18+
intstars =0;
19+
boolean[]visited =newboolean[target.length()];
20+
while (stars <target.length()) {
21+
booleandoneReplace =false;
22+
for (inti =0;i <=target.length() -stamp.length();i++) {
23+
if (!visited[i] &&canReplace(t,i,s)) {
24+
stars =doReplace(t,i,s,stars);
25+
doneReplace =true;
26+
visited[i] =true;
27+
moves.add(i);
28+
if (stars ==t.length) {
29+
break;
30+
}
31+
}
32+
}
33+
if (!doneReplace) {
34+
returnnewint[0];
35+
}
36+
}
37+
38+
int[]result =newint[moves.size()];
39+
for (inti =0;i <moves.size();i++) {
40+
result[i] =moves.get(moves.size() -i -1);
41+
}
42+
returnresult;
43+
}
44+
45+
privatebooleancanReplace(char[]t,inti,char[]s) {
46+
for (intj =0;j <s.length;j++) {
47+
if (t[i +j] !='*' &&t[i +j] !=s[j]) {
48+
returnfalse;
49+
}
50+
}
51+
returntrue;
52+
}
53+
54+
privateintdoReplace(char[]t,inti,char[]s,intstars) {
55+
for (intj =0;j <s.length;j++) {
56+
if (t[i +j] !='*') {
57+
t[i +j] ='*';
58+
stars++;
59+
}
60+
}
61+
returnstars;
62+
}
63+
}
64+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._936;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertArrayEquals;
8+
9+
publicclass_936Test {
10+
privatestatic_936.Solution1solution1;
11+
12+
@BeforeClass
13+
publicstaticvoidsetup() {
14+
solution1 =new_936.Solution1();
15+
}
16+
17+
@Test
18+
publicvoidtest1() {
19+
assertArrayEquals(newint[]{0,2},solution1.movesToStamp("abc","ababc"));
20+
}
21+
}

0 commit comments

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