Huahua’s Tech Road

花花酱 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 "";

}

};

花花酱 LeetCode 1880. Check if Word Equals Summation of Two Words

By zxi on August 8, 2021

The letter value of a letter is its position in the alphabet starting from 0 (i.e. 'a' -> 0, 'b' -> 1, 'c' -> 2, etc.).

The numerical value of some string of lowercase English letters s is the concatenation of the letter values of each letter in s, which is then converted into an integer.

For example, if s = "acb", we concatenate each letter’s letter value, resulting in "021". After converting it, we get 21.

You are given three strings firstWord, secondWord, and targetWord, each consisting of lowercase English letters 'a' through 'j' inclusive.

Return true if the summation of the numerical values of firstWord and secondWord equals the numerical value of targetWord, or false otherwise.

Example 1:

Input: firstWord = "acb", secondWord = "cba", targetWord = "cdb"
Output: true
Explanation:
The numerical value of firstWord is "acb" -> "021" -> 21.
The numerical value of secondWord is "cba" -> "210" -> 210.
The numerical value of targetWord is "cdb" -> "231" -> 231.
We return true because 21 + 210 == 231.

Example 2:

Input: firstWord = "aaa", secondWord = "a", targetWord = "aab"
Output: false
Explanation: 
The numerical value of firstWord is "aaa" -> "000" -> 0.
The numerical value of secondWord is "a" -> "0" -> 0.
The numerical value of targetWord is "aab" -> "001" -> 1.
We return false because 0 + 0 != 1.

Example 3:

Input: firstWord = "aaa", secondWord = "a", targetWord = "aaaa"
Output: true
Explanation: 
The numerical value of firstWord is "aaa" -> "000" -> 0.
The numerical value of secondWord is "a" -> "0" -> 0.
The numerical value of targetWord is "aaaa" -> "0000" -> 0.
We return true because 0 + 0 == 0.

Constraints:

1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord, secondWord, and targetWord consist of lowercase English letters from 'a' to 'j' inclusive.

Solution: Brute Force

Tips: Write a reusable function to compute the score of a word.

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

C++

// Author: Huahua

class Solution {

public:

bool isSumEqual(string firstWord, string secondWord, string targetWord) {

auto score = [](string_view s) {

int ans = 0;

for (char c : s)

ans = ans * 10 + (c - 'a');

return ans;

};

return score(firstWord) + score(secondWord) == score(targetWord);

}

};

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

By zxi on August 7, 2021

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Solution: DP / Permutation to combination

dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].

Time complexity: O(n*2ⁿ)
Space complexity: O(2ⁿ)

C++

// Author: Huahua

class Solution {

public:

int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {

const int n = nums1.size();

vector<int> dp(1 << n, INT_MAX);

dp[0] = 0;

for (int s = 0; s < 1 << n; ++s) {

int index = __builtin_popcount(s);

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

if (s & (1 << i)) continue;

dp[s | (1 << i)] = min(dp[s | (1 << i)],

dp[s] + (nums1[index] ^ nums2[i]));

}

return dp.back();

}

};

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

By zxi on August 6, 2021

You are given an m x n integer matrix grid.

A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum:

Note that the rhombus can have an area of 0, which is depicted by the purple rhombus in the bottom right corner.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Example 1:

Input: grid = [[3,4,5,1,3],[3,3,4,2,3],[20,30,200,40,10],[1,5,5,4,1],[4,3,2,2,5]]
Output: [228,216,211]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 20 + 3 + 200 + 5 = 228
- Red: 200 + 2 + 10 + 4 = 216
- Green: 5 + 200 + 4 + 2 = 211

Example 2:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [20,9,8]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.
- Blue: 4 + 2 + 6 + 8 = 20
- Red: 9 (area 0 rhombus in the bottom right corner)
- Green: 8 (area 0 rhombus in the bottom middle)

Example 3:

Input: grid = [[7,7,7]]
Output: [7]
Explanation: All three possible rhombus sums are the same, so return [7].

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 10⁵

Solution: Brute Force

Just find all Rhombus…

Time complexity: O(mn*min(n,m)²)
Space complexity: O(mn*min(n,m)²)

C++

// Author: Huahua

class Solution {

public:

vector<int> getBiggestThree(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> ans;

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

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

ans.push_back(grid[i][j]);

for (int a = 2; a <= min(m, n); ++a)

for (int cy = a - 1; cy + a <= m; ++cy)

for (int cx = a - 1; cx + a <= n; ++cx) {

int s = grid[cy][cx - a + 1]

+ grid[cy][cx + a - 1]

+ grid[cy + a - 1][cx]

+ grid[cy - a + 1][cx];

for (int i = 1; i < a - 1; ++i)

s += grid[cy - i][cx - a + i + 1]

+ grid[cy - i][cx + a - i - 1]

+ grid[cy + i][cx - a + i + 1]

+ grid[cy + i][cx + a - i - 1];

ans.push_back(s);

}

sort(rbegin(ans), rend(ans));

vector<int> output;

for (int x : ans) {

if (output.empty() || output.back() != x)

output.push_back(x);

if (output.size() == 3) break;

}

return output;

}

};

Huahua's Tech Road

花花酱 LeetCode 1882. Process Tasks Using Servers

Solution: Simulation / Priority Queue

C++

花花酱 LeetCode 1881. Maximum Value after Insertion

Solution: Greedy

C++

花花酱 LeetCode 1880. Check if Word Equals Summation of Two Words

Solution: Brute Force

C++

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

Solution: DP / Permutation to combination

C++

花花酱 LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid

Solution: Brute Force

C++