We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5] Output: [5,10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide. Example 2:

Input: asteroids = [8,-8] Output: [] Explanation: The 8 and -8 collide exploding each other. Example 3:

Input: asteroids = [10,2,-5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10. Example 4:

Input: asteroids = [-2,-1,1,2] Output: [-2,-1,1,2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d - angle/2, d + angle/2].

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

Example 1:

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1] Output: 3 Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight. Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1] Output: 4 Explanation: All points can be made visible in your field of view, including the one at your location. Example 3:

Input: points = [[1,0],[2,1]], angle = 13, location = [1,1] Output: 1 Explanation: You can only see one of the two points, as shown above.

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

Example 1:

Input: nums = [5,3,2,4] Output: 0 Explanation: Change the array [5,3,2,4] to [2,2,2,2]. The difference between the maximum and minimum is 2-2 = 0. Example 2:

Input: nums = [1,5,0,10,14] Output: 1 Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. The difference between the maximum and minimum is 1-0 = 1. Example 3:

Input: nums = [6,6,0,1,1,4,6] Output: 2 Example 4:

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

Input: secret = “acckzz”, wordlist = [“acckzz”,”ccbazz”,”eiowzz”,”abcczz”], numguesses = 10 Output: You guessed the secret word correctly. Explanation: master.guess(“aaaaaa”) returns -1, because “aaaaaa” is not in wordlist. master.guess(“acckzz”) returns 6, because “acckzz” is secret and has all 6 matches. master.guess(“ccbazz”) returns 3, because “ccbazz” has 3 matches. master.guess(“eiowzz”) returns 2, because “eiowzz” has 2 matches. master.guess(“abcczz”) returns 4, because “abcczz” has 4 matches. We made 5 calls to master.guess and one of them was the secret, so we pass the test case. Example 2:

Input: secret = “hamada”, wordlist = [“hamada”,”khaled”], numguesses = 10 Output: You guessed the secret word correctly.

Constraints:

1 <= wordlist.length <= 100 wordlist[i].length == 6 wordlist[i] consist of lowercase English letters. All the strings of wordlist are unique. secret exists in wordlist. numguesses == 10

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15. Example 2:

Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.

//not optimized classSolution { public: intcountSquares(vector<vector<int>>& matrix){ int rows = matrix.size(); int cols = matrix[0].size(); sum.resize(rows+1, vector<int>(cols+1, 0)); for (int r = 1; r <= rows; r++) { for (int c = 1; c <= cols; c++) { sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + matrix[r-1][c-1]; } } int ans = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (matrix[r][c] != 1) continue; int x = r, y = c; while (x < rows && y < cols) { int ones = get_sum(r, c, x, y); if (ones == (x-r+1)*(x-r+1)) { ans++; x++; y++; } else { break; } } } } return ans; } intget_sum(int r1, int c1, int r2, int c2){ return sum[r2+1][c2+1] - sum[r1][c2+1] - sum[r2+1][c1] + sum[r1][c1]; } private: vector<vector<int>> sum; };

//O(rows * cols) classSolution { public: intcountSquares(vector<vector<int>>& matrix){ int rows = matrix.size(); int cols = matrix[0].size(); int ans = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (matrix[r][c] != 1) continue; if (r > 0 && c > 0) matrix[r][c] = min({matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]}) + 1; ans += matrix[r][c]; } } return ans; } };

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end) Example 1:

MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false MyCalendar.book(20, 30); // returns true Explanation: The first event can be booked. The second can’t because time 15 is already booked by another event. The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000. In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked. queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked. removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right). Example 1: addRange(10, 20): null removeRange(14, 16): null queryRange(10, 14): true (Every number in [10, 14) is being tracked) queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked) queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation) Note:

A half open interval [left, right) denotes all real numbers left <= x < right. 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange. The total number of calls to addRange in a single test case is at most 1000. The total number of calls to queryRange in a single test case is at most 5000. The total number of calls to removeRange in a single test case is at most 1000.

