本文介绍: 找零只用分三种情况即可需要注意的是情况三,对20找零时应该先判断一个10和一个5的情况,因为5是万能的,先把5用完的话情况二就不能满足了。

860.柠檬水找零

题目链接:柠檬水找零

        找零只用分三种情况即可

  • 情况一:账单是5,直接收下。
  • 情况二:账单是10,消耗一个5,增加一个10
  • 情况三:账单是20,优先消耗一个10和一个5,如果不够,再消耗三个5

需要注意的是情况三,对20找零时应该先判断一个10和一个5的情况,因为5是万能的,先把5用完的话情况二就不能满足了。

// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int f = 0, t = 0, tw = 0;
        if (bills[0] != 5) return false;
        for (int i = 0; i < bills.size(); ++i)
        {
            if (bills[i] == 5)
            {
                f++;
            }

            if (bills[i] == 10)
            {
                if (f != 0)
                {
                    f--;
                    t++;
                }  
                else
                {
                    return false;
                }
            }

            if (bills[i] == 20)
            {
                if (f != 0 && t != 0)
                {
                    f -= 1;
                    t -= 1;
                    tw++;
                }
                else if (f >= 3)
                {
                    f -= 3;
                    tw++;
                }
                else
                {
                    return false;
                }
            }
        }
        return true;
    }
};

406.根据身高重建队列

题目链接:根据身高重建队列

        思路:现根据身高由大到小排序,相同身高按比他身高高的人数由少到多排序。遍历排序后的people数组,按身高高的人数插入队列,因为身高已经由大到排序了,身高低的人插到前面不会影响后面的判断结果。

// 时间复杂度:O(nlog n + n^2)
// 空间复杂度:O(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);
        vector<vector<int>> queue;
        for (int i = 0; i < people.size(); ++i)
        {
            int pos = people[i][1];
            queue.insert(queue.begin() + pos, people[i]);
        }
        return queue;
    }
};

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

题目链接:用最少数量的箭引爆气球

        思路:先按每个区间的最小值对这些区间由小到大排序,判断前一个区间的最大值是否大于当前区间的最小值,若小于等于则需要加一根箭,若大于则更新前一个区间的最大值,更新为这两个区间中最大值较小的那个(以满足两个以上区间重叠的情况),然后继续向后遍历。

// 时间复杂度:O(nlog n),因为有一个快排
// 空间复杂度:O(1),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);
        int ret = 1;
        for (int i = 1; i < points.size(); ++i)
        {
            if (points[i - 1][1] < points[i][0])
            {
                ret++;
            }
            else
            {
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新右边界
            }
        }
        return ret;
    }
};

原文地址:https://blog.csdn.net/qq_41943352/article/details/136018049

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_65913.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注