贪心基础练习¶

class Solution455
{
public:
    int findContentChildren(vector<int> &g, vector<int> &s)
    {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int count = 0;
        int index = 0;

        for (int i = 0; i < s.size(); i++)
        {
            if (index < g.size() && s[i] >= g[index])
            {
                index++;
                count++;
            }
        }

        return count;
    }
};

class Solution376
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        // 默认存在一个子序列长度
        int count = 1;
        int prediff = 0;
        int curdiff = 0;

        // 假设右侧存在一个峰值，即默认结果1
        for (int i = 0; i < nums.size() - 1; i++)
        {
            curdiff = nums[i + 1] - nums[i];
            if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0))
            {
                prediff = curdiff;
                count++;
            }
        }

        return count;
    }
};

class Solution53
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int ret = INT_MIN;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            // 计算当前和
            if (sum < 0)
                sum = nums[i];
            else
                sum += nums[i];

            // 获取到当前的最大结果
            ret = max(sum, ret);
        }

        return ret;
    }
};

class Solution121
{
public:
    int maxProfit(vector<int> &prices)
    {
        // 如果只有一个元素，说明没有卖出时间，直接返回0
        // 或者理解为买入即卖出
        if (prices.size() < 2)
            return 0;

        int ret = INT_MIN;
        for (int fast = 1, slow = 0; fast < prices.size() && slow < prices.size();)
        {
            int pro = prices[fast] - prices[slow];
            if (pro < 0)
                slow++;
            else
                fast++;
            ret = max(pro, ret);
        }

        return ret;
    }
};

class Solution122
{
public:
    int maxProfit(vector<int> &prices)
    {
        int pro = 0;
        int ret = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            // 计算相邻元素之差
            int pro = prices[i] - prices[i - 1];
            // 如果相邻元素之差大于0即可累加
            if (pro > 0)
                ret += pro;
        }
        return ret;
    }
};

class Solution55
{
public:
    bool canJump(vector<int> &nums)
    {
        int last = nums.size() - 1;
        int step = nums[0];
        for (int i = 0; i < nums.size(); i++)
        {
            step--;

            // 每次贪较大的步数，使可以走的步数尽可能多
            if (nums[i] > step)
                step = nums[i];

            // 步数走完并且没有到最后一个元素
            if (step <= 0 && i < last)
                return false;
        }

        return true;
    }
};

class Solution45
{
public:
    int jump(vector<int> &nums)
    {
        int cur = 0;
        int next = 0;
        int count = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            // 记录下一次最大可以抵达的位置
            next = max(i + nums[i], next);
            // 如果i等于最大可以抵达的位置时存在两种情况
            // 1. 还没有走到终点，需要更新下一次最大可以抵达的位置
            // 2. 走到了终点，直接退出
            if (i == cur)
            {
                if (cur != nums.size() - 1)
                {
                    cur = next;
                    count++;
                }
                else
                    break; // 已经走到终点，直接退出
            }
        }

        return count;
    }
};

class Solution1005
{
public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        // 按照绝对值较大优先，对数组进行排序
        sort(nums.begin(), nums.end(), [&](int a, int b)-> bool
        {
            return abs(a) > abs(b);
        });

        // 第一次贪心：对绝对值较大的负数进行取反，使得数组的负数个数尽可能少
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k > 0)
            {
                nums[i] *= -1;
                k--;
            }
        }

        // 第二次贪心：对最小的非负整数进行取反，使得影响数组总和的负数个数最少
        // 如果k是奇数，那么多次取反后，结果就是原数取反的结果
        // 如果k是偶数，那么多次取反后，结果依旧是原数
        if (k % 2 == 1)
            nums[nums.size() - 1] *= -1;

        return accumulate(nums.begin(), nums.end(), 0);
    }
};

class Solution134
{
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
    {
        // 记录当前位置是增益还是损耗
        int curSum = 0;
        // 记录整体和是增益还是消耗
        int totalSum = 0;
        // 记录起始位置
        int start = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];

            // 如果当前位置是消耗，则说明之前的所有位置作为起始位置到达当前位置都会导致油量不够
            if (curSum < 0)
            {
                // 从下一个位置开始
                start = i + 1;
                // 重新统计增益还是消耗
                curSum = 0;
            }
        }

        // 如果整体是消耗，则说明不存在一个起点可以满足条件
        if (totalSum < 0)
            return -1;
        return start;
    }
};

