- 分配问题
- 455. 分发饼干（简单贪心）">455. 分发饼干（简单贪心）
- 502.IPO（优先队列）
- 135. 分发糖果（重点）">135. 分发糖果（重点）
- 区间问题
- 435. 无重叠区间">435. 无重叠区间
- 646. 最长数对链（与无重叠区间很像）">646. 最长数对链（与无重叠区间很像）
- 605. 种花问题（没什么含金量）">605. 种花问题（没什么含金量）
- 763. 划分字母区间(巧妙)">763. 划分字母区间(巧妙)
- 122. 买卖股票的最佳时机 II（贪心动规都行，贪心更简单）">122. 买卖股票的最佳时机 II（贪心动规都行，贪心更简单）
- 406. 根据身高重建队列（回看）">406. 根据身高重建队列（回看）
- 665. 非递减数列（难想）">665. 非递减数列（难想）
- 376. 摆动序列（经典贪心）">376. 摆动序列（经典贪心）
- 821. 字符的最短距离(没写出来)">821. 字符的最短距离(没写出来)
分配问题
455. 分发饼干（简单贪心）
简单贪心。
class Solution {public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int n = g.size(), m = s.size(), ret = 0;for(int i = 0, j = 0; i < n && j < m;j++){if(g[i] <= s[j]){i++;ret++;}}return ret;}};
502.IPO（优先队列）
想到怎么写没有想到使用优先队列，先把所有能投资的项目放进优先队列中，每次取顶部最大的元素。
typedef pair<int,int> pii;class Solution {public:int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {int n = profits.size();int curr = 0;priority_queue<int, vector<int>> pq; //最后一个是优先队列的参数，排序方法，这里是从小到大排序vector<pii> arr;for (int i = 0; i < n; ++i) {arr.push_back({capital[i], profits[i]});}sort(arr.begin(), arr.end());//按照最小资本从小到小大排for (int i = 0; i < k; ++i) {while (curr < n && arr[curr].first <= w) {pq.push(arr[curr].second);curr++;}if (!pq.empty()) {w += pq.top();pq.pop();} else {break;}}return w;}};
135. 分发糖果（重点）
- 这一题遍历的方向非常重要，这种想法很有普适性
- 想让后面的遍历的情况受到前面遍历结果的影响
- 如果从前往后遍历，比较左大于右来改变左，这样的化后面的结果就无法利用前面的计算的影响了。假如说第一次是1和2比然后改变1，下一次就会是2和3比改变2，每一次的计算结果不相关，因此不行。正确的是1和2比改变2，2和3比改变3，这样每一次比较的结果就不是孤立的了。
最终是如果左和右比改变左，则必须时从后面往前遍历。反之如果是改变右则必须时从前往后遍历。
class Solution {public:int candy(vector<int>& ratings) {int n = ratings.size();vector<int> vec(n, 1);for(int i = 1; i < n ; i++){if(ratings[i] > ratings[i-1]){vec[i] = vec[i-1] + 1;}}for(int i = n - 1; i >= 1; i--){if(ratings[i-1] > ratings[i]){vec[i-1] = max(vec[i] + 1, vec[i-1]);}}return accumulate(vec.begin(), vec.end(), 0);}};
区间问题
435. 无重叠区间
为了保留更多的区间，区间的结尾非常重要。结尾越小就代表留给后面的区间可用的空间就越多。因此直接使用sort函数来根据区间的结尾进行排序。
如果与前一个结尾发生重叠的区间则直接删除。这里的sort函数使用了lamba表达式的简单写法，来实现自定义排序。
class Solution {public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int> &b){return a[1] < b[1];});int ret = 0, pre = intervals[0][1];int n = intervals.size();for(int i = 1; i < n; i++){if(intervals[i][0] < pre){ret++;} else {pre = intervals[i][1];}}return ret;}};
646. 最长数对链（与无重叠区间很像）
为了保留更多的区间，区间的结尾非常重要。结尾越小就代表留给后面的区间可用的空间就越多。因此直接使用sort函数来根据区间的结尾进行排序。
class Solution {public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end(), [](vector<int> &a, vector<int>b) {return a[1] < b[1];});int n = pairs.size(), ans = 1, r = pairs[0][1];for (int i = 1; i < n; i++) {if (pairs[i][0] > r) {ans++;r = pairs[i][1];}}return ans;}};
605. 种花问题（没什么含金量）
我的写法
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int m = flowerbed.size();
if(n == 0){
return true;
}
if(m == 1){
return flowerbed[0]==0&&n<=1? true:false;
}
if(m>=2&&flowerbed[0] == 0&& flowerbed[1] == 0){
flowerbed[0] = 1;
n--;
}
if(m>=2&&flowerbed[m-1] == 0&& flowerbed[m-2] == 0){
flowerbed[m-1] = 1;
n--;
}
for(int i = 1; i < m-1; i++){
if(flowerbed[i] == 0&& flowerbed[i-1] == 0&& flowerbed[i+1] ==0){
flowerbed[i] = 1;
n--;
}
}
return n<=0? true:false;
}
};
官网解答
- 维护prev表示上一朵已经种植的花的下标，初始时为-1
- 从左往右遍历数组flowerbed，当遇到flowebed[i] = 1时根据prev和i的值计算上一个区间内可以种植花的最多数量，然后令prev = i，继续遍历
- 结束后，根据数组组prev和长度m的值计算最后一个区间内可以种植花的最多数量。
- 判断是否大于n
```cpp
class Solution {
public:
bool canPlaceFlowers(vector
& flowerbed, int n) {
} };int count = 0; int m = flowerbed.size(); int prev = -1; for (int i = 0; i < m; ++i) { if (flowerbed[i] == 1) { if (prev < 0) { count += i / 2; } else { count += (i - prev - 2) / 2; } prev = i; } } if (prev < 0) { count += (m + 1) / 2; } else { count += (m - prev - 1) / 2; } return count >= n;
<a name="NWltT"></a>
### [452. 用最少数量的箭引爆气球](https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/)(简单贪心)
与435不同的是，一个是不需要重叠，一个是重叠越多越好。排序一个是按区间尾从小到大，一个是按区间头从小到大。
```cpp
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
return a[0] < b[0];
});
int ret = 1, n = points.size(), prev = points[0][1];
for(int i = 1; i < n; i++){
if(prev < points[i][0]){
ret++;
prev = points[i][1];
} else if(prev > points[i][1]){
prev = points[i][1];
}
}
return ret;
}
};
763. 划分字母区间(巧妙)
使用一个26空间的数组来存储字符串里面字母最后一次出现的位置。不过这并不是主要的，主要是通过一个end来存储当前前面的最后一个字母出现的位置，当end与当前遍历的i重叠时，就代表没有重复的字母了。
class Solution {
public:
vector<int> partitionLabels(string s) {
int last[26];
int length = s.size();
for (int i = 0; i < length; i++) {
last[s[i] - 'a'] = i;
}
vector<int> partition;
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = max(end, last[s[i] - 'a']);
if (i == end) {
partition.push_back(end - start + 1);
start = end + 1;
}
}
return partition;
}
};
122. 买卖股票的最佳时机 II（贪心动规都行，贪心更简单）
动规
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp0 = 0, dp1 = -prices[0];
for (int i = 1; i < n; ++i) {
int newDp0 = max(dp0, dp1 + prices[i]);
int newDp1 = max(dp1, dp0 - prices[i]);
dp0 = newDp0;
dp1 = newDp1;
}
return dp0;
}
};
贪心
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int n = prices.size();
for (int i = 1; i < n; ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};
406. 根据身高重建队列（回看）
怎么就这么难想啊
class Solution {
public:
static bool cmp(vector<int>& a,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) {
// 按h降序，k升序
sort(people.begin(), people.end(), cmp);
vector<vector<int>> result;
// 身高高的先进，身高矮的不会对之前的结果产生影响
for(int i = 0; i < people.size(); i++)
{
// 找到插入位置
if(people[i][1] >= result.size())
result.push_back(people[i]);
else
// 因为已经插入的都是身高比当前准备插入的元素高
// 因此当前元素只要考虑自己前面有几个比自己高，也就是k的值
// 找到下标位置插入即可
result.insert(result.begin() + people[i][1], people[i]);
}
return result;
}
};
665. 非递减数列（难想）
这一题就是判断改变一个数能不能把数组变成非递减数列
这里的有几种特殊情况 3,4,1,2，以及 -1,4,2,3
想要满足所有条件，应该先比较 nums[i+1] 与 nums[i]的大小，然后再比较nums[i+1] 与nums[i-1]的大小。当nums[i+1] < nums[i]并且nums[i-1] > nums[i+1]时，就是上面的3412的情况，如果直接判断的话，因为只有1比4小，会出现判断错误，此时12都比4要小，而且2比1小，在此时就应该把1改成4，来影响后面的判断。
class Solution {
public:
bool checkPossibility(vector<int> &nums) {
int n = nums.size(), cnt = 0;
for (int i = 0; i < n - 1; ++i) {
int x = nums[i], y = nums[i + 1];
if (x > y) {
cnt++;
if (cnt > 1) {
return false;
}
if (i > 0 && y < nums[i - 1]) {
nums[i + 1] = x;
}
}
}
return true;
}
};
376. 摆动序列（经典贪心）
一开始准备直接用比大小的方式来写 ，太过麻烦，这里直接使用两数之差来代表他们之间的对应关系，是非常重要的。
观察这个序列可以发现，我们不断地交错选择「峰」与「谷」，可以使得该序列尽可能长。证明非常简单：如果我们选择了一个「过渡元素」，那么在原序列中，这个「过渡元素」的两侧有一个「峰」和一个「谷」。不失一般性，我们假设在原序列中的出现顺序为「峰」「过渡元素」「谷」。如果「过渡元素」在选择的序列中小于其两侧的元素，那么「谷」一定没有在选择的序列中出现，我们可以将「过渡元素」替换成「谷」；同理，如果「过渡元素」在选择的序列中大于其两侧的元素，那么「峰」一定没有在选择的序列中出现，我们可以将「过渡元素」替换成「峰」。这样一来，我们总可以将任意满足要求的序列中的所有「过渡元素」替换成「峰」或「谷」。并且由于我们不断地交错选择「峰」与「谷」的方法就可以满足要求，因此这种选择方法就一定可以达到可选元素数量的最大值。
这样，我们只需要统计该序列中「峰」与「谷」的数量即可（注意序列两端的数也是「峰」或「谷」），但需要注意处理相邻的相同元素。
在实际代码中，我们记录当前序列的上升下降趋势。每次加入一个新元素时，用新的上升下降趋势与之前对比，如果出现了「峰」或「谷」，答案加一，并更新当前序列的上升下降趋势。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int prevdiff = nums[1] - nums[0];
int ret = prevdiff != 0 ? 2 : 1;
for (int i = 2; i < n; i++) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
ret++;
prevdiff = diff;
}
}
return ret;
}
};
821. 字符的最短距离(没写出来)
- 用贪心的思想两次遍历，一次从计算左边的c到当前位置的距离，一次计算右边的c到当前位置的距离
- 这里注意idx是最近一个c的下标，为了防止对结果产生干扰。需要设定特定的初始值。如果左边还没有idx的话，idx初始值应该设为-n，这样的话就都比n大，在第二次遍历中就会改变。
- 如果右边还没有idx的话就设置为n×2,这样得到的下标也都比n大
class Solution { public: vector<int> shortestToChar(string s, char c) { int n = s.size(); vector<int> ret(n); for(int i = 0, idx = -n; i < n; i++) { if(s[i] == c) { idx = i; } ret[i] = i - idx; //这里还挺细节，保证最前方的元素一定大于n，会被后面的从右往左取代 } for(int i = n-1, idx = 2*n; i >= 0; i--) { if(s[i] == c) { idx = i; } ret[i] = min(ret[i], idx - i); } return ret; } };
若有收获，就点个赞吧
0 人点赞
