650 2 Keys Keyboard - Algorithm Practice

Algorithm Practice

Search…

Algorithm Practice

Topological Sort

Breadth First Search

Dynamic Programming

Longest Common Subsequence

Knapsack Problem

10 Regular Expression Matching

32 Longest Valid Parentheses

44 Wildcard Matching

53 Maximum Subarray

62 Unique Paths

63 Unique Paths II

64 Minimum Path Sum

70 Climbing Stairs

85 Maximal Rectangle

87 Scramble String

95 Unique Binary Search Trees II

96 Unique Binary Search Trees

97 Interleaving String

121 Best Time to Buy and Sell Stock

122 Best Time to Buy and Sell Stock II

123 Best Time to Buy and Sell Stock III

140 Word Break II

152 Maximum Product Subarray

174 Dungeon Game

188 Best Time to Buy and Sell Stock IV

198 House Robber

213 House Robber II

221 Maximal Square

238 Product of Array Except Self

256 Paint House

264 Ugly Number II

265 Paint House II

276 Paint Fence

279 Perfect Squares

303 Range Sum Query - Immutable

304 Range Sum Query 2D - Immutable

309 Best Time to Buy and Sell Stock with Cooldown

321 Create Maximum Number

338 Counting Bits

343 Integer Break

363 Max Sum of Rectangle No Larger Than K

368 Largest Divisible Subset

410 Split Array Largest Sum

413 Arithmetic Slices

418 Sentence Screen Fitting

446 Arithmetic Slices II - Subsequence

466 Count The Repetitions

467 Unique Substrings in Wraparound String

471 Encode String with Shortest Length

514 Freedom Trail

517 Super Washing Machines

523 Continuous Subarray Sum

552 Student Attendance Record II

562 Longest Line of Consecutive One in Matrix

568 Maximum Vacation Days

576 Out of Boundary Paths

600 Non-negative Integers without Consecutive Ones

629 K Inverse Pairs Array

638 Shopping Offers

639 Decode Ways II

650 2 Keys Keyboard

651 4 Keys Keyboard

688 Knight Probability in Chessboard

689 Maximum Sum of 3 Non-Overlapping Subarrays

691 Stickers to Spell Word

698 Partition to K Equal Sum Subsets

714 Best Time to Buy and Sell Stock with Transaction Fee

718 Maximum Length of Repeated Subarray

727 Minimum Window Subsequence

730 Count Different Palindromic Subsequences

740 Delete and Earn

741 Cherry Pickup

746 Min Cost Climbing Stairs

750 Number Of Corner Rectangles

764 Largest Plus Sign

787 Cheapest Flights Within K Stops

790 Domino and Tromino Tiling

801 Minimum Swaps To Make Sequences Increasing

Reservoir Sampling

Powered By GitBook

650 2 Keys Keyboard

650. 2 Keys Keyboard​
1. Question
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
1.Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2.Paste: You can paste the characters which are copied last time.
Given a numbern. You have to getexactlyn'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to getn'A'.
Example 1:
1
Input: 3
2
​
3
Output: 3
4
​
5
Explanation:
6
​
7
Intitally, we have one character 'A'.
8
In step 1, we use Copy All operation.
9
In step 2, we use Paste operation to get 'AA'.
10
In step 3, we use Paste operation to get 'AAA'.
Copied!
Note:
1.Thenwill be in the range [1, 1000].
2. Implementation
(1) DP
1
class Solution {
2
    public int minSteps(int n) {
3
        if (n <= 1) {
4
            return 0;
5
        }
6
        int[] dp = new int[n + 1];
7
​
8
        for (int i = 1; i <= n; i++) {
9
            dp[i] = i;
10
            for (int j = i - 1; j >= 1; j--) {
11
                if (i % j == 0) {
12
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
13
                }
14
            }
15
        }
16
        return dp[n];
17
    }
18
}
Copied!
3. Time & Space Complexity
DFS + Memoization: 时间复杂度O(k ^(mn)), k是offer的数量, m是item的个数，n是每个item要买的个数，空间复杂度O(mn)?

639 Decode Ways II

651 4 Keys Keyboard

Last modified 2yr ago

Copy link

Contents

650. 2 Keys Keyboard

2. Implementation

3. Time & Space Complexity