LeetCode [818] Race Car

Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1.  (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

Note:

• 1 <= target <= 10000.

@LuckyPants/@LeetCode

https://leetcode.com/problems/race-car/discuss/123834/C%2B%2BJavaPython-DP-solution 

Consider two general cases: 

1. target == 2^i-1, this case, i is the best way
2. 2^(i-1)-1 < target < 2^i-1, there are two ways to arrive at target:
   • Use i A to arrive at 2^i-1 first, then use R to change the direction, by here there are i+1 operations (n A and one R), then the remaining is same as dp[2^i-1-target]
   • Use i-1 A to arrive at 2^(i-1)-1 first, then R to change the direction, use m A to go backward, then use R to change the direction again to move forward, by here there are i-1+2+m=i+m+1 operations (i-1 A, two R, m A) , current position is 2^(i-1)-1-(2^m-1)=2^(i-1)-2^m, the remaining operations is same as dp[target-(2^(i-1)-1)+(2^m-1)]=dp[target-2^(i-1)+2^m)].

For example:

target = 5

The right answer should be AARARAA, positions: 0, 1, 3, 3, 2, 2, 3, 5
But if we use the above formula, the answer is AA (0->3) RR (make speed at 1 again) AARA (3->5)

We can move the last A to the middle of RR, so that we save an operation. That's where the combine can happen.

So we do dp by adding m A between the RR and add the # operations for remaining distance.

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

class Solution { int dp[10001]; public: int racecar(int target) { if (dp[target] != 0) return dp[target]; int n = floor(log2(target)) + 1; if (target == pow(2, n) - 1) { dp[target] = n; } else { dp[target] = n + 1 + racecar((int)pow(2, n) - 1 - target); for (int i = 0; i < n - 1; ++i) { dp[target] = min(dp[target], racecar(target - (int)pow(2, n - 1) + (int)pow(2, i)) + i + n + 1); } } return dp[target]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { int[] dp = new int[10001]; public int racecar(int target) { if(dp[target]!=0) return dp[target]; int i = (int)(Math.log(target)/Math.log(2))+1; if(target == Math.pow(2,i)-1){ dp[target] = i; }else{ dp[target] = i+1+racecar((int)Math.pow(2,i)-1-target); for(int m=0; m<i-1; ++m){ dp[target] = Math.min(dp[target], i+1+m+racecar(target-(int)Math.pow(2, i-1)+(int)Math.pow(2, m))); } } return dp[target]; } }

LeetCode [497] Random Point in Non-overlapping Rectangles

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

1. An integer point is a point that has integer coordinates. 
2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
3. ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
4. length and width of each rectangle does not exceed 2000.
5. 1 <= rects.length <= 100
6. pick return a point as an array of integer coordinates [p_x, p_y]
7. pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

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 34 35

class Solution { map<int, int> hash; int sum; vector<vector<int>> rectangles; public: Solution(vector<vector<int>> &rects) { sum = 0; rectangles = rects; for (int i = 0; i < rects.size(); ++i) { sum += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1); hash[sum] = i; } } vector<int> pick() { //randomly pick a vector proportional to its size int r = rand() % sum; auto it = hash.upper_bound(r); //generate a random vector inside that rectangle int x = rand() % (rectangles[it->second][2] - rectangles[it->second][0] + 1) + rectangles[it->second][0]; int y = rand() % (rectangles[it->second][3] - rectangles[it->second][1] + 1) + rectangles[it->second][1]; return vector<int>{x, y}; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector<int> param_1 = obj->pick(); */

LeetCode[951] Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent.  The trees are given by root nodes root1 and root2.

Example 1:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Note:

1. Each tree will have at most 100 nodes.
2. Each value in each tree will be a unique integer in the range [0, 99].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool flipEquiv(TreeNode* root1, TreeNode* root2) { if(!root1 && !root2) return true; if(!root1 || !root2) return false; if(root1->val != root2->val) return false; if(flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) return true; if(flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left)) return true; return false; } };

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

//Java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean flipEquiv(TreeNode root1, TreeNode root2) { if(root1==null && root2==null) return true; if(root1==null || root2==null) return false; if(root1.val != root2.val) return false; return (flipEquiv(root1.left, root2.left)&&flipEquiv(root1.right, root2.right)) || (flipEquiv(root1.left, root2.right)&&flipEquiv(root1.right, root2.left)); } }

LeetCode [544] Output Contest Matches

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you're given n teams, you need to output their final contest matches in the form of a string.

The n teams are given in the form of positive integers from 1 to n, which represents their initial rank. (Rank 1 is the strongest team and Rank n is the weakest team.) We'll use parentheses('(', ')') and commas(',') to represent the contest team pairing - parentheses('(' , ')') for pairing and commas(',') for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Example 1:

Input: 2
Output: (1,2)
Explanation: 
Initially, we have the team 1 and the team 2, placed like: 1,2.
Then we pair the team (1,2) together with '(', ')' and ',', which is the final answer.

Example 2:

Input: 4
Output: ((1,4),(2,3))
Explanation: 
In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1,4),(2,3).
In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).

Example 3:

Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation: 
First round: (1,8),(2,7),(3,6),(4,5)
Second round: ((1,8),(4,5)),((2,7),(3,6))
Third round: (((1,8),(4,5)),((2,7),(3,6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).

Note:

1. The n is in range [2, 212].
2. We ensure that the input n can be converted into the form 2k, where k is a positive integer.

========

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: string findContestMatch(int n) { vector<string> schedules(n); for (int i = 0; i < n; ++i) { schedules[i] = to_string(i + 1); } while (n) { for (int i = 0; i < n/2; i++) { schedules[i] = "(" + schedules[i] + "," + schedules[n - 1 - i] + ")"; } n = n / 2; } return schedules[0]; } };