860.柠檬水找零

题目|文章
image

思路

这道题看上去很复杂，其实只要把每种情况写下来，答案就已经解决了。
1.收到5
2.收到10
3.收到20

实现

点击查看代码 
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int bill5 = 0;
        int bill10 = 0;
        for(int i = 0; i < bills.size(); i++) {
            if(bills[i] == 5) {
                bill5++;
            }
            else if(bills[i] == 10) {
                if(bill5 > 0) {
                    bill5--;
                    bill10++;
                }
                else return false;
            }
            else {
                if(bill10 > 0 && bill5 > 0) {
                    bill10--;
                    bill5--;
                }
                else if(bill5 >= 3) {
                    bill5 -= 3;
                }
                else return false;
            }
        }
        return true;
    }
};

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

406. 根据身高重建队列

题目|文章
image

思路

需要两次贪心算法，第一次对身高进行排序，第二次按照名次进行插入。
本体可以用列表进行插入，从而减少时间复杂度，因为vector的扩容会增加时间。

实现

点击查看代码 
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>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            auto it = que.begin();
            while(position --) {
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>> (que.begin(), que.end());
    }
};

####复杂度分析 * 时间复杂度：O(nlogn+n^n) * 空间复杂度：O(n)

452. 用最少数量的箭引爆气球

题目|文章
image

思路

本题的思路在于使得一只箭尽可能射中更多的气球。
1.使气球按照起始位置进行排序。
2.判断之后气球的起始位置是否超过当前箭射中气球的末尾位置。
特殊情况是如果该气球的末尾位置小于当前箭射中气球的末尾位置，需要对末尾位置进行更新。

实现

class Solution {
public:
int findMinArrowShots(vector<vector
>& points) {

    sort(points.begin(), points.end());
    int count = 1;
    int end = points[0][1];
    for(int i = 1; i < points.size(); i++) {
        if(points[i][1] < end) {
            end = points[i][1];
        }
        if(points[i][0] > end) {
            ++count;
            end = points[i][1];
        }

    }
    return count;
}
bool static cmp(const vector<int>& a, const vector<int>& b) {
    return a[0] < b[0];
}

};

复杂度分析

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

原文地址：http://www.cnblogs.com/suodi/p/16852878.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性