代码随想录算法训练营第35天|860.柠檬水找零,406.根据身高重建队列,452. 用最少数量的箭引爆气球
860.柠檬水找零
题目链接:860.柠檬水找零,难度:简单
【实现代码】
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int change[2] = {0};for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) {change[0]++;} else if (bills[i] == 10) {change[0]--;change[1]++;} else if (bills[i] == 20) {change[0]--;if (change[1] == 0) {change[0] -= 2;} else {change[1]--;} }// cout << change[0] << " " << change[1] << endl;if (change[0] < 0 || change[1] < 0) {return false;}}return true;}
};
【解题思路】
需要注意的是,5块和10块是分开计数的,而且当十块不够的时候可以使用5块的。
406. 根据身高重建队列
题目链接:406. 根据身高重建队列,难度:中等
【实现代码】
class Solution {
public:static bool cmp(const vector<int>& people1, const vector<int>& people2) {if (people1[0] == people2[0]) {return people1[1] < people2[1];} else {return people1[0] > people2[0];}}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(), cmp);// for (int i = 0; i < people.size(); i++) {// cout << people[i][0] << " " << people[i][1] << endl;// }list<vector<int>> queue;for (int i = 0; i < people.size(); i++) {int position = people[i][1];list<vector<int>>::iterator it = queue.begin();while (position--) {it++;}queue.insert(it, people[i]);}return vector<vector<int>>(queue.begin(), queue.end());}
};
【解题思路】
首先是对原数组进行排列,按照身高降序和k值升序的顺序排列。
接着是插入到新的数组里,应该按照对应k值进行操作。
因为vector的底层结构是数组,插入和删除操作都是O(n^2),所以使用链表进行存储新的队列。
452. 用最少数量的箭引爆气球
题目链接:452. 用最少数量的箭引爆气球,难度:中等
【实现代码】
class Solution {
public:static bool cmp(vector<int>& point1, vector<int>& point2) {return point1[0] < point2[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end(), cmp);int result = 1;for (int i = 1; i < points.size(); i++) { if (points[i][0] > points[i - 1][1]) {result++;} else {points[i][1] = min(points[i][1], points[i - 1][1]);}}return result;}
};
【解题思路】
这一题主要是找重叠的坐标范围,首先也是对坐标进行排序,按照第一个x进行升序排列。
之后找重叠的范围,每次要找到相邻两个坐标的最大重叠坐标x;如果下一个的第一个x大于前一个坐标的第二个x,则需要重新射一箭。