Huahua’s Tech Road

花花酱 LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation

By zxi on August 8, 2021

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

Example 1:

Input: mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise to make mat equal target.

Example 2:

Input: mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
Output: false
Explanation: It is impossible to make mat equal to target by rotating mat.

Example 3:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
Output: true
Explanation: We can rotate mat 90 degrees clockwise two times to make mat equal target.

Constraints:

n == mat.length == target.length
n == mat[i].length == target[i].length
1 <= n <= 10
mat[i][j] and target[i][j] are either 0 or 1.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

bool findRotation(vector<vector<int>>& mat, vector<vector<int>>& target) {

const int n = mat.size();

auto rot = [n](vector<vector<int>>& mat) {

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

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

swap(mat[i][j], mat[j][i]);

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

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

swap(mat[i][j], mat[n - i - 1][j]);

return mat;

};

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

if (rot(mat) == target) return true;

return false;

}

};

花花酱 LeetCode 1884. Egg Drop With 2 Eggs and N Floors

By zxi on August 8, 2021

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what the value of f is.

Example 1:

Input: n = 2
Output: 2
Explanation: We can drop the first egg from floor 1 and the second egg from floor 2.
If the first egg breaks, we know that f = 0.
If the second egg breaks but the first egg didn't, we know that f = 1.
Otherwise, if both eggs survive, we know that f = 2.

Example 2:

Input: n = 100
Output: 14
Explanation: One optimal strategy is:
- Drop the 1st egg at floor 9. If it breaks, we know f is between 0 and 8. Drop the 2nd egg starting
  from floor 1 and going up one at a time to find f within 7 more drops. Total drops is 1 + 7 = 8.
- If the 1st egg does not break, drop the 1st egg again at floor 22. If it breaks, we know f is between 9
  and 21. Drop the 2nd egg starting from floor 10 and going up one at a time to find f within 12 more
  drops. Total drops is 2 + 12 = 14.
- If the 1st egg does not break again, follow a similar process dropping the 1st egg from floors 34, 45,
  55, 64, 72, 79, 85, 90, 94, 97, 99, and 100.
Regardless of the outcome, it takes at most 14 drops to determine f.

Constraints:

1 <= n <= 1000

Solution: Math

Time complexity: O(1)
Space complexity: O(1)

C++

class Solution {

public:

int twoEggDrop(int n) {

int ans{0};

while (ans < n) n -= ans++;

return ans;

}

};

花花酱 LeetCode 1883. Minimum Skips to Arrive at Meeting On Time

By zxi on August 8, 2021

You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the i^th road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.

For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly 2 hours, you do not need to wait.

However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.

For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.

Return the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

Example 1:

Input: dist = [1,3,2], speed = 4, hoursBefore = 2
Output: 1
Explanation:
Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.
You can skip the first rest to arrive in ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 hours.
Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.

Example 2:

Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10
Output: 2
Explanation:
Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.
You can skip the first and third rest to arrive in ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 hours.

Example 3:

Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10
Output: -1
Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.

Constraints:

n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 10⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

Solution: DP

Let dp[i][k] denote min (time*speed) to finish the i-th road with k rest.

dp[i][k] = min(dp[i – 1][k – 1] + dist[i] / speed * speed, # skip the rest,
(dp[i-1][k] + dist[i] + speed – 1) // speed * speed # rest

ans = argmin(dp[n][k] <= hours * speed)

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

C++

// Author: Huahua

class Solution {

public:

int minSkips(vector<int>& dist, int speed, int hoursBefore) {

const int n = dist.size();

const long total = accumulate(begin(dist), end(dist), 0L);

if (total > static_cast<long>(speed) * hoursBefore) return -1;

vector<vector<long>> dp(n + 1, vector<long>(n + 1, LONG_MAX / 2));

dp[0][0] = 0;

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

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

dp[i][k] = min((dp[i - 1][k] + dist[i - 1] + speed - 1) / speed * speed,

(k ? dp[i - 1][k - 1] + dist[i - 1] : LONG_MAX));

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

if (dp[n][k] <= static_cast<long>(speed) * hoursBefore) return k;

return -1;

}

};

Python3

// Author: Huahua

class Solution:

def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:

if sum(dist) > speed * hoursBefore: return -1

@cache

def dp(i: int, k: int):

if k < 0: return float('inf')

if i < 0: return 0

return min((dp(i - 1, k) + dist[i] + speed - 1) // speed * speed,

dp(i - 1, k - 1) + dist[i])

n = len(dist)

for k in range(n):

if dp(n - 1, k) <= speed * hoursBefore: return k

return -1

花花酱 LeetCode 1882. Process Tasks Using Servers

By zxi on August 8, 2021

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i^th server, and tasks[j] is the time needed to process the j^th task in seconds.

Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.

At second j, the j^th task is inserted into the queue (starting with the 0^th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index.

If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above.

A server that is assigned task j at second t will be free again at second t + tasks[j].

Build an array ans of length m, where ans[j] is the index of the server the j^th task will be assigned to.

Return the array ans.

Example 1:

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2:

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

Solution: Simulation / Priority Queue

Two priority queues, one for free servers, another for releasing events.
One FIFO queue for tasks to schedule.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {

const int n = servers.size();

const int m = tasks.size();

using P = pair<long, int>;

priority_queue<P, vector<P>, greater<P>> frees, release;

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

frees.emplace(servers[i], i);

vector<int> ans(m);

queue<int> q;

int l = 0;

long t = 0;

int count = 0;

while (count != m) {

// Release servers.

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

auto [rt, i] = release.top(); release.pop();

frees.emplace(servers[i], i);

}

// Enqueue tasks.

while (l < m && l <= t) q.push(l++);

// Schedule tasks.

while (q.size() && frees.size()) {

const int j = q.front(); q.pop();

auto [w, i] = frees.top(); frees.pop();

release.emplace(t + tasks[j], i);

ans[j] = i;

++count;

}

// Advance time.

if (frees.empty() && !release.empty()) {

t = release.top().first;

} else {

++t;

}

return ans;

}

};

花花酱 LeetCode 1881. Maximum Value after Insertion

By zxi on August 8, 2021

You are given a very large integer n, represented as a string, and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximize n‘s numerical value by inserting x anywhere in the decimal representation of n. You cannot insert x to the left of the negative sign.

For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.

Return a string representing the maximum value of n after the insertion.

Example 1:

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.

Example 2:

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.

Constraints:

1 <= n.length <= 10⁵
1 <= x <= 9
The digits in n are in the range [1, 9].
n is a valid representation of an integer.
In the case of a negative n, it will begin with '-'.

Solution: Greedy

Find the best position to insert x. For positive numbers, insert x to the first position i such that s[i] < x or s[i] > x for negatives.

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

C++

// Author: Huahua

class Solution {

public:

string maxValue(string n, int x) {

const int l = n.length();

if (n[0] == '-') {

for (int i = 1; i <= l; ++i)

if (i == l || n[i] - '0' > x)

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

} else {

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

if (i == l || x > n[i] - '0')

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

}

return "";

}

};

Huahua's Tech Road

花花酱 LeetCode 1886. Determine Whether Matrix Can Be Obtained By Rotation

Solution: Simulation

C++

花花酱 LeetCode 1884. Egg Drop With 2 Eggs and N Floors

Solution: Math

C++

花花酱 LeetCode 1883. Minimum Skips to Arrive at Meeting On Time

Solution: DP

C++

Python3

花花酱 LeetCode 1882. Process Tasks Using Servers

Solution: Simulation / Priority Queue

C++

花花酱 LeetCode 1881. Maximum Value after Insertion

Solution: Greedy

C++