Huahua’s Tech Road

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

By zxi on April 2, 2022

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

Solution: Binary Search

Find the smallest L s.t. we can allocate candies to less than k children.

ans = L – 1.

Time complexity: O(nlogm) where n is number of piles, m is sum(candies) / k.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumCandies(vector<int>& candies, long long k) {

long long total = accumulate(begin(candies), end(candies), 0LL);

long long l = 1;

long long r = total / k + 1;

while (l < r) {

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

long long c = 0;

for (int pile : candies)

c += pile / m;

if (c < k)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 2225. Find Players With Zero or One Losses

By zxi on April 2, 2022

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints:

1 <= matches.length <= 10⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
All matches[i] are unique.

Solution: Hashtable

Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.

Time complexity: O(m), m = # of matches
Space complexity: O(n), n = # of players

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findWinners(vector<vector<int>>& matches) {

unordered_map<int, int> m;

for (const auto& match : matches) {

m[match[0]]; // create an entry for the winner.

++m[match[1]];

}

vector<vector<int>> ans(2);

for (const auto& [player, loses] : m)

if (loses <= 1) ans[loses].push_back(player);

sort(begin(ans[0]), end(ans[0]));

sort(begin(ans[1]), end(ans[1]));

return ans;

}

};

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

By zxi on April 2, 2022

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

current and correct are in the format "HH:MM"
current <= correct

Solution: Greedy

Start with 60, then 15, 5 and finally increase 1 minute a time.

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

C++

// Author: Huahua

class Solution {

public:

int convertTime(string current, string correct) {

auto getMinute = [](string_view t) {

return (t[0] - '0') * 10 * 60

+ (t[1] - '0') * 60

+ (t[3] - '0') * 10

+ (t[4] - '0');

};

int t1 = getMinute(current);

int t2 = getMinute(correct);

int ans = 0;

for (int d : {60, 15, 5, 1})

while (t2 - t1 >= d) {

++ans;

t1 += d;

}

return ans;

}

};

花花酱 LeetCode 2223. Sum of Scores of Built Strings

By zxi on April 2, 2022

You are building a string s of length n one character at a time, prepending each new character to the front of the string. The strings are labeled from 1 to n, where the string with length i is labeled s_i.

For example, for s = "abaca", s₁ == "a", s₂ == "ca", s₃ == "aca", etc.

The score of s_i is the length of the longest common prefix between s_i and s_n (Note that s == s_n).

Given the final string s, return the sum of the score of every s_i.

Example 1:

Input: s = "babab"
Output: 9
Explanation:
For s₁ == "b", the longest common prefix is "b" which has a score of 1.
For s₂ == "ab", there is no common prefix so the score is 0.
For s₃ == "bab", the longest common prefix is "bab" which has a score of 3.
For s₄ == "abab", there is no common prefix so the score is 0.
For s₅ == "babab", the longest common prefix is "babab" which has a score of 5.
The sum of the scores is 1 + 0 + 3 + 0 + 5 = 9, so we return 9.

Example 2:

Input: s = "azbazbzaz"
Output: 14
Explanation: 
For s₂ == "az", the longest common prefix is "az" which has a score of 2.
For s₆ == "azbzaz", the longest common prefix is "azb" which has a score of 3.
For s₉ == "azbazbzaz", the longest common prefix is "azbazbzaz" which has a score of 9.
For all other s_i, the score is 0.
The sum of the scores is 2 + 3 + 9 = 14, so we return 14.

Constraints:

1 <= s.length <= 10⁵
s consists of lowercase English letters.

Solution: Z-Function

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

C++

// Author: Huahua

class Solution {

public:

long long sumScores(string s) {

auto zFunc = [](string_view s) {

const int n = s.length();

vector<long long> z(n);

for (long long i = 1, l = 0, r = 0; i < n; ++i) {

if (i <= r)

z[i] = min(r - i + 1, z[i - l]);

while (i + z[i] < n && s[z[i]] == s[i + z[i]])

++z[i];

if (i + z[i] - 1 > r) {

l = i;

r = i + z[i] - 1;

}

return accumulate(begin(z), end(z), 0LL);

};

return zFunc(s) + s.length();

}

};

花花酱 LeetCode 2222. Number of Ways to Select Buildings

By zxi on April 2, 2022

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

s[i] = '0' denotes that the i^th building is an office and
s[i] = '1' denotes that the i^th building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

For example, given s = "001101", we cannot select the 1^st, 3^rd, and 5^th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints:

3 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Solution: DP

The brute force solution will take O(n³) which will lead to TLE.

Since the only two valid cases are “010” and “101”.

We just need to count how many 0s and 1s, thus we can count 01s and 10s and finally 010s and 101s.

C++

// Author: Huahua

class Solution {

public:

long long numberOfWays(string s) {

long long c0 = 0, c1 = 0, c01 = 0, c10 = 0, c101 = 0, c010 = 0;

for (char c : s) {

if (c == '0') {

++c0;

c10 += c1;

c010 += c01;

} else {

++c1;

c01 += c0;

c101 += c10;

}

return c101 + c010;

}

};

Huahua's Tech Road

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

Solution: Binary Search

C++

花花酱 LeetCode 2225. Find Players With Zero or One Losses

Solution: Hashtable

C++

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

Solution: Greedy

C++

花花酱 LeetCode 2223. Sum of Scores of Built Strings

Solution: Z-Function

C++

花花酱 LeetCode 2222. Number of Ways to Select Buildings

Solution: DP

C++