代码随想录第十六天|贪心算法（2）

目录

LeetCode 134. 加油站

LeetCode 135. 分发糖果

LeetCode 860. 柠檬水找零

LeetCode 406. 根据身高重建队列

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

LeetCode 435. 无重叠区间

LeetCode 763. 划分字母区间

LeetCode 56. 合并区间

LeetCode 738. 单调递增的数字

总结

---

歇逼了两天，再次开始

LeetCode 134. 加油站

题目链接：LeetCode 134. 加油站

思想：路过每个加油站的剩余量是gas[i] - cost[i]。那么从0加到第i个加油站的剩余量，如果小于零，说明[0,i]区间内都不能作为起始位置，因为到i就会断油。之后再从i+1位置算起，从0开始计算新一轮的油剩余量。

代码如下：

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int index = 0;int sum = 0;int result = 0;for (int i = 0; i < gas.size(); i++) {sum += gas[i] - cost[i];result += gas[i] - cost[i];if (sum < 0) {index = i + 1;sum = 0;}}if (result < 0) return -1;return index;}

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

LeetCode 135. 分发糖果

题目链接：LeetCode 135. 分发糖果

思想：因为除了开头和结尾的孩子，每个孩子都有相邻的两个方向左边和右边，不能同时考虑，所以本题应该要分开考虑，即先考虑孩子的右边，再考虑孩子的左边。先考虑孩子的右边，从前往后遍历，如果右孩子的评级高于当前孩子的话，右孩子分配到的糖果应当是当前孩子分配到的+1；再考虑左孩子，从后往前遍历，如果左孩子的评级高于当前孩子的话，左孩子分配到的糖果应当是左孩子原本分配到的糖果与当前孩子分配到的糖果+1取最大值。因为前面我们已经遍历且分配了一轮糖果了，不再是原本大家都是1糖果了，所以这里要取最大。

代码如下：

    int candy(vector<int>& ratings) {vector<int> candyNums(ratings.size(), 1);for (int i = 0; i < ratings.size() - 1; i++) {if (ratings[i] < ratings[i + 1]) {candyNums[i + 1] = candyNums[i] + 1;}}for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candyNums[i] = max(candyNums[i], candyNums[i + 1] + 1);}}int minCandy = 0;for (int i = 0; i < candyNums.size(); i++) minCandy += candyNums[i];return minCandy;}

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

LeetCode 860. 柠檬水找零

题目链接：LeetCode 860. 柠檬水找零

思想：本题其实十分简单，遇到5就收下；遇到10，就查看5是否有多余的，如果有就收下10，指出1张5，如果没有就return false；遇到20，优先支出1张10和1张5，因为收到的10只能用于20的补零，而5可以补10和20，灵活度更高，如果没有1张10和1张5的话，就支出3张5，如果没有3张5的话就return false。

代码如下：

    bool lemonadeChange(vector<int>& bills) {int five = 0;int ten = 0;int twenty = 0;for (int i = 0; i < bills.size(); i++) {if (bills[i] == 5) five++;else if (bills[i] == 10) {if (five > 0) {five--;ten++;}else {return false;}}else {if (ten > 0 && five > 0) {five--;ten--;twenty++;} else if (five > 2) {five-=3;twenty++;} else {return false;}}}return true;}

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

LeetCode 406. 根据身高重建队列

题目链接：LeetCode 406. 根据身高重建队列

思想：因为本题是根据身高来重建队列，[h,k]分别是身高h和队列里前面有k个高于当前的人。所以可以按照身高h来先重新排列，从大到小，如果身高相同的话则k小的站前面，让高个子站前面。之后就遍历新排列的数组，按照k来插入到新数组，插入不影响前后顺序。

代码：

    static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] == b[0] ? a[1] < b[1] : 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 position = people[i][1];result.insert(result.begin() + position, people[i]);}return result;}

时间复杂度：O(nlogn)，空间复杂度：O(n)。

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

题目链接：LeetCode 452. 用最少数量的箭引爆气球

思想：因为所有气球位置在数组里面是随机排列的，所以现在我们可以先对数组进行一个排序，对气球的左边界排序，小的在前面，大的在后面。然后遍历数组里面的元素，如果当前气球的左边界大于上一个气球的右边界的话，就需要多一个箭头；反之就让当前气球的右边界等于上一个气球的右边界，也就是可以用同一个箭头处理这一类的气球。

