Huahua’s Tech Road

花花酱 LeetCode 2558. Take Gifts From the Richest Pile

By zxi on February 4, 2023

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

Choose the pile with the maximum number of gifts.
If there is more than one pile with the maximum number of gifts, choose any.
Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

Constraints:

1 <= gifts.length <= 10³
1 <= gifts[i] <= 10⁹
1 <= k <= 10³

Solution: Priority Queue

Keep all numbers in a priority queue (max heap), each time extract the top one (largest one), then put num – sqrt(num) back to the queue.

Tip: We can early return if all the numbers become 1.

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

C++

// Author: Huahua

class Solution {

public:

long long pickGifts(vector<int>& gifts, int k) {

long long ans = accumulate(begin(gifts), end(gifts), 0LL);

priority_queue<int> q(begin(gifts), end(gifts));

while (k-- && q.top() > 1) {

int cur = q.top(); q.pop();

int next = sqrt(cur);

ans -= (cur - next);

q.push(next);

}

return ans;

}

};

花花酱 LeetCode 1061. Lexicographically Smallest Equivalent String

By zxi on January 14, 2023

You are given two strings of the same length s1 and s2 and a string baseStr.

We say s1[i] and s2[i] are equivalent characters.

For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'.

Equivalent characters follow the usual rules of any equivalence relation:

Reflexivity: 'a' == 'a'.
Symmetry: 'a' == 'b' implies 'b' == 'a'.
Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'.

For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr.

Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Example 1:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

Example 2:

Input: s1 = "hello", s2 = "world", baseStr = "hold"
Output: "hdld"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r].
So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld".

Example 3:

Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"

Output: "aauaaaaada"

Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada".

Constraints:

1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
s1, s2, and baseStr consist of lowercase English letters.

Solution: Union Find

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

C++

// Author: Huahua

class Solution {

public:

string smallestEquivalentString(string s1, string s2, string baseStr) {

vector<int> p(26);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (int i = 0; i < s1.length(); ++i) {

int r1 = find(s1[i] - 'a');

int r2 = find(s2[i] - 'a');

if (r2 < r1) swap(r1, r2);

p[r2] = r1;

}

string ans(baseStr);

for (int i = 0; i < baseStr.length(); ++i) {

ans[i] = find(baseStr[i] - 'a') + 'a';

}

return ans;

}

};

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

By zxi on December 31, 2022

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= nums1 < nums2 <= right .
nums1 and nums2 are both prime numbers.
nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Solution: Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all primes in range [0, right].

Check neighbor primes and find the best pair.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> closestPrimes(int left, int right) {

vector<int> primes(right + 1, 1);

primes[0] = primes[1] = 0;

for (int i = 2; i <= sqrt(right); ++i) {

if (!primes[i]) continue;

for (int x = i * i; x <= right; x += i)

primes[x] = 0;

}

vector<int> ans{-1,-1};

for (int i = left, last = -1, best = INT_MAX; i <= right; ++i) {

if (!primes[i]) continue;

if (last > 0 && i - last < best) {

best = i - last;

ans = {last, i};

}

last = i;

}

return ans;

}

};

花花酱 LeetCode 2477. Minimum Fuel Cost to Report to the Capital

By zxi on November 26, 2022

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [a_i, b_i] denotes that there exists a bidirectional road connecting cities a_i and b_i.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Example 1:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: 
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₂ goes directly to the capital with 1 liter of fuel.
- Representative₃ goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7
Explanation: 
- Representative₂ goes directly to city 3 with 1 liter of fuel.
- Representative₂ and representative₃ go together to city 1 with 1 liter of fuel.
- Representative₂ and representative₃ go together to the capital with 1 liter of fuel.
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₅ goes directly to the capital with 1 liter of fuel.
- Representative₆ goes directly to city 4 with 1 liter of fuel.
- Representative₄ and representative₆ go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

Input: roads = [], seats = 1
Output: 0
Explanation: No representatives need to travel to the capital city.

Constraints:

1 <= n <= 10⁵
roads.length == n - 1
roads[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
roads represents a valid tree.
1 <= seats <= 10⁵

Solution: Greedy + DFS

To reach the minimum cost, we must share cars if possible, say X reps from children nodes to an intermediate node u on the way towards capital 0. Then they all changes cars at node u, and we need (X + 1) // seats cars/fuel from u to 0.

We use DFS to count # of reps at each node u while accumulating the total cost.

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

C++

// Author: Huahua

class Solution {

public:

long long minimumFuelCost(vector<vector<int>>& roads, int seats) {

long long ans = 0;

vector<vector<int>> g(roads.size() + 1);

for (const vector<int>& r : roads) {

g[r[0]].push_back(r[1]);

g[r[1]].push_back(r[0]);

}

// Returns total # of children of u.

function<int(int, int)> dfs = [&](int u, int p, int rep = 1) {

for (int v : g[u])

if (v != p) rep += dfs(v, u);

if (u) ans += (rep + seats - 1) / seats;

return rep;

};

dfs(0, -1);

return ans;

}

};

花花酱 LeetCode 2469. Convert the Temperature

By zxi on November 22, 2022

You are given a non-negative floating point number rounded to two decimal places celsius, that denotes the temperature in Celsius.

You should convert Celsius into Kelvin and Fahrenheit and return it as an array ans = [kelvin, fahrenheit].

Return the array ans. Answers within 10^-5 of the actual answer will be accepted.

Note that:

Kelvin = Celsius + 273.15
Fahrenheit = Celsius * 1.80 + 32.00

Example 1:

Input: celsius = 36.50
Output: [309.65000,97.70000]
Explanation: Temperature at 36.50 Celsius converted in Kelvin is 309.65 and converted in Fahrenheit is 97.70.

Example 2:

Input: celsius = 122.11
Output: [395.26000,251.79800]
Explanation: Temperature at 122.11 Celsius converted in Kelvin is 395.26 and converted in Fahrenheit is 251.798.

Constraints:

0 <= celsius <= 1000

Solution: Follow the formulas

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

C++

// Author: Huahua

class Solution {

public:

vector<double> convertTemperature(double celsius) {

return {celsius + 273.15, celsius * 1.80 + 32.00};

}

};

Huahua's Tech Road

花花酱 LeetCode 2558. Take Gifts From the Richest Pile

Solution: Priority Queue

C++

花花酱 LeetCode 1061. Lexicographically Smallest Equivalent String

Solution: Union Find

C++

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

Solution: Sieve of Eratosthenes

C++

花花酱 LeetCode 2477. Minimum Fuel Cost to Report to the Capital

Solution: Greedy + DFS

C++

花花酱 LeetCode 2469. Convert the Temperature

Solution: Follow the formulas

C++