class Solution135
{
public:
    int candy(vector<int> &ratings)
    {
        // 先给每个孩子都发一颗糖，总糖量即为数组长度
        vector<int> totalCandy(ratings.size(), 1);

        // 先正向遍历，考虑左侧比右侧大的情况
        for (int i = 1; i < ratings.size(); i++)
        {
            if (ratings[i] > ratings[i - 1])
                totalCandy[i] = totalCandy[i - 1] + 1;
        }

        // 再反向遍历，考虑右侧比左侧小的情况
        for (int i = ratings.size() - 2; i >= 0; i--)
        {
            if (ratings[i] > ratings[i + 1])
                totalCandy[i] = max(totalCandy[i + 1] + 1, totalCandy[i]);
        }

        return accumulate(totalCandy.begin(), totalCandy.end(), 0);
    }
};

class Solution860
{
public:
    bool lemonadeChange(vector<int> &bills)
    {
        int five = 0;
        int ten = 0;
        for (auto bill: bills)
        {
            if (bill == 5)
                five++;
            else if (bill == 10)
            {
                if (five == 0)
                    return false;
                five--;
                ten++;
            }
            else if (bill == 20)
            {
                if (five > 0 && ten > 0)
                {
                    five--;
                    ten--;
                }
                else if (five >= 3)
                {
                    five -= 3;
                }
                else
                    return false;
            }
        }

        return true;
    }
};

class Solution452
{
public:
    int findMinArrowShots(vector<vector<int>> &points)
    {
        if (points.size() == 0)
            return 0;

        int count = 1;

        sort(points.begin(), points.end(), [](vector<int> &p1, vector<int> &p2)-> bool
        {
            // return p1[0] < p2[0] || p1[0] == p2[0] && p1[1] < p2[1];
            // 也可以只比较左边界，因为下面会对右边界根据较小值进行更新
            return p1[0] < p2[0];
        });

        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][1], points[i][1]);
            }
        }

        return count;
    }
};

class Solution435
{
public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        int count = 0;

        sort(intervals.begin(), intervals.end(), [](vector<int> &i1, vector<int> &i2)
        {
            return i1[0] < i2[0];
        });

        for (int i = 1; i < intervals.size(); i++)
        {
            // 判断当前位置的左边界是否小于前一个位置的右边界
            if (intervals[i][0] < intervals[i - 1][1])
            {
                count++;
                // 取最小右边界作为下一次判断的条件，此步骤就相当于移除重叠区间
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }

        return count;
    }
};

class Solution56
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        vector<vector<int>> ret;

        sort(intervals.begin(), intervals.end(), [](vector<int> &i1, vector<int> &i2)
        {
            return i1[0] < i2[0];
        });

        // 默认有第一个区间
        ret.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); i++)
        {
            // 判断当前区间的左边界是否小于等于上一区间的右边界
            if (intervals[i][0] <= intervals[i - 1][1])
            {
                // 先移除前一个区间
                ret.pop_back();
                // 合并区间并插入合并后的区间
                intervals[i][0] = min(intervals[i - 1][0], intervals[i][0]);
                intervals[i][1] = max(intervals[i - 1][1], intervals[i][1]);
                ret.push_back(intervals[i]);
            }
            else
            {
                // 否则直接插入
                ret.push_back(intervals[i]);
            }
        }

        return ret;
    }
};

class Solution763
{
public:
    vector<int> partitionLabels(string s)
    {
        // 使用哈希表统计每个字符最远出现的位置
        unordered_map<char, int> maxPos;

        for (int i = 0; i < s.size(); i++)
            maxPos[s[i]] = i;

        // 从前向后遍历整个字符串，找出每个区间的最大位置
        int start = 0, end = 0;
        vector<int> ret;
        for (int i = 0; i < s.size(); i++)
        {
            end = max(end, maxPos[s[i]]);
            // 如果当前位置已经到达区间最大位置，就说明已经找到一个区间
            if (i == end)
            {
                ret.push_back(end - start + 1);
                // 更新左边界
                start = i + 1;
            }
        }

        return ret;
    }
};