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

Commit8c4892a

Browse files
add 651
1 parentc53bfa6 commit8c4892a

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
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
2020

2121
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2222
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
23+
|651|[4 Keys Keyboard](https://leetcode.com/problems/4-keys-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_651.java) | O(n^2) |O(n) | Medium | DP
2324
|650|[2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_650.java) | O(n^2) |O(n) | Medium | DP
2425
|648|[Replace Words](https://leetcode.com/problems/replace-words/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_648.java) | O(n) |O(n) | Medium | Trie
2526
|647|[Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_647.java) | O(n^2) |O(1) | Medium | DP
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packagecom.fishercoder.solutions;
2+
3+
/**
4+
* 651. 4 Keys Keyboard
5+
*
6+
* Imagine you have a special keyboard with the following keys:
7+
8+
Key 1: (A): Prints one 'A' on screen.
9+
10+
Key 2: (Ctrl-A): Select the whole screen.
11+
12+
Key 3: (Ctrl-C): Copy selection to buffer.
13+
14+
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
15+
16+
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
17+
18+
Example 1:
19+
Input: N = 3
20+
Output: 3
21+
Explanation:
22+
We can at most get 3 A's on screen by pressing following key sequence:
23+
A, A, A
24+
25+
Example 2:
26+
Input: N = 7
27+
Output: 9
28+
Explanation:
29+
We can at most get 9 A's on screen by pressing following key sequence:
30+
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
31+
32+
Note:
33+
1 <= N <= 50
34+
Answers will be in the range of 32-bit signed integer.
35+
*/
36+
publicclass_651 {
37+
38+
/**Minimum needs to be more than 3 A's in a row, otherwise "Ctrl A, Ctrl C, Ctrl V" will make fewer A's than directly
39+
* copying A's with the equal number of steps.
40+
* E.g. when n == 5,
41+
* if we do 5 this: A, A, Ctrl A, Ctrl C, Ctrl V, => this will result in only AAAA (4 A's)
42+
* while if we do A, A, A, A, A, => this will result in AAAAA (5 A's)
43+
* So, at a minimum, we need to have 3 A's, then it's worth to do "Ctrl A, Ctrl C, Ctrl V"..
44+
* That's why we have j = 3 in the inner for loop below.
45+
* */
46+
publicintmaxA(intN) {
47+
int[]dp =newint[N+1];
48+
for (inti =1;i <=N;i++) {
49+
dp[i] =i;
50+
for (intj =3;j <i;j++) {
51+
dp[i] =Math.max(dp[i],dp[i-j] * (j-1));
52+
}
53+
}
54+
returndp[N];
55+
}
56+
57+
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._651;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticorg.junit.Assert.assertEquals;
8+
9+
/**
10+
* Created by stevesun on 7/30/17.
11+
*/
12+
publicclass_651Test {
13+
privatestatic_651test;
14+
15+
@BeforeClass
16+
publicstaticvoidsetup(){
17+
test =new_651();
18+
}
19+
20+
@Test
21+
publicvoidtest1(){
22+
assertEquals(3,test.maxA(3));
23+
}
24+
25+
@Test
26+
publicvoidtest2(){
27+
assertEquals(324,test.maxA(20));
28+
}
29+
30+
@Test
31+
publicvoidtest3(){
32+
assertEquals(256,test.maxA(19));
33+
}
34+
35+
@Test
36+
publicvoidtest4(){
37+
assertEquals(1,test.maxA(1));
38+
}
39+
40+
@Test
41+
publicvoidtest5(){
42+
assertEquals(1327104,test.maxA(50));
43+
}
44+
45+
@Test
46+
publicvoidtest6(){
47+
assertEquals(9,test.maxA(7));
48+
}
49+
}

0 commit comments

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