Huahua's Tech Road
Problem
You have an initial power P, an initial score of 0 points, and a bag of tokens.
Each token can be used at most once, has a value token[i], and has potentially two ways to use it.
- If we have at least
token[i]power, we may play the token face up, losingtoken[i]power, and gaining1point. - If we have at least
1point, we may play the token face down, gainingtoken[i]power, and losing1point.
Return the largest number of points we can have after playing any number of tokens.
Example 1:
Input: tokens = [100], P = 50 Output: 0
Example 2:
Input: tokens = [100,200], P = 150 Output: 1
Example 3:
Input: tokens = [100,200,300,400], P = 200 Output: 2
Note:
tokens.length <= 10000 <= tokens[i] < 100000 <= P < 10000
Solution: Greedy + Two Pointers
Sort the tokens, gain points from the low end gain power from the high end.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, Running time: 8 ms class Solution { public: int bagOfTokensScore(vector<int>& tokens, int P) { sort(begin(tokens), end(tokens)); int points = 0; int ans = 0; int i = 0; int j = tokens.size() - 1; while (i <= j) if (P >= tokens[i]) { P -= tokens[i++]; ans = max(ans, ++points); } else if (points > 0) { P += tokens[j--]; --points; } else { break; } return ans; } }; |
Problem
On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
Now, a move consists of removing a stone that shares a column or row with another stone on the grid.
What is the largest possible number of moves we can make?
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Example 3:
Input: stones = [[0,0]]
Output: 0
Note:
1 <= stones.length <= 10000 <= stones[i][j] < 10000
Solution 2: Union Find
Find all connected components (islands)
Ans = # of stones – # of islands
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// Author: Huahua, running time: 16 ms class Solution { public: int removeStones(vector<vector<int>>& stones) { const int kSize = 10000; DSU dsu(kSize * 2); for (const auto& stone : stones) dsu.Union(stone[0], stone[1] + kSize); unordered_set<int> seen; for (const auto& stone : stones) seen.insert(dsu.Find(stone[0])); return stones.size() - seen.size(); } private: class DSU { public: DSU(int n): p_(n) { for (int i = 0 ; i < n; ++i) p_[i] = i; } void Union(int i, int j) { p_[Find(i)] = Find(j); } int Find(int i) { if (p_[i] != i) p_[i] = Find(p_[i]); return p_[i]; } private: vector<int> p_; }; }; |
Related Problems
Problem
Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: true Explanation: We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output: false Explanation: 1 cannot be popped before 2.
Note:
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushedis a permutation ofpopped.pushedandpoppedhave distinct values.
Solution: Simulation
Simulate the push/pop operation.
Push element from |pushed sequence| onto stack s one by one and pop when top of the stack s is equal the current element in the |popped sequence|.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, 8 ms class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> s; auto it = begin(popped); for (int e : pushed) { s.push(e); while (!s.empty() && s.top() == *it) { s.pop(); ++it; } } return it == end(popped); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua, Running time: 40 ms class Solution: def validateStackSequences(self, pushed, popped): s = [] i = 0 for e in pushed: s.append(e) while s and s[-1] == popped[i]: s.pop() i += 1 return i == len(popped) |
Problem
Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.
Return the least number of moves to make every value in A unique.
Example 1:
Input: [1,2,2] Output: 1 Explanation: After 1 move, the array could be [1, 2, 3].
Example 2:
Input: [3,2,1,2,1,7] Output: 6 Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7]. It can be shown with 5 or less moves that it is impossible for the array to have all unique values.
Note:
0 <= A.length <= 400000 <= A[i] < 40000
Solution: Greedy
Sort the elements, make sure A[i] >= A[i-1] + 1, if not increase A[i] to A[i – 1] + 1
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 56 ms class Solution { public: int minIncrementForUnique(vector<int>& A) { int ans = 0; sort(begin(A), end(A)); for (int i = 1; i < A.size(); ++i) { if (A[i] > A[i - 1]) continue; ans += (A[i - 1] - A[i]) + 1; A[i] = A[i - 1] + 1; } return ans; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua, Running time: 196 ms class Solution(object): def minIncrementForUnique(self, A): A.sort() ans = 0 for i in range(1, len(A)): if A[i] > A[i - 1]: continue ans += A[i - 1] - A[i] + 1 A[i] = A[i - 1] + 1 return ans |