A summary of greedy algorithm related problems from LeetCode with solutions in C++.
贪心算法一般分为如下四步 ：
(1) 将问题分解为若干个子问题
(2) 找出适合的贪心策略
(3) 求解每一个子问题的最优解
(4) 将局部最优解堆叠成全局最优解
Problems:
455. Assign Cookies
376. Wiggle Subsequence
53. Maximum Subarray
122. Best Time to Buy and Sell Stock II
55. Jump Game
45. Jump Game II
1005. Maximize Sum Of Array After K Negations
134. Gas Station
135. Candy
860. Lemonade Change
406. Queue Reconstruction by Height
452. Minimum Number of Arrows to Burst Balloons
435. Non-overlapping Intervals
763. Partition Labels
56. Merge Intervals
738. Monotone Increasing Digits
714. Best Time to Buy and Sell Stock with Transaction Fee
968. Binary Tree Cameras
Problem: Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Case 1: Input: g = [1,2,3], s = [1,1], Output: 1
Case 2: Input: g = [1,2], s = [1,2,3], Output: 2
先将饼干数组和小孩数组排序, 然后从后向前遍历小孩数组, 用大饼干优先满足胃口大的, 并统计满足小孩数量
class Solution {
public:
// 时间复杂度: O(nlogn)
// 空间复杂度：O(1)
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end()); // 胃口值
sort(s.begin(), s.end()); // 饼干尺寸
int index = s.size() - 1; // 饼干数组的下标
int result = 0;
for (int i = g.size() - 1; i >= 0; i--) {
if (index >= 0 && s[index] >= g[i]) {
result++;
index--;
}
}
return result;
}
};
Problem: A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.
For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative. In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order. Given an integer array nums, return the length of the longest wiggle subsequence of nums.
Case 1: Input: nums = [1,7,4,9,2,5], Output: 6
Case 2: Input: nums = [1,17,5,10,13,15,10,5,16,8], Output: 7
Case 3: Input: nums = [1,2,3,4,5,6,7,8,9], Output: 2
局部最优: 删除单调坡度上的节点(不包括单调坡度两端的节点), 那么这个坡度就可以有两个局部峰值
整体最优: 整个序列有最多的局部峰值, 从而达到最长摆动序列
实际操作上, 其实连删除的操作都不用做, 因为题目要求的是最长摆动子序列的长度, 所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点, 然后统计长度)
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度：O(1)
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) { return nums.size();}
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数, 默认序列最右边有一个峰值
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
// 出现峰值
if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
}
};
Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.
Case 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4], Output: 6
Case 2: Input: nums = [1], Output: 1
Case 3: Input: nums = [5,4,-1,7,8], Output: 23
局部最优: 当前”连续和”为负数的时候立刻放弃, 从下一个元素重新计算”连续和”, 因为负数加上下一个元素”连续和”只会越来越小。全局最优: 选取最大”连续和”。
从代码角度上来讲: 遍历nums, 从头开始用count累积, 如果count一旦加上nums[i]变为负数, 那么就应该从nums[i+1]开始从0累积count了, 因为已经变为负数的count, 只会拖累总和。
class Solution {
public:
// 时间复杂度：O(n)
// 空间复杂度：O(1)
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
// 取区间累计的最大值(相当于不断确定最大子序终止位置)
if (count > result) { result = count; }
// 相当于重置最大子序起始位置, 因为遇到负数一定是拉低总和
if (count <= 0) { count = 0; }
}
return result;
}
};
4. 122. Best Time to Buy and Sell Stock II
Problem: You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
Case 1: Input: prices = [7,1,5,3,6,4], Output: 7
Case 2: Input: prices = [1,2,3,4,5], Output: 4
Case 3: Input: prices = [7,6,4,3,1], Output: 0
假如第0天买入, 第3天卖出, 那么利润为: prices[3] – prices[0], 相当于(prices[3] – prices[2]) + (prices[2] – prices[1]) + (prices[1] – prices[0]), 此时就是把利润分解为每天为单位的维度, 而不是从0天到第3天整体去考虑, 那么根据prices可以得到每天的利润序列: (prices[i] – prices[i – 1]) + … + … + (prices[1] – prices[0])
第一天没有利润, 至少要第二天才会有利润, 所以利润的序列比股票序列少一天。从图中可以发现, 其实我们需要收集每天的正利润就可以, 收集正利润的区间, 就是股票买卖的区间, 而我们只需要关注最终利润, 不需要记录区间。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); i++) {
result += max(prices[i] - prices[i - 1], 0);
}
return result;
}
};
Problem: You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
Case 1: Input: nums = [2,3,1,1,4], Output: true
Case 2: Input: nums = [3,2,1,0,4], Output: false
每次移动取最大跳跃步数(得到最大的覆盖范围), 每移动一个单位, 就更新最大覆盖范围。贪心算法局部最优解: 每次取最大跳跃步数(取最大覆盖范围), 整体最优解: 最后得到整体最大覆盖范围, 看是否能到终点
i每次移动只能在cover的范围内移动, 每移动一个元素, cover得到该元素数值(新的覆盖范围)的补充, 让i继续移动下去。而cover每次只取max(该元素数值补充后的范围, cover本身范围)。如果cover大于等于了终点下标, 直接return true就可以了。
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0;
if (nums.size() == 1) { return true; } // 只有一个元素，就是能达到
for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
cover = max(i + nums[i], cover);
if (cover >= nums.size() - 1) { return true; } // 说明可以覆盖到终点了
}
return false;
}
};
Problem : You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:
0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n – 1]. The test cases are generated such that you can reach nums[n – 1].
Case 1: Input: nums = [2,3,1,1,4], Output: 2
Case 2: Input: nums = [2,3,0,1,4], Output: 2
解题的时候, 要从覆盖范围出发, 不管怎么跳, 覆盖范围内一定是可以跳到的, 以最小的步数增加覆盖范围, 覆盖范围一旦覆盖了终点, 得到的就是最小步数, 这里需要统计两个覆盖范围, 当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了, 还没有到终点的话, 那么就必须再走一步来增加覆盖范围, 直到覆盖范围覆盖了终点。
从图中可以看出来, 就是移动下标达到了当前覆盖的最远距离下标时, 步数就要加一, 来增加覆盖距离, 最后的步数就是最少步数。这里还是有个特殊情况需要考虑, 当移动下标达到了当前覆盖的最远距离下标时
(1) 如果当前覆盖最远距离下标不是是集合终点, 步数就加一, 还需要继续走
(2) 如果当前覆盖最远距离下标就是是集合终点, 步数不用加一, 因为不能再往后走了
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() == 1) { return 0; }
int ans = 0; // 记录走的最大步数
int curDistance = 0; // 当前覆盖最远距离下标
int nextDistance = 0; // 下一步覆盖最远距离下标
for (int i = 0; i < nums.size(); i++) {
// 更新下一步覆盖最远距离下标
nextDistance = max(nums[i] + i, nextDistance);
// 遇到当前覆盖最远距离下标
if (i == curDistance) {
// 如果当前覆盖最远距离下标不是终点
if (curDistance != nums.size() - 1) {
// 需要走下一步
ans++;
// 更新当前覆盖最远距离下标(相当于加油了)
curDistance = nextDistance;
// 下一步的覆盖范围已经可以达到终点, 结束循环
if (nextDistance >= nums.size() - 1) {break;}
} else {break;} // 当前覆盖最远距离下标是集合终点, 不用做ans++操作了, 直接结束
}
}
return ans;
}
};
7. 1005. Maximize Sum Of Array After K Negations
Problem: Given an integer array nums and an integer k, modify the array in the following way: choose an index i and replace nums[i] with -nums[i]. You should apply this process exactly k times. You may choose the same index i multiple times. Return the largest possible sum of the array after modifying it in this way.
Case 1: Input: nums = [4,2,3], k = 1, Output: 5, 解释: 选择索引(1,), 然后A变为[4,-2,3]
Case 2: Input: nums = [3,-1,0,2], k = 3, Output: 6, 解释: 选择索引 (1, 2, 2), 然后A变为[3,1,0,2]
Case 3: Input: nums = [2,-3,-1,5,-4], k = 2, Output: 13, 解释: 选择索引(1, 4), 然后A变为[2,3,-1,5,4]
贪心的思路, 局部最优: 让绝对值大的负数变为正数, 当前数值达到最大, 整体最优: 整个数组和达到最大, 局部最优可以推出全局最优。那么如果将负数都转变为正数了, K依然大于0, 此时的问题是一个有序正整数序列, 如何转变K次正负, 让数组和达到最大。局部最优: 只找数值最小的正整数进行反转, 当前数值可以达到最大(例如正整数数组{5,3,1}, 反转1得到-1比反转5得到的-5大多了), 全局最优: 整个数组和达到最大。
第一步: 将数组按照绝对值大小从大到小排序, 注意要按照绝对值的大小
第二步: 从前向后遍历, 遇到负数将其变为正数, 同时K–
第三步: 如果K还大于0, 那么反复转变数值最小的元素, 将K用完
第四步: 求和
class Solution {
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), cmp); // 第一步
for (int i = 0; i < nums.size(); i++) { // 第二步
if (nums[i] < 0 && k > 0) {
nums[i] *= -1;
k--;
}
}
if (k % 2 == 1) {nums[nums.size() - 1] *= -1;} // 第三步
int result = 0;
for (int a : nums) { result += a; } // 第四步
return result;
}
};
Problem: There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Case 1: Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2], Output: 3
Case 2: Input: gas = [2,3,4], cost = [3,4,3], Output: -1
如果题目有解, 该答案即为唯一答案
输入数组均为非空数组, 且长度相同
输入数组中的元素均为非负数
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈, 说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] – cost[i], i从0开始累加rest[i], 和记为curSum, 一旦curSum小于零, 说明[0, i]区间都不能作为起始位置, 起始位置从i+1算起, 再从0计算curSum
那么局部最优: 当前累加rest[j]的和curSum一旦小于0, 起始位置至少要是j+1, 因为从j开始一定不行。全局最优: 找到可以跑一圈的起始位置
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(1)
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) { // 当前累加rest[i]和curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) { return -1; } // 说明怎么走都不可能跑一圈了
return start;
}
};
9. 135. Candy
Problem: There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: (1) Each child must have at least one candy. (2) Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.
Case 1: Input: ratings = [1,0,2], Output: 5
Case 2: Input: ratings = [1,2,2], Output: 4
如果ratings[i] > ratings[i-1], 那么[i]的糖 一定要比[i-1]的糖多一个, 所以贪心: candyVec[i] = candyVec[i-1] + 1
再确定左孩子大于右孩子的情况(从后向前遍历), 如果ratings[i] > ratings[i+1], 此时candyVec[i] (第i个小孩的糖果数量) 就有两个选择了, 一个是candyVec[i+1] + 1(从右边这个加1得到的糖果数量), 一个是candyVec[i](之前比较右孩子大于左孩子得到的糖果数量)。局部最优: 取candyVec[i+1] + 1 和 candyVec[i] 最大的糖果数量, 保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优: 相邻的孩子中, 评分高的孩子获得更多的糖果。
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
// 从前向后
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) {
candyVec[i] = candyVec[i - 1] + 1;
}
}
// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] ) {
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
}
}
// 统计结果
int result = 0;
for (int i = 0; i < candyVec.size(); i++) { result += candyVec[i]; }
return result;
}
};
Problem: At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5. Note that you do not have any change in hand at first. Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Case 1: Input: bills = [5,5,5,10,20], Output: true
Case 2: Input: bills = [5,5,10,10,20], Output: false
情况一: 账单是5, 直接收下
情况二: 账单是10, 消耗一个5, 增加一个10
情况三: 账单是20, 优先消耗一个10和一个5, 如果不够, 再消耗三个5
局部最优: 遇到账单20, 优先消耗美元10, 完成本次找零, 全局最优: 完成全部账单的找零
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0;
for (int bill : bills) {
// 情况一
if (bill == 5) { five++; }
// 情况二
if (bill == 10) {
if (five <= 0) { return false; }
ten++;
five--;
}
// 情况三
if (bill == 20) {
// 优先消耗10美元, 因为5美元的找零用处更大, 能多留着就多留着
if (five > 0 && ten > 0) {
five--;
ten--;
twenty++; // 其实这行代码可以删了, 因为记录20已经没有意义了, 不会用20来找零
} else if (five >= 3) {
five -= 3;
twenty++; // 同理, 这行代码也可以删了
} else { return false; }
}
}
return true;
}
};
11. 406. Queue Reconstruction by Height
Problem: You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi. Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
Case 1: Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]], Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Case 2: Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]], Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
按照身高排序之后, 优先按身高高的people的k来插入, 后序插入节点也不会影响前面已经插入的节点, 最终按照k的规则完成了队列。所以在按照身高从大到小排序后: 局部最优: 优先按身高高的people的k来插入, 插入操作过后的people满足队列属性。全局最优: 最后都做完插入操作, 整个队列满足题目队列属性
排序完的people: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]
插入的过程：
插入[7,0]: [[7,0]]
插入[7,1]: [[7,0],[7,1]]
插入[6,1]: [[7,0],[6,1],[7,1]]
插入[5,0]: [[5,0],[7,0],[6,1],[7,1]]
插入[5,2]: [[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
class Solution {
public:
// 时间复杂度: O(nlog n + n^2)
// 空间复杂度: O(n)
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>> que;
for (int i = 0; i < people.size(); i++) {
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};
12. 452. Minimum Number of Arrows to Burst Balloons
Problem: There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path. Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
Case 1: Input: points = [[10,16],[2,8],[1,6],[7,12]], Output: 2
Case 2: Input: points = [[1,2],[3,4],[5,6],[7,8]], Output: 4
Case 3: Input: points = [[1,2],[2,3],[3,4],[4,5]], Output: 2
局部最优: 当气球出现重叠, 一起射, 所用弓箭最少。全局最优: 把所有气球射爆所用弓箭最少
如果把气球排序之后, 从前到后遍历气球, 被射过的气球仅仅跳过就行了, 没有必要让气球数组remove气球, 只要记录一下箭的数量就可以了。既然按照起始位置排序, 那么就从前向后遍历气球数组, 靠左尽可能让气球重复。如果气球重叠了, 重叠气球中右边边界的最小值之前的区间一定需要一个弓箭
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) { return 0; }
sort(points.begin(), points.end(), cmp);
// points不为空至少需要一支箭
int result = 1;
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着, 注意这里不是>=
result++; // 需要一支箭
}
else { // 气球i和气球i-1挨着
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
}
}
return result;
}
};
13. 435. Non-overlapping Intervals
Problem: Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Case 1: Input: intervals = [[1,2],[2,3],[3,4],[1,3]], Output: 1
Case 2: Input: intervals = [[1,2],[1,2],[1,2]], Output: 2
Case 3: Input: intervals = [[1,2],[2,3]], Output: 0
按照右边界排序, 从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。此时问题就是要求非交叉区间的最大个数, 右边界排序之后, 局部最优: 优先选右边界小的区间, 所以从左向右遍历, 留给下一个区间的空间大一些, 从而尽量避免交叉。全局最优: 选取最多的非交叉区间
区间1,2,3,4,5,6都按照右边界排好序, 每次取非交叉区间的时候, 都是可右边界最小的来做分割点(这样留给下一个区间的空间就越大), 所以第一条分割线就是区间1结束的位置。接下来就是找大于区间1结束位置的区间, 是从区间4开始。区间4结束之后, 再找到区间6, 所以一共记录非交叉区间的个数是三个。总共区间个数为6, 减去非交叉区间的个数3, 移除区间的最小数量就是3
class Solution {
public:
// 时间复杂度: O(nlog n), 有一个快排
// 空间复杂度: O(n)
// 按照区间右边界排序
static bool cmp (const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {return 0;}
sort(intervals.begin(), intervals.end(), cmp);
int count = 1; // 记录非交叉区间的个数
int end = intervals[0][1]; // 记录区间分割点
for (int i = 1; i < intervals.size(); i++) {
if (end <= intervals[i][0]) {
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}
};
Problem: You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return a list of integers representing the size of these parts.
Case 1: Input: s = “ababcbacadefegdehijhklij”, Output: [9,7,8]
Case 2: Input: s = “eccbbbbdec”, Output: [10]
在遍历的过程中相当于是要找每一个字母的边界, 如果找到之前遍历过的所有字母的最远边界, 说明这个边界就是分割点了。此时前面出现过所有字母, 最远也就到这个边界了。可以分为如下两步:
(1) 统计每一个字符最后出现的位置
(2) 从头遍历字符, 并更新字符的最远出现下标, 如果找到字符最远出现位置下标和当前下标相等了, 则找到了分割点
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(1), 使用的hash数组是固定大小
vector<int> partitionLabels(string S) {
// i为字符, hash[i]为字符出现的最后位置
int hash[27] = {0};
// 统计每一个字符最后出现的位置
for (int i = 0; i < S.size(); i++) {
hash[S[i] - 'a'] = i;
}
vector<int> result;
int left = 0;
int right = 0;
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;
}
};
Problem: Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Case 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]], Output: [[1,6],[8,10],[15,18]]
Case 2: Input: intervals = [[1,4],[4,5]], Output: [[1,5]]
按照左边界排序, 排序之后, 局部最优: 每次合并都取最大的右边界, 这样就可以合并更多的区间了, 整体最优: 合并所有重叠的区间。按照左边界从小到大排序之后, 如果 intervals[i][0] < intervals[i – 1][1], 即intervals[i]左边界 < intervals[i – 1]右边界, 则一定有重复, 因为intervals[i]的左边界一定是大于等于intervals[i – 1]的左边界
class Solution {
public:
// 时间复杂度: O(nlog n), 有一个快排
// 空间复杂度: O(n)
// 按照区间左边界从小到大排序
static bool cmp (const vector<int>& a, const 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 result; }
sort(intervals.begin(), intervals.end(), cmp);
bool flag = false; // 标记最后一个区间有没有合并
int length = intervals.size();
for (int i = 1; i < length; i++) {
int start = intervals[i - 1][0]; // 初始为i-1区间的左边界
int end = intervals[i - 1][1]; // 初始i-1区间的右边界
while (i < length && intervals[i][0] <= end) { // 合并区间
end = max(end, intervals[i][1]); // 不断更新右区间
if (i == length - 1) {flag = true;} // 最后一个区间也合并了
i++; // 继续合并下一个区间
}
// start和end是表示intervals[i - 1]的左边界右边界
// 所以最优intervals[i]区间是否合并了要标记一下
result.push_back({start, end});
}
// 如果最后一个区间没有合并, 将其加入result
if (flag == false) {
result.push_back({intervals[length - 1][0], intervals[length - 1][1]});
}
return result;
}
};
16. 738. Monotone Increasing Digits
Problem: An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y. Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
Case 1: Input: n = 10, Output: 9
Case 2: Input: n = 1234, Output: 1234
Case 2: Input: n = 332, Output: 299
题目要求小于等于N的最大单调递增的整数, 局部最优: 例如: 98, 一旦出现strNum[i – 1] > strNum[i]的情况(非单调递增), 首先想让strNum[i – 1]–, 然后strNum[i]给为9, 这样这个整数就是89, 即小于98的最大的单调递增整数。全局最优: 得到小于等于N的最大单调递增的整数。但这里局部最优推出全局最优, 还需要其他条件, 即遍历顺序, 和标记从哪一位开始统一改成9。从前向后遍历的话, 遇到strNum[i – 1] > strNum[i]的情况, 让strNum[i – 1]减一, 但此时如果strNum[i – 1]减一了, 可能又小于strNum[i – 2]。举个例子, 数字: 332, 从前向后遍历的话, 那么就把变成了329, 此时2又小于了第一位的3了, 真正的结果应该是299。那么从后向前遍历, 就可以重复利用上次比较得出的结果了, 从后向前遍历332的数值变化为: 332 -> 329 -> 299
class Solution {
public:
// 时间复杂度: O(n), n为数字长度
// 空间复杂度: O(n), 需要一个字符串, 转化为字符串操作更方便
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
// flag用来标记赋值9从哪里开始
// 设置为这个默认值, 为了防止第二个for循环在flag没有被赋值的情况下执行
int flag = strNum.size();
for (int i = strNum.size() - 1; i > 0; i--) {
if (strNum[i - 1] > strNum[i] ) {
flag = i;
strNum[i - 1]--;
}
}
for (int i = flag; i < strNum.size(); i++) {
strNum[i] = '9';
}
return stoi(strNum);
}
};
17. 714. Best Time to Buy and Sell Stock with Transaction Fee