Huahua's Tech Road

花花酱 LeetCode 1610. Maximum Number of Visible Points

By zxi on October 4, 2020

You are given an array points, an integer angle, and your location, where location = [pos_x, pos_y] and points[i] = [x_i, y_i] 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, pos_x and pos_y 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.

Constraints:

1 <= points.length <= 10⁵
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= pos_x, pos_y, x_i, y_i <= 10⁹

Solution: Sliding window

Sort all the points by angle, duplicate the points with angle + 2*PI to deal with turn around case.

maintain a window [l, r] such that angle[r] – angle[l] <= fov

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& o) {

int at_origin = 0;

vector<double> ps;

for (const auto& p : points)

if (p[0] == o[0] && p[1] == o[1])

++at_origin;

else

ps.push_back(atan2(p[1] - o[1], p[0] - o[0]));

sort(begin(ps), end(ps));

const int n = ps.size();

for (int i = 0; i < n; ++i)

ps.push_back(ps[i] + 2.0 * M_PI); // duplicate the array +2PI

int l = 0;

int ans = 0;

double fov = angle * M_PI / 180.0;

for (int r = 0; r < ps.size(); ++r) {

while (ps[r] - ps[l] > fov) ++l;

ans = max(ans, r - l + 1);

}

return ans + at_origin;

}

};

花花酱 LeetCode 1609. Even Odd Tree

By zxi on October 4, 2020

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Example 4:

Input: root = [1]
Output: true

Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: true

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Solution 1: DFS

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

bool isEvenOddTree(TreeNode* root) {

vector<int> vals;

function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return true;

if (vals.size() <= d)

vals.push_back(d % 2 == 0 ? -1 : INT_MAX);

int& val = vals[d];

if (d % 2 == 0)

if (root->val % 2 == 0 || root->val <= val) return false;

if (d % 2 == 1)

if (root->val % 2 == 1 || root->val >= val) return false;

val = root->val;

return dfs(root->left, d + 1) && dfs(root->right, d + 1);

};

return dfs(root, 0);

}

};

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

vals = {}

def dfs(root: TreeNode, d: int) -> bool:

if not root: return True

if d not in vals: vals[d] = 0 if d % 2 == 0 else 10**7

comp = int.__ge__ if d % 2 else int.__le__

if root.val % 2 == d % 2 or comp(root.val, vals[d]): return False

vals[d] = root.val

return dfs(root.left, d + 1) and dfs(root.right, d + 1)

return dfs(root, 0)

Solution 2: BFS

Time complexity: O(n)
Space complexity: O(n)

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

q = collections.deque([root])

odd = 1

while q:

prev = 0 if odd else 10**7

for _ in range(len(q)):

root = q.popleft()

if not root: continue

comp = int.__le__ if odd else int.__ge__

if root.val % 2 != odd or comp(root.val, prev): return False

prev = root.val

q += (root.left, root.right)

odd = 1 - odd

return True

花花酱 LeetCode 1608. Special Array With X Elements Greater Than or Equal X

By zxi on October 4, 2020

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Solution 1: Brute Force

Try all possible x from 0 to n.

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

for (int x = 0; x <= nums.size(); ++x)

if (x == count_if(begin(nums), end(nums), [x](int num) {

return num >= x; }))

return x;

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def specialArray(self, nums: List[int]) -> int:

for x in range(len(nums) + 1):

if x == sum([n >= x for n in nums]): return x

return -1

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(n)

f[i] := sum(nums >= i)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

const int n = nums.size();

vector<int> f(n + 2);

for (int v : nums) ++f[min(v, n)];

for (int i = n; i >= 0; --i)

if ((f[i] += f[i + 1]) == i) return i;

return -1;

}

};

花花酱 LeetCode 1606. Find Servers That Handled Most Number of Requests

By zxi on October 3, 2020

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

The i^th (0-indexed) request arrives.
If all servers are busy, the request is dropped (not handled at all).
If the (i % k)^th server is available, assign the request to that server.
Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the i^th server is busy, try to assign the request to the (i+1)^th server, then the (i+2)^th server, and so on.

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the i^th request, and another array load, where load[i] represents the load of the i^th request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Example 1:

Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
Output: [1] 
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.

Example 2:

Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.

Example 3:

Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.

Example 4:

Input: k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]
Output: [1]

Example 5:

Input: k = 1, arrival = [1], load = [1]
Output: [0]

Constraints:

1 <= k <= 10⁵
1 <= arrival.length, load.length <= 10⁵
arrival.length == load.length
1 <= arrival[i], load[i] <= 10⁹
arrival is strictly increasing.

Solution: Heap + TreeSet

Use a min heap to store the release time -> server.
Use a treeset to track the current available servers.
For reach request, check whether servers can be released at that time.

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {

priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> q; // {release_time, server}

set<int> servers;

vector<int> requests(k);

for (int i = 0; i < k; ++i)

servers.insert(i);

for (int i = 0; i < arrival.size(); ++i) {

const int t = arrival[i];

const int l = load[i];

// Release servers. O(logk) per pop()

while (!q.empty() && q.top().first <= t) {

servers.insert(q.top().second);

q.pop();

}

// Drop the request.

if (servers.empty()) continue;

// Find first avaiable one O(logk)

auto it = servers.lower_bound(i % k);

if (it == servers.end()) it = begin(servers);

const int idx = *it;

++requests[idx];

servers.erase(it);

q.emplace(t + l, idx);

}

const int max_req = *max_element(begin(requests), end(requests));

vector<int> ans;

for (int i = 0; i < k; ++i)

if (requests[i] == max_req) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 1605. Find Valid Matrix Given Row and Column Sums

By zxi on October 3, 2020

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the i^th row and colSum[j] is the sum of the elements of the j^th column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.

Return a 2D array representing any matrix that fulfills the requirements. It’s guaranteed that at least one matrix that fulfills the requirements exists.

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
         [1,7]]
Explanation:
0th row: 3 + 0 = 0 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
                             [3,5]]

Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
         [6,1,0],
         [2,0,8]]

Example 3:

Input: rowSum = [14,9], colSum = [6,9,8]
Output: [[0,9,5],
         [6,0,3]]

Example 4:

Input: rowSum = [1,0], colSum = [1]
Output: [[1],
         [0]]

Example 5:

Input: rowSum = [0], colSum = [0]
Output: [[0]]

Constraints:

1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10⁸
sum(rows) == sum(columns)

Solution: Greedy

Let a = min(row[i], col[j]), m[i][j] = a, row[i] -= a, col[j] -=a

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {

const int m = rowSum.size();

const int n = colSum.size();

vector<vector<int>> ans(m, vector<int>(n));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

ans[i][j] = min(rowSum[i], colSum[j]);

rowSum[i] -= ans[i][j];

colSum[j] -= ans[i][j];

}

return ans;

}

};