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

Commita66d65e

Browse files
add 672
1 parent3d4e770 commita66d65e

File tree

4 files changed

+207
-0
lines changed

4 files changed

+207
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
2222

2323
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2424
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
25+
|672|[Bulb Switcher II](https://leetcode.com/problems/bulb-switcher-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_672.java) | O(1) | O(1) | Medium | Math
2526
|671|[Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_671.java) | O(n) | O(n) | Easy | Tree, DFS
2627
|670|[Maximum Swap](https://leetcode.com/problems/maximum-swap/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_670.java) | O(n^2) | O(1) | Medium | String
2728
|669|[Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_669.java) | O(n) | O(1) | Easy | Tree, DFS

‎src/main/java/com/fishercoder/common/utils/CommonUtils.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,16 @@ public static void printArray(int[] nums) {
3232
System.out.println();
3333
}
3434

35+
publicstaticvoidprint2DIntArray(int[][]nums) {
36+
for (int[]array :nums) {
37+
for (inti :array) {
38+
System.out.print(i +", ");
39+
}
40+
System.out.println();
41+
}
42+
System.out.println();
43+
}
44+
3545
publicstaticvoidprint(Stringmessage) {
3646
System.out.print(message);
3747
}
Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importcom.fishercoder.common.utils.CommonUtils;
4+
5+
/**
6+
* 672. Bulb Switcher II
7+
* There is a room with n lights which are turned on initially and 4 buttons on the wall.
8+
* After performing exactly m unknown operations towards buttons,
9+
* you need to return how many different kinds of status of the n lights could be.
10+
* Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:
11+
12+
Flip all the lights.
13+
Flip lights with even numbers.
14+
Flip lights with odd numbers.
15+
Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...
16+
17+
Example 1:
18+
19+
Input: n = 1, m = 1.
20+
Output: 2
21+
Explanation: Status can be: [on], [off]
22+
23+
Example 2:
24+
25+
Input: n = 2, m = 1.
26+
Output: 3
27+
Explanation: Status can be: [on, off], [off, on], [off, off]
28+
29+
Example 3:
30+
31+
Input: n = 3, m = 1.
32+
Output: 4
33+
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].
34+
35+
Note: n and m both fit in range [0, 1000].
36+
*/
37+
publicclass_672 {
38+
publicstaticclassSolution1 {
39+
publicintflipLights(intn,intm) {
40+
if (m <1) {
41+
return1;
42+
}
43+
int[][]dp =newint[m][n];
44+
for (inti =0;i <m;i++) {
45+
for (intj =0;j <n;j++) {
46+
if (j ==0) {
47+
dp[i][j] =2;
48+
}elseif (i ==0 &&j ==1) {
49+
dp[i][j] =3;
50+
}elseif (i ==0) {
51+
dp[i][j] =4;
52+
}elseif (i ==1 &&j ==1) {
53+
dp[i][j] =4;
54+
}elseif (i ==1 &&j >1) {
55+
dp[i][j] =7;
56+
}elseif (j ==1) {
57+
dp[i][j] =4;
58+
}elseif (i ==1) {
59+
dp[i][j] =7;
60+
}else {
61+
dp[i][j] =8;
62+
}
63+
}
64+
}
65+
CommonUtils.print2DIntArray(dp);
66+
returndp[m-1][n-1];
67+
}
68+
}
69+
70+
publicstaticclassSolution2 {
71+
publicintflipLights(intn,intm) {
72+
if (n ==1 &&m >0) {
73+
return2;
74+
}elseif (n ==2 &&m ==1) {
75+
return3;
76+
}elseif ((n >2 &&m ==1) || (n ==2 &&m >1)) {
77+
return4;
78+
}elseif (n >2 &&m ==2) {
79+
return7;
80+
}elseif (n >2 &&m >2) {
81+
return8;
82+
}else {
83+
return1;
84+
}
85+
}
86+
}
87+
}
Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._672;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
publicclass_672Test {
10+
privatestatic_672.Solution1solution1;
11+
privatestatic_672.Solution2solution2;
12+
13+
@BeforeClass
14+
publicstaticvoidsetup() {
15+
solution1 =new_672.Solution1();
16+
solution2 =new_672.Solution2();
17+
}
18+
19+
@Test
20+
publicvoidtest1() {
21+
assertEquals(2,solution1.flipLights(1,1));
22+
assertEquals(2,solution2.flipLights(1,1));
23+
}
24+
25+
@Test
26+
publicvoidtest2() {
27+
assertEquals(3,solution1.flipLights(2,1));
28+
assertEquals(3,solution2.flipLights(2,1));
29+
}
30+
31+
@Test
32+
publicvoidtest3() {
33+
assertEquals(4,solution1.flipLights(3,1));
34+
assertEquals(4,solution2.flipLights(3,1));
35+
}
36+
37+
@Test
38+
publicvoidtest4() {
39+
assertEquals(4,solution1.flipLights(4,1));
40+
assertEquals(4,solution2.flipLights(4,1));
41+
}
42+
43+
@Test
44+
publicvoidtest5() {
45+
assertEquals(4,solution1.flipLights(10,1));
46+
assertEquals(4,solution2.flipLights(10,1));
47+
}
48+
49+
@Test
50+
publicvoidtest6() {
51+
assertEquals(4,solution1.flipLights(2,2));
52+
assertEquals(4,solution2.flipLights(2,2));
53+
}
54+
55+
@Test
56+
publicvoidtest7() {
57+
assertEquals(2,solution1.flipLights(1,2));
58+
assertEquals(2,solution2.flipLights(1,2));
59+
}
60+
61+
@Test
62+
publicvoidtest8() {
63+
assertEquals(2,solution1.flipLights(1,3));
64+
assertEquals(2,solution2.flipLights(1,3));
65+
}
66+
67+
@Test
68+
publicvoidtest9() {
69+
assertEquals(2,solution1.flipLights(1,4));
70+
assertEquals(2,solution2.flipLights(1,4));
71+
}
72+
73+
@Test
74+
publicvoidtest10() {
75+
assertEquals(2,solution1.flipLights(1,5));
76+
assertEquals(2,solution2.flipLights(1,5));
77+
}
78+
79+
@Test
80+
publicvoidtest11() {
81+
assertEquals(2,solution1.flipLights(1,10));
82+
assertEquals(2,solution2.flipLights(1,10));
83+
}
84+
85+
@Test
86+
publicvoidtest12() {
87+
assertEquals(7,solution1.flipLights(3,2));
88+
assertEquals(7,solution2.flipLights(3,2));
89+
}
90+
91+
@Test
92+
publicvoidtest13() {
93+
assertEquals(8,solution1.flipLights(7,5));
94+
assertEquals(8,solution2.flipLights(7,5));
95+
}
96+
97+
@Test
98+
publicvoidtest14() {
99+
assertEquals(1,solution1.flipLights(1,0));
100+
assertEquals(1,solution2.flipLights(1,0));
101+
}
102+
103+
@Test
104+
publicvoidtest15() {
105+
assertEquals(8,solution1.flipLights(7,5));
106+
assertEquals(8,solution2.flipLights(7,5));
107+
}
108+
109+
}

0 commit comments

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