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

Commit79e3890

Browse files
committed
276 (1)
1 parent603ece7 commit79e3890

File tree

3 files changed

+183
-0
lines changed

3 files changed

+183
-0
lines changed

‎src/_276_PaintFence/Solution.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag : Dynamic Programming
4+
* @by : Steven Cooks
5+
* @date: Sep 29, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* There is a fence with n posts, each post can be painted with one of the
10+
* k colors.
11+
*
12+
* You have to paint all the posts such that no more than two adjacent
13+
* fence posts have the same color.
14+
*
15+
* Return the total number of ways you can paint the fence.
16+
*
17+
* Note: n and k are non-negative integers.
18+
*
19+
***************************************************************************
20+
* {@link https://leetcode.com/problems/paint-fence/ }
21+
*/
22+
package_276_PaintFence;
23+
24+
/** see test {@link _276_PaintFence.SolutionTest } */
25+
publicclassSolution {
26+
27+
publicintnumWays(intn,intk) {
28+
if (n ==0) {
29+
return0;
30+
}elseif (n ==1) {
31+
returnk;
32+
}
33+
intdiffColorCounts =k * (k -1);
34+
intsameColorCounts =k;
35+
for (inti =2;i <n;i++) {
36+
inttemp =diffColorCounts;
37+
diffColorCounts = (diffColorCounts +sameColorCounts) * (k -1);
38+
sameColorCounts =temp;
39+
}
40+
returndiffColorCounts +sameColorCounts;
41+
}
42+
43+
}

‎src/_276_PaintFence/Solution2.java

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag : Dynamic Programming
4+
* @by : Steven Cooks
5+
* @date: Sep 29, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* There is a fence with n posts, each post can be painted with one of the
10+
* k colors.
11+
*
12+
* You have to paint all the posts such that no more than two adjacent
13+
* fence posts have the same color.
14+
*
15+
* Return the total number of ways you can paint the fence.
16+
*
17+
* Note: n and k are non-negative integers.
18+
*
19+
***************************************************************************
20+
* {@link https://leetcode.com/problems/paint-fence/ }
21+
* @refer {@link https://leetcode.com/discuss/58451/java-dp-solution }
22+
*/
23+
package_276_PaintFence;
24+
25+
/** see test {@link _276_PaintFence.SolutionTest } */
26+
publicclassSolution2 {
27+
28+
publicintnumWays(intn,intk) {
29+
if (n ==0 ||k ==0)
30+
return0;
31+
if (n ==1)
32+
returnk;
33+
// same[i] means the ith post has the same color with the (i-1)th post.
34+
int[]same =newint[n];
35+
// diff[i] means the ith post has a different color with the (i-1)th
36+
// post.
37+
int[]diff =newint[n];
38+
same[0] =same[1] =k;
39+
diff[0] =k;
40+
diff[1] =k * (k -1);
41+
for (inti =2;i <n; ++i) {
42+
same[i] =diff[i -1];
43+
diff[i] = (k -1) *same[i -1] + (k -1) *diff[i -1];
44+
}
45+
returnsame[n -1] +diff[n -1];
46+
}
47+
48+
}
Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package_276_PaintFence;
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 _276_PaintFence.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+
// public void Test1() {
31+
// int n = 0;
32+
// int k = 1;
33+
// int actual = solution.numWays(n, k);
34+
// int expected = 0;
35+
// assertEquals(expected, actual);
36+
// }
37+
//
38+
// @Test
39+
// public void Test2() {
40+
// int n = 1;
41+
// int k = 0;
42+
// int actual = solution.numWays(n, k);
43+
// int expected = 0;
44+
// assertEquals(expected, actual);
45+
// }
46+
47+
@Test
48+
publicvoidTest3() {
49+
intn =1;
50+
intk =1;
51+
intactual =solution.numWays(n,k);
52+
intexpected =1;
53+
assertEquals(expected,actual);
54+
}
55+
56+
@Test
57+
publicvoidTest4() {
58+
intn =1;
59+
intk =5;
60+
intactual =solution.numWays(n,k);
61+
intexpected =5;
62+
assertEquals(expected,actual);
63+
}
64+
65+
@Test
66+
publicvoidTest5() {
67+
intn =2;
68+
intk =3;
69+
intactual =solution.numWays(n,k);
70+
intexpected =9;
71+
assertEquals(expected,actual);
72+
}
73+
74+
@Test
75+
publicvoidTest6() {
76+
intn =3;
77+
intk =4;
78+
intactual =solution.numWays(n,k);
79+
intexpected =60;
80+
assertEquals(expected,actual);
81+
}
82+
83+
@Test
84+
publicvoidTest7() {
85+
intn =2;
86+
intk =1;
87+
intactual =solution.numWays(n,k);
88+
intexpected =1;
89+
assertEquals(expected,actual);
90+
}
91+
92+
}

0 commit comments

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