Posts published in “Greedy”

花花酱 LeetCode 860. Lemonade Change

By zxi on June 30, 2018

Problem

At a lemonade stand, each lemonade costs $5.

Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).

Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays $5.

Note that you don’t have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Solution: Simulation + Greedy

Always use 10 bill first.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

bool lemonadeChange(vector<int>& bills) {

int fives = 0;

int tens = 0;

for (const int bill : bills) {

if (bill == 5) {

++fives;

} else if (bill == 10) {

if (!fives) return false;

++tens;

--fives;

} else if (bill == 20) {

if (tens && fives) {

--tens;

--fives;

} else if (fives >= 3) {

fives -= 3;

} else {

return false;

}

return true;

}

};

花花酱 LeetCode 605. Can Place Flowers

By zxi on June 28, 2018

Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

int count = 0;

for (size_t i = 0; i < flowerbed.size() && count < n; ++i) {

if (flowerbed[i]) continue;

bool left = i == 0 ? true : !flowerbed[i - 1];

bool right = i == flowerbed.size() - 1 ? true : !flowerbed[i + 1];

if (left && right) {

flowerbed[i++] = 1;

++count;

}

return count == n;

}

};

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

By zxi on June 23, 2018

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_endbursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution: Sweep Line

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findMinArrowShots(vector<pair<int, int>>& points) {

if (points.empty()) return 0;

sort(points.begin(), points.end(),

[&](const pair<int,int>& a, const pair<int,int>& b){

return a.second < b.second;

});

int right = points.front().second;

int ans = 1;

for (const auto& point : points) {

if (point.first > right) {

right = point.second;

++ans;

}

return ans;

}

};

Problem

题目大意：给你一些牌，问你能否分组，要求每组w张连续的牌。

https://leetcode.com/problems/hand-of-straights/description/

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

Example 1:

Input: hand = [1,2,3,6,2,3,4,7,8], W = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8].

Example 2:

Input: hand = [1,2,3,4,5], W = 4
Output: false
Explanation: Alice's hand can't be rearranged into groups of 4.

Note:

1 <= hand.length <= 10000
0 <= hand[i] <= 10^9
1 <= W <= hand.length

Solution: Greedy

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

bool isNStraightHand(vector<int>& hand, int W) {

map<int, int> counts;

for (int h : hand) ++counts[h];

while (!counts.empty()) {

auto it = counts.begin();

int start = it->first;

for (int j = 0; j < W; ++j) {

if (it == counts.end()

|| it->first != start + j) return false;

auto prev = it++;

if (--(prev->second) == 0)

counts.erase(prev);

}

return true;

}

};

花花酱 LeetCode 334. Increasing Triplet Subsequence

By zxi on May 28, 2018

Problem

题目大意：判断一个数组中是否存在长度为3的单调递增子序列。

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool increasingTriplet(vector<int>& nums) {

int min1 = INT_MAX;

int min2 = INT_MAX;

for (int num : nums) {

if (num > min2) return true;

else if (num < min1) {

min1 = num;

} else if (num > min1 && num < min2) {

min2 = num;

}

return false;

}

};

Posts published in “Greedy”

花花酱 LeetCode 860. Lemonade Change

Problem

Solution: Simulation + Greedy

花花酱 LeetCode 605. Can Place Flowers

Problem

Solution: Greedy

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 846. Hand of Straights

Problem

Solution: Greedy

花花酱 LeetCode 334. Increasing Triplet Subsequence

Problem

Solution: Greedy