第八章 贪心算法 part02
122.买卖股票的最佳时机II
本题解法很巧妙，本题大家可以先自己思考一下然后再看题解，会有惊喜！
https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for(int i = 0; i < prices.length - 1; i ++){
int cur = prices[i + 1] - prices[i];
if(cur > 0) {
result += cur;
}
}
return result;
}
}
55. 跳跃游戏
本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
for(int i = 0; i <= cover; i ++){
cover = Math.max(cover, nums[i] + i);
if(cover >= nums.length - 1){
return true;
}
}
return false;
}
}
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
for(int i = 0; i <= cover; i ++){
cover = Math.max(cover, nums[i] + i);
if(cover >= nums.length - 1){
return true;
}
}
return false;
}
}
45.跳跃游戏II
本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
class Solution {
public int jump(int[] nums) {
int result = 0;
int cur = 0;
int next = 0;
for(int i = 0; i < nums.length; i++){
next = Math.max(cur, nums[i]+i);
if(cur < nums.length - 1){
cur = next;
result ++;
if(cur >= nums.length - 1){
return result;
}
}
}
return result;
}
}
class Solution {
public int jump(int[] nums) {
int result = 0;
int cur = 0;
int next = 0;
for(int i = 0; i < nums.length; i++){
next = Math.max(cur, nums[i]+i);
if(i == cur){
cur = next;
result ++;
if(cur >= nums.length - 1){
return result;
}
}
}
return result;
}
}
输入
nums =
[2,3,1,1,4]
输出
3
预期结果
2
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int result = 0;
int cur = 0;
int next = 0;
for(int i = 0; i < nums.length; i++){
next = Math.max(next, nums[i]+i);
if(i == cur){
cur = next;
result ++;
if(cur >= nums.length - 1){
break;
}
}
}
return result;
}
}
1005.K次取反后最大化的数组和
本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int i = 0;
while(i < nums.length && k > 0 && nums[i] < 0){
nums[i] = nums[i]*(-1);
i ++;
k --;
}
Arrays.sort(nums);
if(k%2 == 1) nums[0] = nums[0]*(-1);
int sum = 0;
for(int j = 0; j < nums.length; j ++){
sum += nums[j];
}
return sum;
}
}
