Huahua’s Tech Road

花花酱 LeetCode 2141. Maximum Running Time of N Computers

By zxi on January 30, 2022

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.

Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return the maximum number of minutes you can run all the n computers simultaneously.

Example 1:

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: 
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.

Example 2:

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation: 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.

Constraints:

1 <= n <= batteries.length <= 10⁵
1 <= batteries[i] <= 10⁹

Solution: Binary Search

Find the smallest L that we can not run, ans = L – 1.

For a guessing m, we check the total battery powers T = sum(min(m, batteries[i])), if T >= m * n, it means there is a way (doesn’t need to figure out how) to run n computers for m minutes by fully unitize those batteries.

Proof: If T >= m*n holds, there are two cases:

There are only n batteries, can not swap, but each of them has power >= m.
At least one of the batteries have power less than m, but there are more than n batteries and total power is sufficient, we can swap them with others.

Time complexity: O(Slogn) where S = sum(batteries)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long maxRunTime(int n, vector<int>& batteries) {

long long l = 0;

long long r = accumulate(begin(batteries), end(batteries), 0LL) + 1;

while (l < r) {

long long m = l + (r - l) / 2;

long long t = 0;

for (long long b : batteries)

t += min(m, b);

if (m * n > t) // smallest m that does not fit.

r = m;

else

l = m + 1;

}

return l - 1; // greatest m that fits.

}

};

花花酱 LeetCode 2140. Solving Questions With Brainpower

By zxi on January 30, 2022

You are given a 0-indexed 2D integer array questions where questions[i] = [points_i, brainpower_i].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you points_i points but you will be unable to solve each of the next brainpower_i questions. If you skip question i, you get to make the decision on the next question.

For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
- If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
- If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

Constraints:

1 <= questions.length <= 10⁵
questions[i].length == 2
1 <= points_i, brainpower_i <= 10⁵

Solution: DP

A more general version of 花花酱 LeetCode 198. House Robber

dp[i] := max points by solving questions[i:n].
dp[i] = max(dp[i + b + 1] + points[i] /* solve */ , dp[i+1] /* skip */)

ans = dp[0]

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

Python3

# Author: Huahua

class Solution:

def mostPoints(self, questions: List[List[int]]) -> int:

n = len(questions)

@cache

def dp(i: int) -> int:

if i >= n: return 0

p, b = questions[i]

return max(p + dp(i + b + 1), dp(i + 1))

return dp(0)

花花酱 LeetCode 2139. Minimum Moves to Reach Target Score

By zxi on January 30, 2022

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

Increment the current integer by one (i.e., x = x + 1).
Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation:Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:

1 <= target <= 10⁹
0 <= maxDoubles <= 100

Solution: Reverse + Greedy

If num is odd, decrement it by 1. Divide num by 2 until maxdoubles times. Apply decrementing until 1 reached.

ex1: 19 (dec)-> 18 (div1)-> 9 (dec) -> 8 (div2)-> 4 (dec)-> 3 (dec)-> 2 (dec)-> 1

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

C++

// Author: Huahua

class Solution {

public:

int minMoves(int target, int maxDoubles) {

int ans = 0;

while (maxDoubles-- && target != 1) {

if (target & 1)

--target, ++ans;

++ans;

target >>= 1;

}

ans += (target - 1);

return ans;

}

};

花花酱 LeetCode 2138. Divide a String Into Groups of Size k

By zxi on January 30, 2022

A string s can be partitioned into groups of size k using the following procedure:

The first group consists of the first k characters of the string, the second group consists of the next k characters of the string, and so on. Each character can be a part of exactly one group.
For the last group, if the string does not have k characters remaining, a character fill is used to complete the group.

Note that the partition is done so that after removing the fill character from the last group (if it exists) and concatenating all the groups in order, the resultant string should be s.

Given the string s, the size of each group k and the character fill, return a string array denoting the composition of every group s has been divided into, using the above procedure.

Example 1:

Input: s = "abcdefghi", k = 3, fill = "x"
Output: ["abc","def","ghi"]
Explanation:
The first 3 characters "abc" form the first group.
The next 3 characters "def" form the second group.
The last 3 characters "ghi" form the third group.
Since all groups can be completely filled by characters from the string, we do not need to use fill.
Thus, the groups formed are "abc", "def", and "ghi".

Example 2:

Input: s = "abcdefghij", k = 3, fill = "x"
Output: ["abc","def","ghi","jxx"]
Explanation:
Similar to the previous example, we are forming the first three groups "abc", "def", and "ghi".
For the last group, we can only use the character 'j' from the string. To complete this group, we add 'x' twice.
Thus, the 4 groups formed are "abc", "def", "ghi", and "jxx".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters only.
1 <= k <= 100
fill is a lowercase English letter.

Solution: Pre-fill

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

C++

// Author: Huahua

class Solution {

public:

vector<string> divideString(string s, int k, char fill) {

if (s.length() % k)

s.append(k - s.length() % k, fill);

vector<string> ans;

for (int i = 0; i < s.length(); i += k)

ans.push_back(s.substr(i, k));

return ans;

}

};

花花酱 LeetCode 2135. Count Words Obtained After Adding a Letter

By zxi on January 17, 2022

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

Append any lowercase letter that is not present in the string to its end.
- For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
Rearrange the letters of the new string in any arbitrary order.
- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

1 <= startWords.length, targetWords.length <= 5 * 10⁴
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Solution: Bitmask w/ Hashtable

Since there is no duplicate letters in each word, we can use a bitmask to represent a word.

Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.

E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.

Time complexity: O(n * 26^2)
Space complexity: O(n * 26)

C++

// Author: Huahua

class Solution {

public:

int wordCount(vector<string>& startWords, vector<string>& targetWords) {

unordered_set<int> s;

auto getKey = [](const string& s) {

return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); });

};

for (const string& w : startWords)

s.insert(getKey(w));

return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) {

const int key = getKey(w);

return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); });

});

}

};

Huahua's Tech Road

花花酱 LeetCode 2141. Maximum Running Time of N Computers

Solution: Binary Search

C++

花花酱 LeetCode 2140. Solving Questions With Brainpower

Solution: DP

Python3

花花酱 LeetCode 2139. Minimum Moves to Reach Target Score

Solution: Reverse + Greedy

C++

花花酱 LeetCode 2138. Divide a String Into Groups of Size k

Solution: Pre-fill

C++

花花酱 LeetCode 2135. Count Words Obtained After Adding a Letter

Solution: Bitmask w/ Hashtable

C++