Posts tagged as “greedy”

花花酱 LeetCode 1953. Maximum Number of Weeks for Which You Can Work

By zxi on December 31, 2021

There are n projects numbered from 0 to n - 1. You are given an integer array milestones where each milestones[i] denotes the number of milestones the i^th project has.

You can work on the projects following these two rules:

Every week, you will finish exactly one milestone of one project. You must work every week.
You cannot work on two milestones from the same project for two consecutive weeks.

Once all the milestones of all the projects are finished, or if the only milestones that you can work on will cause you to violate the above rules, you will stop working. Note that you may not be able to finish every project’s milestones due to these constraints.

Return the maximum number of weeks you would be able to work on the projects without violating the rules mentioned above.

Example 1:

Input: milestones = [1,2,3]
Output: 6
Explanation: One possible scenario is:
- During the 1^st week, you will work on a milestone of project 0.
- During the 2^nd week, you will work on a milestone of project 2.
- During the 3^rd week, you will work on a milestone of project 1.
- During the 4^th week, you will work on a milestone of project 2.
- During the 5^th week, you will work on a milestone of project 1.
- During the 6^th week, you will work on a milestone of project 2.
The total number of weeks is 6.

Example 2:

Input: milestones = [5,2,1]
Output: 7
Explanation: One possible scenario is:
- During the 1^st week, you will work on a milestone of project 0.
- During the 2^nd week, you will work on a milestone of project 1.
- During the 3^rd week, you will work on a milestone of project 0.
- During the 4^th week, you will work on a milestone of project 1.
- During the 5^th week, you will work on a milestone of project 0.
- During the 6^th week, you will work on a milestone of project 2.
- During the 7^th week, you will work on a milestone of project 0.
The total number of weeks is 7.
Note that you cannot work on the last milestone of project 0 on 8^th week because it would violate the rules.
Thus, one milestone in project 0 will remain unfinished.

Constraints:

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

Solution: Math

Let x be the longest project.

Case 1: x > sum of the rest.

Obviously, we cannot finish it.
The best we can do is : [x, a}, {x, b}, {x, c}, …., {x, z}, x.
Ans = 2 * rest + 1

Case 2: x <= sum of the rest.

We can finish all the projects by alternating them properly.
Ans = sum

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

C++

// Author: Huahua

class Solution {

public:

long long numberOfWeeks(vector<int>& milestones) {

long long sum = accumulate(begin(milestones), end(milestones), 0LL);

long long longest = *max_element(begin(milestones), end(milestones));

return min(sum, 2 * (sum - longest) + 1);

}

};

花花酱 LeetCode 1946. Largest Number After Mutating Substring

By zxi on December 31, 2021

You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d maps to digit change[d].

You may choose to mutate a single substring of num. To mutate a substring, replace each digit num[i] with the digit it maps to in change (i.e. replace num[i] with change[num[i]]).

Return a string representing the largest possible integer after mutating (or choosing not to) a single substring of num.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8]
Output: "832"
Explanation: Replace the substring "1":
- 1 maps to change[1] = 8.
Thus, "132" becomes "832".
"832" is the largest number that can be created, so return it.

Example 2:

Input: num = "021", change = [9,4,3,5,7,2,1,9,0,6]
Output: "934"
Explanation: Replace the substring "021":
- 0 maps to change[0] = 9.
- 2 maps to change[2] = 3.
- 1 maps to change[1] = 4.
Thus, "021" becomes "934".
"934" is the largest number that can be created, so return it.

Example 3:

Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4]
Output: "5"
Explanation: "5" is already the largest number that can be created, so return it.

Constraints:

1 <= num.length <= 10⁵
num consists of only digits 0-9.
change.length == 10
0 <= change[d] <= 9

Solution: Greedy

Find the first digit that is less equal to the mutated one as the start of the substring, keep replacing as long as mutated >= current.

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

C++

// Author: Huahua

class Solution {

public:

string maximumNumber(string num, vector<int>& change) {

const int n = num.size();

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

if (num[i] - '0' < change[num[i] - '0']) {

for (int j = i; j < n && num[j] - '0' <= change[num[j] - '0']; ++j)

num[j] = change[num[j] - '0'] + '0';

break;

}

return num;

}

};

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

By zxi on December 25, 2021

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Solution: Greedy

Sort by arrival time, and see how many we can eliminate.

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

C++

// Author: Huahua

class Solution {

public:

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {

const int n = dist.size();

vector<int> t(n);

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

t[i] = (dist[i] + speed[i] - 1) / speed[i];

sort(begin(t), end(t));

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

if (t[i] <= i) return i;

return n;

}

};

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

By zxi on December 24, 2021

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.

Constraints:

4 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Solution: Greedy

Since all the numbers are positive, we just need to find the largest two numbers as the first pair and smallest two numbers are the second pair.

Time complexity: O(nlogn) / sorting, O(n) / finding min/max elements.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProductDifference(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];

}

};

Python3

# Author: Huahua

class Solution:

def maxProductDifference(self, nums: List[int]) -> int:

nums.sort()

return nums[-1] * nums[-2] - nums[0] * nums[1]

花花酱 LeetCode 179. Largest Number

By zxi on November 28, 2021

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Example 3:

Input: nums = [1]
Output: "1"

Example 4:

Input: nums = [10]
Output: "10"

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 10⁹

Solution: Greedy

Sort numbers by lexical order.
e.g. 9 > 666

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

C++

// Author: Huahua

class Solution {

public:

string largestNumber(vector<int> &num) {

vector<string> s;

for (int x : num)

s.emplace_back(to_string(x));

sort(begin(s), end(s), [](const auto& s1, const auto& s2) {

return s1 + s2 > s2 + s1;

});

if (s[0] == "0") return "0";

string ans;

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

ans += s[i];

return ans;

}

};