860. 檸檬水找零
https://leetcode.cn/problems/lemonade-change/
分情況討論：
用five 、ten 、twenty 3個變量記錄零錢的情況蝌数，每次看能否找零佛析。
class Solution {
public:
? ? bool lemonadeChange(vector<int>& bills) {
? ? ? ? int five = 0, ten = 0, twenty = 0;
? ? ? ? for(int i=0;i<bills.size();i++)
? ? ? ? {
? ? ? ? ? ? if(bills[i] == 5)
? ? ? ? ? ? ? ? five++;
? ? ? ? ? ? if(bills[i] == 10)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(five==0)
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? five--;
? ? ? ? ? ? ? ? ten++;
? ? ? ? ? ? }
? ? ? ? ? ? if(bills[i] == 20)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(ten>0&&five>0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ten--;five--;
? ? ? ? ? ? ? ? ? ? twenty++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if (five>=3)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? five = five-3;
? ? ? ? ? ? ? ? ? ? twenty++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return true;
? ? }
};
406. 根據(jù)身高重建隊列
https://leetcode.cn/problems/queue-reconstruction-by-height/
從兩個維度考慮問題痹仙，身高和排名
先按身高進行排序闷游，然后根據(jù)排名插入指定位置拜姿。
class Solution {
public:
? ? static bool cmp(const vector<int>& a, const vector<int>&b)
? ? {
? ? ? ? if(a[0]==b[0]) return a[1]<b[1];
? ? ? ? return a[0]>b[0];
? ? }
? ? vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
? ? ? ? //先按照身高進行排序
? ? ? ? sort(people.begin(), people.end(), cmp );
? ? ? ? vector<vector<int> > result;
? ? ? ? for(int i=0;i<people.size();i++)
? ? ? ? {
? ? ? ? ? ? int k = people[i][1];
? ? ? ? ? ? result.insert(result.begin()+k, people[i]);
? ? ? ? }
? ? ? ? return result;
? ? }
};
由于vector插入操作烙样，當插入的元素大于當前的大小時，會申請兩倍的大小進行擴容蕊肥，然后復(fù)制過去谒获。
而且插入操作的時間復(fù)雜度是n，因此整個的時間復(fù)雜度就是n平方了晴埂，再加上擴容拷貝的次數(shù)，不止n的平方了寻定。
改成鏈表的寫法：
class Solution {
public:
? ? static bool cmp(const vector<int>& a, const vector<int>&b)
? ? {
? ? ? ? if(a[0]==b[0]) return a[1]<b[1];
? ? ? ? return a[0]>b[0];
? ? }
? ? vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
? ? ? ? //先按照身高進行排序
? ? ? ? sort(people.begin(), people.end(), cmp );
? ? ? ? list<vector<int> > result;
? ? ? ? for(int i=0;i<people.size();i++)
? ? ? ? {
? ? ? ? ? ? int k = people[i][1];
? ? ? ? ? ? list<vector<int>>::iterator iter = result.begin();
? ? ? ? ? ? while(k--)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? iter++;
? ? ? ? ? ? }
? ? ? ? ? ? result.insert(iter, people[i]);
? ? ? ? }
? ? ? ? return vector<vector<int>> (result.begin(), result.end());
? ? }
};
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
算法思想：
關(guān)鍵是如何判斷兩個氣球是否重疊：使用當前氣球的左邊界與上一個氣球的右邊界比較儒洛。
如果判斷連續(xù)的氣球是否重疊：更新當前氣球的邊界為當前氣球右邊界與上一個氣球的右邊界最小值。
class Solution {
private:
? ? static bool cmp(const vector<int>&a, const vector<int>&b)
? ? {
? ? ? ? if(a[0]==b[0]) return a[1]<b[1];
? ? ? ? return a[0]<b[0];
? ? }
public:
? ? int findMinArrowShots(vector<vector<int>>& points) {
? ? ? ? //對數(shù)組進行排序
? ? ? ? sort(points.begin(), points.end(), cmp);
? ? ? ? int count = 1;
? ? ? ? for(int i=1;i<points.size();i++)
? ? ? ? {
? ? ? ? ? ? if(points[i][0]>points[i-1][1]) //當前氣球的左邊界和上一個氣球的右邊界進行比較狼速，看有沒有重合
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? points[i][1] = min(points[i][1], points[i-1][1]); //更新右邊界為二者中小的部分
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return count;
? ? }
};
