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

Commit6854625

Browse files
add a dp solution for 788
1 parent14b55e0 commit6854625

File tree

2 files changed

+68
-11
lines changed

2 files changed

+68
-11
lines changed

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

Lines changed: 44 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ public static class Solution1 {
88
/**
99
* My very original, but non-DP solution.
1010
*/
11-
publicintrotatedDigits(intN) {
11+
publicintrotatedDigits(intn) {
1212
intcount =0;
1313
Map<Character,String>map =newHashMap<>();
1414
map.put('0',"0");
@@ -18,7 +18,7 @@ public int rotatedDigits(int N) {
1818
map.put('5',"2");
1919
map.put('6',"9");
2020
map.put('9',"6");
21-
for (inti =1;i <=N;i++) {
21+
for (inti =1;i <=n;i++) {
2222
if (isRotatedNumber(i,map)) {
2323
count++;
2424
}
@@ -39,4 +39,46 @@ private boolean isRotatedNumber(int num, Map<Character, String> map) {
3939
return !originalNum.equals(sb.toString());
4040
}
4141
}
42+
43+
publicstaticclassSolution2 {
44+
/**
45+
* credit: https://leetcode.com/problems/rotated-digits/discuss/117975/Java-dp-solution-9ms
46+
* dp[i] = 0 means invalid;
47+
* dp[i] = 1 means valid but the same;
48+
* dp[i] = 2 means valid and different.
49+
*/
50+
publicintrotatedDigits(intn) {
51+
int[]dp =newint[n +1];
52+
intcount =0;
53+
for (intnum =0;num <=n;num++) {
54+
if (num <10) {
55+
if (num ==0 ||num ==1 ||num ==8) {
56+
dp[num] =1;
57+
}elseif (num ==2 ||num ==5 ||num ==6 ||num ==9) {
58+
count++;
59+
dp[num] =2;
60+
}
61+
}else {
62+
/**Here's the key/beauty of this DP solution:
63+
* we could keep checking each number by reusing the previous number we worked on,
64+
* basically, always break a bigger number into two parts: a number that's its right most digit and everything else, e.g.
65+
* num = 12 -> 1 and 2, so we check dp[1] and dp[2] to know if 12 could be rotated to a valid number,
66+
* num = 123 -> 12 and 3, so we check dp[12] and dp[3] to know if 123 could be rotated to a valid number.
67+
* and so on.
68+
* */
69+
inta =dp[num /10];
70+
intb =dp[num %10];
71+
if (a ==1 &&b ==1) {
72+
//we first check if both are valid and the same, if that's the case, then we mark it as 1
73+
dp[num] =1;
74+
}elseif (a >=1 &&b >=1) {
75+
//then only in this case, either a or b is greater than 1, it's a valid and different number
76+
dp[num] =2;
77+
count++;
78+
}
79+
}
80+
}
81+
returncount;
82+
}
83+
}
4284
}

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

Lines changed: 24 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -7,15 +7,30 @@
77
importstaticjunit.framework.TestCase.assertEquals;
88

99
publicclass_788Test {
10-
privatestatic_788.Solution1solution1;
10+
privatestatic_788.Solution1solution1;
11+
privatestatic_788.Solution2solution2;
1112

12-
@BeforeClass
13-
publicstaticvoidsetup() {
14-
solution1 =new_788.Solution1();
15-
}
13+
@BeforeClass
14+
publicstaticvoidsetup() {
15+
solution1 =new_788.Solution1();
16+
solution2 =new_788.Solution2();
17+
}
1618

17-
@Test
18-
publicvoidtest1() {
19-
assertEquals(4,solution1.rotatedDigits(10));
20-
}
19+
@Test
20+
publicvoidtest1() {
21+
assertEquals(4,solution1.rotatedDigits(10));
22+
assertEquals(4,solution2.rotatedDigits(10));
23+
}
24+
25+
@Test
26+
publicvoidtest2() {
27+
assertEquals(247,solution1.rotatedDigits(857));
28+
assertEquals(247,solution2.rotatedDigits(857));
29+
}
30+
31+
@Test
32+
publicvoidtest3() {
33+
assertEquals(6,solution1.rotatedDigits(15));
34+
assertEquals(6,solution2.rotatedDigits(15));
35+
}
2136
}

0 commit comments

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