贪心算法练习题：
605. 种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。
可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。
另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。 这个题目，3个元素为一组判断，左 当前 右，其实保证左右都是0 示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
自己写的思路差不多，但是看到一个不错的答案:
bool canPlaceFlowers(std::vector& flowerbed, int n) {
int size = flowerbed.size();
for (int i = 0; i < size; i++) {
// 比如只有一个[0]，i == 0 和 i == size-1就是做这类判断
if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == size - 1 || flowerbed[i + 1] == 0)) {
n--;
flowerbed[i] = 1;
}
}
return n <= 0;
}
作者:
Bowen
bowen_sky
LeetCode See https://leetcode-cn.com/problems/can-place-flowers/
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。
你不知道气球的确切 y 坐标， 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。
可以射出的弓箭的数量 没有限制 ， 弓箭一旦被射出之后，可以无限地前进。 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
自己觉着这道题目，求交集(不算边界包含)，比如{1,2}∩{2,3}为真 output++;
思路1：有序循环比较是否产生包含元素，有过有交集元素就共用一只箭。
思路2：乱序循环，如果可以用同一只箭队列中删除，剩下的元素在一起遍历，直至最后一个。
思路一：
int findMinArrowShots(std::vector<std::vector>& intervals) {
if (intervals.empty()) {
return 0;
}
int n = intervals.size();
std::sort(intervals.begin(), intervals.end(), [](std::vector& a, std::vector& b)
{
return a[1] < b[1];
});
int archery = 0, idx = 0, current_ptr = 0;
while (current_ptr <= n - 1) {
// star最小,end是否包含
if (current_ptr < (n - 1) && intervals[idx][1] - intervals[current_ptr + 1][0] >= 0)
current_ptr++;
else
{
idx = current_ptr = (current_ptr + 1);
archery++; // 进入else,则代表已经浪费一直箭.
}
}
return archery;
}
好家伙提交时候遇到错误，可以将减法替换成两个int大小相比，把减法改成了>=，至此完成测试用49道验证.：
[[-2147483646,-2147483645],[2147483646,2147483647]]
int findMinArrowShots(std::vector<std::vector>& intervals) {
if (intervals.empty()) {
return 0;
}
int n = intervals.size();
std::sort(intervals.begin(), intervals.end(), [](std::vector& a, std::vector& b)
{
return a[1] < b[1];
});
unsigned int archery = 0, idx = 0, current_ptr = 0;
while (current_ptr <= n - 1) {
// star最小,end是否包含
if (current_ptr < (n - 1) && intervals[idx][1] >= intervals[current_ptr + 1][0])
current_ptr++;
else
{
idx = current_ptr = (current_ptr + 1);
archery++; // 进入else,则代表已经浪费一直箭.
}
}
return archery;
}
LeetCode See https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
122. 股票问题
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。 返回 你能获得的 最大 利润 。
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
仔细了看了这道题目脑子比较空白，通过示例可以知道如下:
- 有序的股票价格计算，左到右依次增高(最低买，最高卖)，左到右依次递减(不盈利)，所以使用0(n)这里复杂度，循环如果明天比今天高则卖出
- 乱序无章可循
int maxProfit(std::vector& prices) {
int money = 0, idx = 1; const size_t while_len = prices.size() - 1;
const auto max_money = *max_element(prices.begin(), prices.end());
const auto min_money = *min_element(prices.begin(), prices.end());
if (min_money == prices[0] && max_money == prices[while_len])
return max_money - min_money;
while (idx < while_len)
{
if (prices[idx] > prices[idx - 1])
money += (prices[idx] - prices[idx - 1]);
++idx;
}
return money;
}
LeetCode See https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
665.非递减数列
给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。 我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
示例 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
示例 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
这道题整麻了，搞了两个多小时，测了几十波，思路如下：
- 先判断两个元素大小，[3,4,2,3]，如2<4，那么为false，引用计数ptrcout自减。
- 如果4>3，判断2和3的关系，也就是左右关系，如果3小于等于2，那么修改4为3，反之，修改2为4.
bool checkPossibility(std::vector& nums) {
const int numslens = nums.size();
const int fire = numslens - 1;
if (2 >= numslens)
return true;
int idx = 1, ptrcout = 1, tmpint = 0; bool isflag = false;
do
{
isflag = (nums[idx] >= nums[idx - 1]) ? true : false;
if (false == isflag && 0 == ptrcout--)
return false; // nums[idx - 1] > nums[idx];
else
{
if ((idx < numslens - 1) && nums[idx] > nums[idx + 1])
{
if (ptrcout == 0)
return false;
if (fire > idx && nums[idx - 1] <= nums[idx + 1])
nums[idx] = nums[idx - 1];
else
nums[idx + 1] = nums[idx];
idx++; ptrcout--;
}
}
idx++;
} while (idx < numslens);
return true;
}
LeetCode See: https://leetcode.cn/problems/non-decreasing-array/
