Posts tagged as “greedy”

花花酱 LeetCode 646. Maximum Length of Pair Chain

By zxi on April 9, 2025

这题我选DP，因为不需要证明，直接干就行了。

方法1: DP

首先还是需要对pairs的right进行排序。一方面是为了方便chaining，另一方面是可以去重。

然后定义 dp[i] := 以pairs[i]作为结尾，最长的序列的长度。

状态转移：dp[i] = max(dp[j] + 1) where pairs[i].left > pairs[j].right and 0 < j < i.

解释：对于pairs[i]，找一个最优的pairs[j]，满足pairs[i].left > pairs[j].right，这样我就可以把pairs[i]追加到以pairs[j]结尾的最长序列后面了，长度+1。

边检条件：dp[0:n] = 1，每个pair以自己作为序列的最后元素，长度为1。

时间复杂度：O(n²)
空间复杂度：O(n)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

const int n = pairs.size();

vector<int> dp(n, 1);

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

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

if (pairs[i][0] > pairs[j][1])

dp[i] = max(dp[i], dp[j] + 1);

return *max_element(begin(dp), end(dp));

}

};

方法2: 贪心

和DP一样，对数据进行排序。

每当我看到 cur.left > prev.right，那么就直接把cur接在prev后面。我们需要证明这么做是最优的，而不是跳过它选后面的元素。

Case 0: cur已经是最后一个元素了，跳过就不是最优解了。

假设cur后面有next, 因为已经排序过了，我们可以得知 next.right >= cur.right。

Case 1: next.right == cur.right。这时候选cur和选next对后面的决策来说是一样的，但由于Case 0的存在，我必须选cur。

Case 2: next.right > cur.right。不管left的情况怎么样，由于right更小，这时候选择cur一定是优于next。

综上所述，看到有元素可以连接起来就贪心的选它就对了。

时间复杂度：O(nlogn)
空间复杂度：O(1)

class Solution {

public:

int findLongestChain(vector<vector<int>>& pairs) {

sort(begin(pairs), end(pairs), [](const auto& p1, const auto& p2){

return p1[1] < p2[1];

});

int right = INT_MIN;

int ans = 0;

for (const auto& p : pairs)

if (p[0] > right) {

right = p[1];

++ans;

}

return ans;

}

};

花花酱 LeetCode 2829. Determine the Minimum Sum of a k-avoiding Array

By zxi on August 26, 2023

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.

Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.

Constraints:

1 <= n, k <= 50

Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSum(int n, int k) {

int sum = 0;

unordered_set<int> s;

for (int i = 1; s.size() != n; ++i) {

if (s.count(k - i)) continue;

sum += i;

s.insert(i);

}

return sum;

}

};

花花酱 LeetCode 2769. Find the Maximum Achievable Number

By zxi on July 11, 2023

You are given two integers, num and t.

An integer x is called achievable if it can become equal to num after applying the following operation no more than t times:

Increase or decrease x by 1, and simultaneously increase or decrease num by 1.

Return the maximum possible achievable number. It can be proven that there exists at least one achievable number.

Example 1:

Input: num = 4, t = 1
Output: 6
Explanation: The maximum achievable number is x = 6; it can become equal to num after performing this operation:
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5. 
It can be proven that there is no achievable number larger than 6.

Example 2:

Input: num = 3, t = 2
Output: 7
Explanation: The maximum achievable number is x = 7; after performing these operations, x will equal num: 
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 7.

Constraints:

1 <= num, t <= 50

Solution: Greedy

Always decrease x and always increase num, the max achievable number x = num + t * 2

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

C++

// Author: Huahua

class Solution {

public:

int theMaximumAchievableX(int num, int t) {

return num + t * 2;

}

};

花花酱 LeetCode 2656. Maximum Sum With Exactly K Elements

By zxi on April 30, 2023

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

Select an element m from nums.
Remove the selected element m from the array.
Add a new element with a value of m + 1 to the array.
Increase your score by m.

Return the maximum score you can achieve after performing the operation exactly k times.

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.

Example 2:

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.

Constraints:

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

Solution: Greedy

Always to chose the largest element from the array.

We can find the largest element of the array m, then the total score will be
m + (m + 1) + (m + 2) + … + (m + k – 1),
We can use summation formula of arithmetic sequence to compute that in O(1)
ans = (m + (m + k – 1)) * k / 2

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

C++

// Author: Huahua

class Solution {

public:

int maximizeSum(vector<int>& nums, int k) {

int m = *max_element(begin(nums), end(nums));

return (m + m + k - 1) * k / 2;

}

};

花花酱 LeetCode 2587. Rearrange Array to Maximize Prefix Score

By zxi on March 11, 2023

You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order).

Let prefix be the array containing the prefix sums of nums after rearranging it. In other words, prefix[i] is the sum of the elements from 0 to i in nums after rearranging it. The score of nums is the number of positive integers in the array prefix.

Return the maximum score you can achieve.

Example 1:

Input: nums = [2,-1,0,1,-3,3,-3]
Output: 6
Explanation: We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].
prefix = [2,5,6,5,2,2,-1], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.

Example 2:

Input: nums = [-2,-3,0]
Output: 0
Explanation: Any rearrangement of the array will result in a score of 0.

Constraints:

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

Solution: Greedy

Sort the numbers in descending order.

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(vector<int>& nums) {

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

int ans = 0;

for (long i = 0, s = 0; i < nums.size(); ++i) {

s += nums[i];

if (s <= 0) break;

++ans;

}

return ans;

}

};