Posts published in “Greedy”

花花酱 LeetCode 122. Best Time to Buy and Sell Stock II

By zxi on October 9, 2019

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution: Greedy

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

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int> &prices) {

int profit = 0;

for (size_t i = 1; i < prices.size(); ++i)

profit += max(0, prices[i] - prices[i - 1]);

return profit;

}

};

花花酱 LeetCode 1200. Minimum Absolute Difference

By zxi on September 22, 2019

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

Solution: Sorting

The min abs difference could only happen between consecutive numbers in sorted form.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {

sort(begin(arr), end(arr));

vector<vector<int>> ans;

int best = INT_MAX;

for (int i = 1; i < arr.size(); ++i) {

int d = abs(arr[i] - arr[i - 1]);

if (d < best) {

ans.clear();

best = d;

}

if (d == best) ans.push_back({arr[i - 1], arr[i]});

}

return ans;

}

};

花花酱 LeetCode 1147. Longest Chunked Palindrome Decomposition

By zxi on August 4, 2019

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Solution: Greedy

Break the string when the shortest palindrome is found.
prefer to use string_view

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

C++

// Author: Huahua, 0 ms, 8.7 ms

class Solution {

public:

int longestDecomposition(string_view text) {

const int n = text.length();

if (n == 0) return 0;

for (int l = 1; l <= n / 2; ++l) {

if (text.substr(0, l) == text.substr(n - l))

return 2 + longestDecomposition(text.substr(l, n - 2 * l));

}

return 1;

}

};

花花酱 LeetCode 1144. Decrease Elements To Make Array Zigzag

By zxi on August 4, 2019

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.

An array A is a zigzag array if either:

Every even-indexed element is greater than adjacent elements, ie. A[0] > A[1] < A[2] > A[3] < A[4] > ...
OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < ...

Return the minimum number of moves to transform the given array nums into a zigzag array.

Example 1:

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:

Input: nums = [9,6,1,6,2]
Output: 4

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000

Solution: Greedy

One pass, making each element local minimum.

[9,6,1,6,2]
i = 0, [inf, 9, 6], 9 => 5, even cost 4
i = 1, [9, 6, 1], 6 => 0, odd cost 6
i = 2, [6, 1, 6], 1 => 1, even cost 0
i = 3, [1, 6, 2], 6 => 0, odd cost 12
i = 4, [6, 2, inf], 2 => 2, even cost 0
total even cost 4, new array => [5, 6, 1, 6, 2]
total odd cost 18, new array => [9, 0, 1, 0, 2]

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

C++

// Author: Huahua

class Solution {

public:

int movesToMakeZigzag(vector<int>& nums) {

const int n = nums.size();

vector<int> moves(2);

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

int l = i == 0 ? INT_MAX : nums[i - 1];

int r = i == n - 1 ? INT_MAX : nums[i + 1];

moves[i % 2] += max(0, nums[i] - min(l, r) + 1);

}

return min(moves[0], moves[1]);

}

};

花花酱 LeetCode 630. Course Schedule III

By zxi on May 10, 2019

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on d_th day. A course should be taken continuouslyfor t days and must be finished before or on the d_th day. You will start at the 1_st day.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation: 
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

The integer 1 <= d, t, n <= 10,000.
You can’t take two courses simultaneously.

Solution: Priority queue

Sort courses by end date
Use a priority queue (Max-Heap) to store the course lengths or far
Swap with a longer course if we could not take the current one

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

C++

// Author: Huahua, running time: 196 ms, 40.5 MB

class Solution {

public:

int scheduleCourse(vector<vector<int>>& courses) {

sort(begin(courses), end(courses), [](const auto& a, const auto& b) {

return a[1] < b[1];

});

priority_queue<int> q;

int d = 0;

for (const auto& c: courses) {

if (d + c[0] <= c[1]) {

d += c[0];

q.push(c[0]);

} else if (q.size() && q.top() > c[0]) {

d += c[0] - q.top(); q.pop();

q.push(c[0]);

}

return q.size();

}

};