Huahua’s Tech Road

花花酱 LeetCode 1834. Single-Threaded CPU

By zxi on April 18, 2021

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Solution: Simulation w/ Sort + PQ

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getOrder(vector<vector<int>>& tasks) {

const int n = tasks.size();

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

tasks[i].push_back(i);

sort(begin(tasks), end(tasks)); // sort by enqueue_time;

vector<int> ans;

priority_queue<pair<int, int>> q; // {-processing_time, -index}

int i = 0;

long t = 0;

while (ans.size() != n) {

// Advance to next enqueue time if q is empty.

if (i < n && q.empty() && tasks[i][0] > t)

t = tasks[i][0];

// Enqueue all available tasks.

while (i < n && tasks[i][0] <= t) {

q.emplace(-tasks[i][1], -tasks[i][2]);

++i;

}

// Extra the top one.

t -= q.top().first;

ans.push_back(-q.top().second);

q.pop();

}

return ans;

}

};

花花酱 LeetCode 1833. Maximum Ice Cream Bars

By zxi on April 18, 2021

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the i^th ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

Solution: Greedy

Sort by price in ascending order, buy from the lowest price to the highest price.

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

C++

class Solution {

public:

int maxIceCream(vector<int>& costs, int coins) {

sort(begin(costs), end(costs));

int ans = 0;

for (int c : costs) {

if (c > coins) break;

coins -= c;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1832. Check if the Sentence Is Pangram

By zxi on April 18, 2021

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, returntrue if sentence is a pangram, or false otherwise.

Example 1:

Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.

Example 2:

Input: sentence = "leetcode"
Output: false

Constraints:

1 <= sentence.length <= 1000
sentence consists of lowercase English letters.

Solution: Hashset

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

C++

class Solution {

public:

bool checkIfPangram(string sentence) {

unordered_set<char> s;

for (char c : sentence)

s.insert(c);

return s.size() == 26;

}

};

Python3

class Solution:

def checkIfPangram(self, sentence: str) -> bool:

return len(set(sentence)) == 26

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

By zxi on April 18, 2021

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".

Example 2:

Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".

Example 3:

Input: s = "cdbea"
Output: 63

Example 4:

Input: s = "leetcodeleetcodeleetcode"
Output: 982157772

Constraints:

1 <= s.length <= 3000
s consists only of lowercase English letters.

Solution: Math

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

C++

constexpr int kMod = 1e9 + 7;

int64_t powm(int64_t b, int64_t p) {

int64_t ans = 1;

while (p) {

if (p & 1) ans = (ans * b) % kMod;

b = (b * b) % kMod;

p >>= 1;

}

return ans;

}

class Solution {

public:

int makeStringSorted(string s) {

const int n = s.length();

vector<int64_t> fact(n + 1, 1);

vector<int64_t> inv(n + 1, 1);

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

fact[i] = (fact[i - 1] * i) % kMod;

inv[i] = powm(fact[i], kMod - 2);

}

int64_t ans = 0;

vector<int> freq(26);

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

const int idx = s[i] - 'a';

++freq[idx];

int64_t cur = accumulate(begin(freq), begin(freq) + idx, 0ll) *

fact[n - i - 1] % kMod;

for (int f : freq)

cur = cur * inv[f] % kMod;

ans = (ans + cur) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1829. Maximum XOR for Each Query

By zxi on April 17, 2021

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

nums.length == n
1 <= n <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.

Solution: Prefix XOR

Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first

to remove nums[i], we just need to do s ^= nums[i]

We can always maximize the xor of s and k to (2^maxbit – 1)
k = (2 ^ maxbit – 1) ^ s

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {

const int t = (1 << maximumBit) - 1;

const int n = nums.size();

vector<int> ans(n);

int s = 0;

for (int x : nums) s ^= x;

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

ans[n - i - 1] = t ^ s;

s ^= nums[i];

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1834. Single-Threaded CPU

Solution: Simulation w/ Sort + PQ

C++

花花酱 LeetCode 1833. Maximum Ice Cream Bars

Solution: Greedy

C++

花花酱 LeetCode 1832. Check if the Sentence Is Pangram

Solution: Hashset

C++

Python3

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

Solution: Math

C++

花花酱 LeetCode 1829. Maximum XOR for Each Query

Solution: Prefix XOR

C++