代码如下：

    static bool cmp(vector<int>& a, 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 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][1], points[i][1]);}}return result;}

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

LeetCode 435. 无重叠区间

题目链接：LeetCode 435. 无重叠区间

思想：首先本题也需要先重新排序输入数组，这里我选择的根据一个区间的左边界来进行排序，接下来就是找出重叠的区间，先标记一个区间的起始点，这里分为从前往后还是从后往前，这里我选择从后往前，这样做的原因是非常好进行对比。对比什么呢，如果这个标记点大于等于前一个区间的右边界的话，说明两个区间重叠了，就令标记点等于前一个区间的左边界，令重复数组标记+1。最后返回区间个数-重复数组的个数。

代码如下：

    static bool cmp(vector<int>& a, vector<int>& b) {return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int result = 1;int start = intervals[intervals.size() - 1][0];for (int i = intervals.size() - 1; i > 0; i--) {if (start >= intervals[i - 1][1]) {start = intervals[i - 1][0];result++;} else {continue;}}return intervals.size() - result;}

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

LeetCode 763. 划分字母区间

题目链接：LeetCode 763. 划分字母区间

思想：要让同一个字母最多出现在一个片段中，首先就要记录一个字母最后出现的下标。然后遍历这个字符串，标记一个片段的左边界和右边界，左右边界最开始为0，右边界在遍历的过程中等于右边界和当前字母最后出现的下标取最大值，如果遇到当前遍历的下标和右边界相等之后，就往结果数组压入当前的长度，即right - left + 1，左边界就更新为i + 1。

代码如下：

    vector<int> partitionLabels(string s) {int hash[27] = {0};for (int i = 0; i < s.size(); i++) {hash[s[i] - 'a'] = i;}int left = 0;int right = 0;vector<int> result;for (int i = 0; i < s.size(); i++) {right = max(right, hash[s[i] - 'a']);if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}

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

LeetCode 56. 合并区间

题目链接：LeetCode 56. 合并区间

思想：本题首先需要借用一个额外的数组来存储合并区间，如果只是在原来的数组上合并并更改区间的话，会导致遍历中遍历不完数组或者数组越界的情况。首先本题也需要对数组进行排序，我采用的是对左边界排序，然后往结果数组里面存放第一个区间，再遍历排序过后的区间数组，如果结果数组的最后一个区间的右边界大于或等于区间数组当前区间的左边界的话，说明两个区间重叠了，就进行合并，就是更改结果数组中的最后一个区间的右边界等于本身和区间数组当前区间的右边界取最大值；如果小于的话，就直接放入结果数组。

代码如下：

    static bool cmp(vector<int>& a, vector<int>& b) {return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if(intervals.size() == 0) return intervals;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) {result.back()[1] = max(result.back()[1], intervals[i][1]);} else {result.push_back(intervals[i]);}}return result;}

时间复杂度：O(nlogn)，空间复杂度：O(n)。

LeetCode 738. 单调递增的数字

题目链接：LeetCode 738. 单调递增的数字

思想：本题有一个十分有趣的规律，就是如果要使一个数字成为一个单调递增的数字的话，如果它本身不是，则可以先找到它不满足单调递增的地方，例如123123123，就需要找到第二个1的地方，令其减小一位，将其后面满足单调递增的数字改为9，第三个123也是如此操作。

代码如下：

    int monotoneIncreasingDigits(int n) {vector<int> count;if (n == 0) return 0;while (n) {count.push_back(n % 10);n = n / 10;}int flag = -1;for (int i = 0; i < count.size() - 1; i++) {if (count[i] < count[i + 1]) {count[i + 1]--;flag = i;}}int sum = 0;for (int i = flag; i >= 0; i--) {count[i] = 9;}for (int i = 0; i < count.size(); i++) {sum += count[i] * pow(10, i);}return sum;}

时间复杂度：O(n)，空间复杂度：O(n)。

总结

贪心算法没学到什么，能自己做出来的屈指可数，不过学到了sort函数的新方法，可以根据自定义的函数来进行排序。