贪心算法
122 买卖股票的最佳时机II medium
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回 你能获得的 最大 利润 。
题目中的在同一天出售，相当于不赚不赔，那就和没买没什么区别；
买股票，如果知道了未来的股市行情，肯定是谷底的时候买入，峰值的时候卖出，只要能涨，就卖！这也是本题中贪心所在之处。
所以这道题思路就很简单，只要求出所给数组中，差值为正数的和就可以了，代码如下：
int maxProfit(vector
int sum = 0;
for (int i = 0; i < prices.size() - 1; i++) {
if (prices[i + 1] - prices[i] > 0)
sum += prices[i + 1] - prices[i];
}
return sum;
}
55 跳跃游戏 medium
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
这道题更适合用动态规划求解，既然放在贪心的范围内，要考虑的问题就是贪心在哪？
本题如果是求解如何在达到最后一个阶梯时，跳跃次数最少，更能体现贪心的思想，现在只是判断能不能达到最后一个阶梯。
一个简单的思路是，从头开始遍历，用一个变量记录当前能跳跃到的最远范围，以[2,3,1,1,4]为例，在2的时候，最远跳到第三格，在3的时候，最远跳到第五格，已经等于阶梯长度了，所以返回true。
bool canJump(vector
int maxLength = nums.size() - 1;
if (nums[0] == 0 && nums.size() > 1) return false; // 如果第一步为零，且大于等于两格，自然无法抵达
int howFar = 1; // 排除了前面一种情况，最大能走的步数必然大于1
for (int i = 0; i < nums.size() && i <= howFar; i++) {
int temp = i + nums[i];
if (temp > howFar) howFar = temp;
if (howFar >= maxLength) return true;
}
return false;
}
还可以再优化一下：
bool canJump(vector
int maxLength = nums.size() - 1;
if (nums.size() == 1) return true;
int howFar = 0;
for (int i = 0; i <= howFar; i++) {
howFar = max(howFar, i + nums[i]);
if (howFar >= maxLength) return true;
}
return false;
}
45 跳跃游戏II medium
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
这道题就是我们在上面所说的，如何使用最少的步数跳到最后一个位置。
总体思想还是一致的，要判断当前所能走到的最远范围是哪里。
关键在于什么时候要考虑多走一步。
如果当前下标移动到起初能移动到的最远距离，但是还没有到达终点，就说明一定要多走一步；此时要重新开始计数。
以[2,3,1,1,4]为例，一开始2能走到index = 2的位置，但是如果遍历到此位置还没能达到终点，说明一定要多走一步。
用这种方法求解要考虑，实际上不用走到数组最后的位置，如果能遍历到倒数第二个位置，只有两种可能，当前位置已经达到了此前的最大距离，说明一定要多走一步；和当前位置小于此前的最大距离，说明不用再多走一步就可以达到终点。
依照上述思想，代码如下：
int jump(vector
int res = 0;
int preMaxIndex = 0;
int curMaxIndex = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
curMaxIndex = max(nums[i] + i, curMaxIndex);
if (i == preMaxIndex) {
preMaxIndex = curMaxIndex;
res++;
}
}
return res;
}
1005 K次取反后最大化的数组和 easy
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
逻辑是这样的：
如果有负数，肯定先变负数，而且要变绝对值最大的负数；
如果所有数都是非负数，而且k还大于0，要判断k是否是偶数。如果是偶数，说明没变化；如果是奇数，要变绝对值最小的非负数。
为了便于处理，要对整体数组按照绝对值大小排序，从大到小排和从小到大排都可以，整体代码如下：
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
int largestSumAfterKNegations(vector
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 res = 0;
for (int num: nums) {
res += num;
}
return res;
}
参考阅读
您阅读本篇文章共花了：
发表评论