Posts tagged as “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 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 1145. Binary Tree Coloring Game

By zxi on August 4, 2019

Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x. The first player colors the node with value x red, and the second player colors the node with value yblue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a y to ensure you win the game, return true. If it is not possible, return false.

Example 1:

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: true
Explanation: The second player can choose the node with value 2.

Constraints:

root is the root of a binary tree with n nodes and distinct node values from 1 to n.
n is odd.
1 <= x <= n <= 100

Solution: Count size of red’s subtrees

There are two situations that blue can win.
1. one of the red’s subtree has more than n>>1 nodes. Blue colorize the root of the larger subtree.
2. red and its children has size less or equal to n>>1. Blue colorize red’s parent.

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

C++

// Author: Huahua

class Solution {

public:

bool btreeGameWinningMove(TreeNode* root, int n, int x) {

int red_left;

int red_right;

function<int(TreeNode*)> count = [&](TreeNode* node){

if (!node) return 0;

int l = count(node->left);

int r = count(node->right);

if (root->val == x) {

red_left = l;

red_right = r;

}

return 1 + l + r;

};

count(root);

// Color red's parent.

if (1 + red_left + red_right <= n / 2) return true;

// Color the child that has the larger subtree.

return max(red_left, red_right) > n / 2;

}

};

花花酱 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();

}

};