Posts tagged as “greedy”

花花酱 LeetCode 1405. Longest Happy String

By zxi on April 5, 2020

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

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

C++

// Author: Huahua

class Solution {

public:

string longestDiverseString(int a, int b, int c) {

const int total = a + b + c;

vector<int> f{a, b, c};

vector<int> l{0, 0, 0};

string ans;

for (int _ = 0; _ < total; ++_)

for (int i = 0; i < 3; ++i) {

const int j = (i + 1) % 3;

const int k = (i + 2) % 3;

if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2)

|| (f[i] > 0 && (l[j] == 2 || l[k] == 2))) {

ans += 'a' + i;

++l[i];

--f[i];

l[j] = l[k] = 0;

break;

}

return ans;

}

};

花花酱 LeetCode 1403. Minimum Subsequence in Non-Increasing Order

By zxi on April 4, 2020

Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.

If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.

Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.

Example 1:

Input: nums = [4,3,10,9,8]
Output: [10,9] 
Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included, however, the subsequence [10,9] has the maximum total sum of its elements.

Example 2:

Input: nums = [4,4,7,6,7]
Output: [7,7,6] 
Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to returned in non-decreasing order.

Example 3:

Input: nums = [6]
Output: [6]

Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 100

Solution: Greedy

Sort the elements in reverse order, pick the largest elements until their sum is greater than the sum of the left elements or total / 2.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> minSubsequence(vector<int>& nums) {

sort(rbegin(nums), rend(nums));

int total = accumulate(begin(nums), end(nums), 0);

vector<int> ans;

int sum = 0;

for (int v : nums) {

sum += v;

ans.push_back(v);

if (sum > total / 2) break;

}

return ans;

}

};

花花酱 LeetCode 1386. Cinema Seat Allocation

By zxi on March 22, 2020

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i]=[3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person families you can allocate on the cinema seats. A four-person family occupies fours seats in one row, that are next to each other. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case, exactly two people have to sit on each side of the aisle.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four families, where seats mark with blue are already reserved and contiguous seats mark with orange are for one family.

Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Constraints:

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

Solution: HashTable + Greedy

if both seat[2~5] seat[6~9] are empty, seat two groups.
if any of seat[2~5] seat[4~7] seat[6~9] is empty seat one group.
if there is no one sit in a row, seat two groups.

Time complexity: O(|reservedSeats|)
Space complexity: O(|rows|)

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {

unordered_map<int, int> rows;

for (auto& seat : reservedSeats)

rows[seat[0]] |= 1 << (seat[1] - 1);

int ans = (n - rows.size()) * 2;

for (const auto& [idx, row] : rows) {

int s2 = row & 0b0000011110;

int s4 = row & 0b0001111000;

int s6 = row & 0b0111100000;

if (s2 == 0 && s6 == 0)

ans += 2;

else if (s2 == 0 || s4 == 0 || s6 == 0)

ans += 1;

}

return ans;

}

};

花花酱 LeetCode 1383. Maximum Performance of a Team

By zxi on March 21, 2020

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n

Solution: Greedy + Sliding Window

Sort engineers by their efficiency in descending order.
For each window of K engineers (we can have less than K people in the first k-1 windows), ans is sum(speed) * min(efficiency).

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

C++

// Author: Huahua

class Solution {

public:

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {

vector<pair<int, int>> es;

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

es.push_back({efficiency[i], speed[i]});

sort(rbegin(es), rend(es));

priority_queue<int, vector<int>, greater<int>> q;

long sum = 0;

long ans = 0;

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

if (i >= k) {

sum -= q.top();

q.pop();

}

sum += es[i].second;

q.push(es[i].second);

ans = max(ans, sum * es[i].first);

}

return ans % static_cast<int>(1e9 + 7);

}

};

Python3

# Author: Huahua

class Solution:

def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:

speeds = 0

ans = 0

q = []

for e, s in sorted(zip(efficiency, speed), reverse=True):

if len(q) >= k:

speeds -= heapq.heappop(q)

speeds += s

heapq.heappush(q, s)

ans = max(ans, speeds * e)

return ans % (10**9 + 7)

花花酱 LeetCode 1363. Largest Multiple of Three

By zxi on February 23, 2020

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0"

Constraints:

1 <= digits.length <= 10^4
0 <= digits[i] <= 9
The returning answer must not contain unnecessary leading zeros.

Solution: Greedy + Math + Counting sort

Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0

Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output

C++

// Author: Huahua

class Solution {

public:

string largestMultipleOfThree(vector<int>& digits) {

vector<int> c(10);

for (int d : digits) ++c[d];

auto getNum = [&](const vector<int>& ds) {

for (int d : ds) --c[d];

string ans;

for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d);

ans.append(ans.empty() ? min(1, c[0]) : c[0], '0');

return ans;

};

const int r = accumulate(begin(digits), end(digits), 0) % 3;

vector<vector<int>> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}};

// Use all digitis.

if (r == 0) return getNum({});

// Remove one among {1, 4, 7}, {2, 5, 8}

for (int d : rs[r]) if (c[d]) return getNum({d});

// Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1)

for (int d1 : rs[3 - r])

for (int d2 : rs[3 - r])

if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2])

return getNum({d1, d2});

return "";

}

};

Python3

# Author: Huahua

class Solution:

def largestMultipleOfThree(self, digits: List[int]) -> str:

c = collections.Counter(digits)

def getNum(ds):

ans = []

for d in ds: c[d] -= 1

for d in range(9, 0, -1): ans += [d] * c[d]

ans += [0] * min(1 if not ans else c[0], c[0])

return ''.join(map(str, ans))

rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]

r = sum(digits) % 3

if r == 0: return getNum([])

for d in rs[r]:

if c[d] > 0: return getNum([d])

for d1, d2 in zip(rs[3 - r], rs[3 - r]):

if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]:

return getNum([d1, d2])

return ""