classRangeModule { public: RangeModule() { } //O(N) voidaddRange(int left, int right){ bool added = false; vector<pair<int,int>> new_ranges; int n = ranges.size(); int i = 0; while (i < n || !added) { pair<int,int> next; if (i == n || (!added && left < ranges[i].first)) { next = {left, right}; added = true; } else { next = ranges[i]; i++; } if (new_ranges.empty() || new_ranges.back().second < next.first) new_ranges.push_back(next); else new_ranges.back().second = max(new_ranges.back().second, next.second); } ranges.swap(new_ranges); } //O(logN) boolqueryRange(int left, int right){ int lo = 0, hi = ranges.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (ranges[mid].first <= left) lo = mid + 1; else hi = mid - 1; } if (lo == 0) returnfalse; int idx = lo - 1; return ranges[idx].first <= left && ranges[idx].second >= right; } //O(N) voidremoveRange(int left, int right){ vector<pair<int,int>> new_ranges; for (auto &range : ranges) { if (range.first >= right || range.second <= left) { new_ranges.push_back(range); continue; } pair<int,int> left_range = {range.first, left}; if (left_range.first < left_range.second) new_ranges.push_back(left_range); pair<int,int> right_range = {right, range.second}; if (right_range.first < right_range.second) new_ranges.push_back(right_range); } ranges.swap(new_ranges); } private: vector<pair<int,int>> ranges; };

/** * Your RangeModule object will be instantiated and called as such: * RangeModule* obj = new RangeModule(); * obj->addRange(left,right); * bool param_2 = obj->queryRange(left,right); * obj->removeRange(left,right); */

classRangeModule { public: RangeModule() { } //O(MlogN) m是erase的区间 voidaddRange(int left, int right){ IT l, r; get_overlap(left, right, l, r); if (l != r) { left = min(l->first, left); right = max(prev(r)->second, right); ranges.erase(l, r); } ranges[left] = right; } //O(logN) boolqueryRange(int left, int right){ IT l, r; get_overlap(left, right, l, r); if (l == r) returnfalse; return l->first <= left && l->second >= right; } //O(MlogN) m是erase的区间 voidremoveRange(int left, int right){ IT l, r; get_overlap(left, right, l, r); if (l == r) return;

int start = min(left, l->first); int end = max(right, prev(r)->second); ranges.erase(l, r); if (start < left) ranges[start] = left; if (end > right) ranges[right] = end; } private: map<int, int> ranges; //left ==> right typedefmap<int, int>::iterator IT; voidget_overlap(int left, int right, IT &l, IT &r){ //return [l, r) l = ranges.upper_bound(left); r = ranges.upper_bound(right); if (l != ranges.begin()) { if (prev(l)->second >= left) l--; } } };

There are n cars traveling at different speeds in the same direction along a one-lane road. You are given an array cars of length n, where cars[i] = [positioni, speedi] represents:

positioni is the distance between the ith car and the beginning of the road in meters. It is guaranteed that positioni < positioni+1. speedi is the initial speed of the ith car in meters per second. For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the slowest car in the fleet.

Return an array answer, where answer[i] is the time, in seconds, at which the ith car collides with the next car, or -1 if the car does not collide with the next car. Answers within 10-5 of the actual answers are accepted.

Example 1:

Input: cars = [[1,2],[2,1],[4,3],[7,2]] Output: [1.00000,-1.00000,3.00000,-1.00000] Explanation: After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s. Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Explanation: We return the node with value 2, colored in yellow in the diagram. The nodes coloured in blue are the deepest nodes of the tree. Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it. Example 2:

Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree. Example 3:

Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.

Constraints:

The number of nodes in the tree will be in the range [1, 500]. 0 <= Node.val <= 500 The values of the nodes in the tree are unique.

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

1 <= nums.length <= 5000 -104 <= nums[i] <= 10^4 nums is guaranteed to be rotated at some pivot. -104 <= target <= 104

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?