Huahua’s Tech Road

花花酱 LeetCode 2187. Minimum Time to Complete Trips

By zxi on February 27, 2022

You are given an array time where time[i] denotes the time taken by the i^th bus to complete one trip.

Each bus can make multiple trips successively; that is, the next trip can start immediately after completing the current trip. Also, each bus operates independently; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, the number of trips completed by each bus are [1,0,0]. 
  The total number of trips completed is 1 + 0 + 0 = 1.
- At time t = 2, the number of trips completed by each bus are [2,1,0]. 
  The total number of trips completed is 2 + 1 + 0 = 3.
- At time t = 3, the number of trips completed by each bus are [3,1,1]. 
  The total number of trips completed is 3 + 1 + 1 = 5.
So the minimum time needed for all buses to complete at least 5 trips is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it will complete its first trip at t = 2.
So the minimum time needed to complete 1 trip is 2.

Constraints:

1 <= time.length <= 10⁵
1 <= time[i], totalTrips <= 10⁷

Solution: Binary Search

Find the smallest t s.t. trips >= totalTrips.

Time complexity: O(nlogm), where m ~= 1e15
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long minimumTime(vector<int>& time, int totalTrips) {

long long l = 1;

long long r = 1e15;

while (l < r) {

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

long long trips = 0;

for (int t : time) {

trips += m / t;

if (trips >= totalTrips) break;

}

if (trips >= totalTrips)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 2186. Minimum Number of Steps to Make Two Strings Anagram II

By zxi on February 26, 2022

You are given two strings s and t. In one step, you can append any character to either s or t.

Return the minimum number of steps to make s and t anagrams of each other.

An anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = "leetcode", t = "coats"
Output: 7
Explanation: 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Example 2:

Input: s = "night", t = "thing"
Output: 0
Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.

Constraints:

1 <= s.length, t.length <= 2 * 10⁵
s and t consist of lowercase English letters.

Solution: Hashtable

Record the frequency difference of each letter.

Ans = sum(diff)

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

C++

// Author: Huahua

class Solution {

public:

int minSteps(string s, string t) {

vector<int> diff(26);

for (char c : s) ++diff[c - 'a'];

for (char c : t) --diff[c - 'a'];

int ans = 0;

for (int d : diff)

ans += abs(d);

return ans;

}

};

花花酱 LeetCode 2185. Counting Words With a Given Prefix

By zxi on February 26, 2022

You are given an array of strings words and a string pref.

Return the number of strings in words that contain pref as a prefix.

A prefix of a string s is any leading contiguous substring of s.

Example 1:

Input: words = ["pay","attention","practice","attend"], pref = "at"
Output: 2
Explanation: The 2 strings that contain "at" as a prefix are: "attention" and "attend".

Example 2:

Input: words = ["leetcode","win","loops","success"], pref = "code"
Output: 0
Explanation: There are no strings that contain "code" as a prefix.

Constraints:

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] and pref consist of lowercase English letters.

Solution: Straight forward

We can use std::count_if and std::string::find.

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

C++

// Author: Huahua

class Solution {

public:

int prefixCount(vector<string>& words, string pref) {

return count_if(begin(words), end(words), [&](const string& w) {

return w.find(pref) == 0;

});

}

};

花花酱 LeetCode 2169. Count Operations to Obtain Zero

By zxi on February 13, 2022

You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

0 <= num1, num2 <= 10⁵

Solution 1: Simulation

Time complexity: O(max(n,m) / min(n, m))
Space complexity: O(1)

No code

Solution 2: Simualtion + Math

For the case of 100, 3
100 – 3 = 97
97 – 3 = 94
…
4 – 3 = 1
Swap
3 – 1 = 2
2 – 1 = 1
1 – 1 = 0
It takes 36 steps.

We can do 100 / 3 to skip 33 steps
100 %= 3 = 1
3 / 1 = 3 to skip 3 steps
3 %= 1 = 0
total is 33 + 3 = 36.

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

C++

// Author: Huahua

class Solution {

public:

int countOperations(int num1, int num2) {

int ans = 0;

while (num1 && num2) {

if (num1 < num2) swap(num1, num2);

ans += num1 / num2;

num1 %= num2;

}

return ans;

}

};

花花酱 LeetCode 2170. Minimum Operations to Make the Array Alternating

By zxi on February 13, 2022

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

nums[i - 2] == nums[i], where 2 <= i <= n - 1.
nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Solution: Greedy

Count and sort the frequency of numbers at odd and even positions.

Case 1: top frequency numbers are different, change the rest of numbers to them respectively.
Case 2: top frequency numbers are the same, compare top 1 odd + top 2 even vs top 2 even + top 1 odd.

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

C++

// Author: Huahua

class Solution {

public:

int minimumOperations(vector<int>& nums) {

const int n = nums.size();

if (n == 1) return 0;

unordered_map<int, int> odd, even;

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

((i & 1 ? odd : even)[nums[i]])++;

vector<pair<int, int>> o, e;

for (const auto [k, v] : odd)

o.emplace_back(v, k);

for (const auto [k, v] : even)

e.emplace_back(v, k);

sort(rbegin(o), rend(o));

sort(rbegin(e), rend(e));

if (o[0].second != e[0].second)

return n - o[0].first - e[0].first;

int mo = o[0].first + (e.size() > 1 ? e[1].first : 0);

int me = e[0].first + (o.size() > 1 ? o[1].first : 0);

return n - max(mo, me);

}

};

Huahua's Tech Road

花花酱 LeetCode 2187. Minimum Time to Complete Trips

Solution: Binary Search

C++

花花酱 LeetCode 2186. Minimum Number of Steps to Make Two Strings Anagram II

Solution: Hashtable

C++

花花酱 LeetCode 2185. Counting Words With a Given Prefix

Solution: Straight forward

C++

花花酱 LeetCode 2169. Count Operations to Obtain Zero

Solution 1: Simulation

Solution 2: Simualtion + Math

C++

花花酱 LeetCode 2170. Minimum Operations to Make the Array Alternating

Solution: Greedy

C++