860. Change for lemonade
Link to Links(opens new window)
At the lemonade stand, a glass of lemonade sells for $5.
Customers line up to buy your products, one drink at a time (in the order bills are paid).
Each customer buys just one glass of lemonade and pays you $5, $10, or $20. You have to give each customer the correct change, which means the net transaction is that each customer pays you $5.
Note that you don’t have any change on hand at first.
Return true if you gave each customer correct change, false otherwise.
Example 1:
- Input: [5,5,5,10,20]
- Output: true
Idea: If you solve the problem from the overall change, you will find it difficult. However, from the analysis of the specific change action, there are only 3 situations:
Situation 1: Receive 5, no change required;
Situation 2: Receive 10, need to use 5 to make change;
Situation 3: Received 20, 1. You can use 10 + 5 to get change, 2. You can use 5*3 to get change
Be greedy in case 3, use 5 as little as possible. (local optimization)
class Solution {
public:
bool lemonadeChange(vector<int> & amp; bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// case one
if (bill == 5) five ++ ;
// case two
if (bill == 10) {
if (five <= 0) return false;
ten + + ;
five--;
}
// case three
if (bill == 20) {
// Consume $10 first, because the change of $5 is more useful, keep as much as you can
if (five > 0 & amp; & amp; ten > 0) {
five--;
ten--;
twenty + + ; // In fact, this line of code can be deleted, because the record 20 is meaningless, and 20 will not be used for change
} else if (five >= 3) {
five -= 3;
twenty + + ; // Similarly, this line of code can also be deleted
} else return false;
}
}
return true;
}
};
Java
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills. length; i ++ ) {
if (bills[i] == 5) {
five ++ ;
} else if (bills[i] == 10) {
five--;
ten + + ;
} else if (bills[i] == 20) {
if (ten > 0) {
ten--;
five--;
} else {
five -= 3;
}
}
if (five < 0 || ten < 0) return false;
}
return true;
}
}
406. Rebuild the queue based on height
Link to Links(opens new window)
Assume that a group of people in random order stand in a queue, and the array people represents the attributes of some people in the queue (not necessarily in order). Each people[i] = [hi, ki] means that the height of the i-th person is hi, and there are exactly ki people whose height is greater than or equal to hi in front.
Please reconstruct and return the queue represented by the input array people. The returned queue should be formatted as the array queue , where queue[j] = [hj, kj] is an attribute of the jth person in the queue (queue[0] is the person at the front of the queue).
Example 1:
- Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
- Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Idea: This question has two dimensions: 1. Height sorting; 2. The number of people in front of the queue; If you consider the two dimensions together, you will lose sight of the other. (Similar to distributing candy) So Sort from large to small in terms of height first (In this way, when the elements behind are inserted into the front to meet the number of people in the front queue, the elements behind will not be affected.), Then traverse the entire two-dimensional array and sort according to the number of people in the front queue.
// version one
class Solution {
public:
static bool cmp(const vector<int> & amp; a, const vector<int> & amp; b) {
if (a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>> & amp; people) {
sort (people.begin(), people.end(), cmp);
vector<vector<int>> que;
for (int i = 0; i < people. size(); i ++ ) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
Java
class Solution {
public int[][] reconstructQueue(int[][] people) {
// Heights are arranged from large to small (the ones with the same height and small k stand in front)
Arrays. sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];
return b[0] - a[0];
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
que.add(p[1],p);
}
return que.toArray(new int[people.length][]);
}
}
452. Detonate the balloon with the least number of arrows
Link to Links(opens new window)
There are many spherical balloons in two dimensions. For each balloon, the input provided is the start and end coordinates of the diameter of the balloon in the horizontal direction. Since it’s horizontal, the ordinate doesn’t really matter, so just knowing the start and end abscissa is enough. The start coordinate is always less than the end coordinate.
A bow and arrow can be shot perfectly vertically from different points along the x-axis. Shoot an arrow at coordinate x, if there is a balloon whose diameter starts and ends at coordinates xstart, xend, and satisfies xstart ≤ x ≤ xend, the balloon will be detonated. There is no limit to the number of bows that can be shot. Once the bow and arrow is shot, it can move forward indefinitely. We want to find the minimum number of bows and arrows required to explode all the balloons.
Given an array points where points [i] = [xstart,xend] , returns the minimum number of arrows that must be shot to explode all balloons.
Example 1:
- Input: points = [[10,16],[2,8],[1,6],[7,12]]
- Output: 2
- Explanation: For this example, x = 6 can pop two balloons [2,8],[1,6], and x = 11 can pop two other balloons
Idea: Local Optimum: When the balloons overlap, shoot together and use the least amount of bows and arrows. Globally optimal: the least amount of bows and arrows is used to burst all the balloons.
In order to find overlapping balloons as much as possible, the array needs to be sorted first.
1. Determine whether the intervals of the two balloons overlap, and check whether the right interval of balloon 1 is <= the left interval of balloon 2;
2. To judge whether the three balloons overlap, first take the value of the smallest right interval of the two balloons and compare it with the left interval of balloon 3.
class Solution {
private:
static bool cmp(const vector<int> & amp; a, const vector<int> & amp; b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>> & points) {
if (points. size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1; // points need at least one arrow if it is not empty
for (int i = 1; i < points. size(); i ++ ) {
if (points[i][0] > points[i - 1][1]) { // balloon i and balloon i-1 are not next to each other, note that this is not >=
result + + ; // needs an arrow
}
else { // balloon i and balloon i-1 next to each other
points[i][1] = min(points[i - 1][1], points[i][1]); // Update the minimum right boundary of overlapping balloons
}
}
return result;
}
};
java:
/**
* Time complexity: O(NlogN) sorting requires O(NlogN) complexity
* Space complexity: O(logN) The built-in function used by java uses the space of logN for quick sorting
*/
class Solution {
public int findMinArrowShots(int[][] points) {
// Sort according to the starting coordinates of the balloon diameter from small to large
// Use Integer's built-in comparison method without overflow
Arrays. sort(points, (a, b) -> Integer. compare(a[0], b[0]));
int count = 1; // at least one arrow is required if points is not empty
for (int i = 1; i < points. length; i ++ ) {
if (points[i][0] > points[i - 1][1]) { // balloon i and balloon i-1 are not next to each other, note that this is not >=
count + + ; // needs an arrow
} else { // balloon i and balloon i-1 next to each other
points[i][1] = Math.min(points[i][1], points[i - 1][1]); // Update the minimum right boundary of overlapping balloons
}
}
return count;
}
}