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

Commitc53bfa6

Browse files
add 650
1 parent4509d34 commitc53bfa6

File tree

3 files changed

+85
-0
lines changed

3 files changed

+85
-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+
|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
2324
|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
2425
|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
2526
|646|[Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_646.java) | O(nlogn) |O(1) | Medium | DP
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
packagecom.fishercoder.solutions;
2+
3+
/**
4+
* 650. 2 Keys Keyboard
5+
*
6+
* Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
7+
8+
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
9+
Paste: You can paste the characters which are copied last time.
10+
Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
11+
12+
Example 1:
13+
Input: 3
14+
Output: 3
15+
16+
Explanation:
17+
Intitally, we have one character 'A'.
18+
In step 1, we use Copy All operation.
19+
In step 2, we use Paste operation to get 'AA'.
20+
In step 3, we use Paste operation to get 'AAA'.
21+
22+
Note:
23+
The n will be in the range [1, 1000].
24+
*/
25+
publicclass_650 {
26+
27+
publicintminSteps(intn) {
28+
int[]dp =newint[n+1];
29+
for (inti =2;i <=n;i++) {
30+
dp[i] =i;//we assign i to dp[i] first, because for a lot of cases, e.g. for most cases when i is odd, its min steps is i itself, if it's not, we can overwrite it later
31+
for (intj =i-1;j >1;j--) {//traverse backwards, whenever it's divisible by j, we'll update dp[i] because it's guaranteed to be smaller when j is smaller.
32+
if (i %j ==0) {
33+
dp[i] =dp[j] + (i/j);
34+
break;
35+
}
36+
}
37+
}
38+
returndp[n];
39+
}
40+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._650;
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_650Test {
13+
privatestatic_650test;
14+
15+
@BeforeClass
16+
publicstaticvoidsetup(){
17+
test =new_650();
18+
}
19+
20+
@Test
21+
publicvoidtest1(){
22+
assertEquals(3,test.minSteps(3));
23+
}
24+
25+
@Test
26+
publicvoidtest2(){
27+
assertEquals(9,test.minSteps(20));
28+
}
29+
30+
@Test
31+
publicvoidtest3(){
32+
assertEquals(19,test.minSteps(19));
33+
}
34+
35+
@Test
36+
publicvoidtest4(){
37+
assertEquals(0,test.minSteps(1));
38+
}
39+
40+
@Test
41+
publicvoidtest5(){
42+
assertEquals(35,test.minSteps(741));
43+
}
44+
}

0 commit comments

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