122. 买卖股票的最佳时机 II
给你一个整数数组prices，其中prices[i]是给定股票第i天的价格。
每天，您都可以决定购买和/或出售股票。您在任何时候最多只能持有一股股票。不过，您可以购买并在当天立即出售。
找到并返回您可以获得的最大利润。
示例1：
输入：价格 = [7,1,5,3,6,4]
输出：7
说明：第 2 天买入（价格 = 1），第 3 天卖出（价格 = 5），利润 = 5-1 = 4。
然后在第 4 天买入（价格 = 3）并在第 5 天卖出（价格 = 6），利润 = 6-3 = 3。
总利润为 4 + 3 = 7。
示例2：
输入：价格 = [1,2,3,4,5]
输出：4
说明：第 1 天买入（价格 = 1），第 5 天卖出（价格 = 5），利润 = 5-1 = 4。
总利润为 4。
示例 3：
输入：价格 = [7,6,4,3,1]
输出：0
说明：没有办法盈利，所以我们从来不买股票来实现最大利润0。
限制：
1
0
原始页面
错误代码
public int maxProfit(int[] prices) {
int profit = 0;
int buy = Integer.MAX_VALUE;
int sum = 0;
int peek = 0;
for(int i=0; i<prices.length; i++){
int num = prices[i];
if(num > buy && num > peek){
profit = num - buy;
peek = num;
}
else if((num>buy && num<peek) || num < buy){
sum += profit;
profit = 0;
buy = num;
peek = num;
}
}
return sum+profit;
}
登录后复制
我初始化购买 int MAX_VALUE 并忘记更新，这可能会导致一些错误。
修复此问题并截断代码
精细代码
public int maxProfit(int[] prices) {
if(prices.length <1){
return 0;
}
int profit = 0;
int buy = prices[0];
int sum = 0;
int peek = prices[0];
for(int i=0; i<prices.length; i++){
int num = prices[i];
if( num > peek){
profit = num - buy;
peek = num;
}
else if(num<peek){
sum += profit;
profit = 0;
buy = num;
peek = num;
}
}
sum += profit;
return sum;
}
登录后复制
1005. K 个否定后数组的和最大化
给定一个整数数组 nums 和一个整数 k，按以下方式修改该数组：
选择一个索引 i 并将 nums[i] 替换为 -nums[i]。
您应该准确应用此过程 k 次。您可以多次选择相同的索引 i。
以这种方式修改数组后，返回数组可能的最大和。
示例1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择索引 1，nums 变为 [4,-2,3]。
示例2：
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择索引 (1, 2, 2)，nums 变为 [3,1,0,2]。
示例 3：
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择索引 (1, 4)，nums 变为 [2,3,-1,5,4]。
限制：
1 <= nums.length <= 10^4
-100 <= nums[i] <= 100
1 <= k <= 10^4
原始页面
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
int change = nums[nums.length-1] >=0?0:nums.length-1;
int sum = 0;
for(int i=0; i<nums.length; i++){
if(nums[i] < 0 && k>0){
sum -= nums[i];
k--;
}else{
sum += nums[i];
}
// find the cross over
if(i>0 && nums[i-1]<=0 && nums[i]>0){
if(-nums[i-1]>nums[i]){
change = i;
}else{
change = i-1;
}
}
}
// k>nums.length so we need to run out of these k
if(k>0){
if(k%2!=0){
//find the min abs value
sum -= 2*Math.abs(nums[change]);
}
}
return sum;
}
登录后复制
55. 跳跃游戏
给你一个整数数组 nums。您最初位于数组的第一个索引处，数组中的每个元素代表您在该位置的最大跳跃长度。
如果可以到达最后一个索引，则返回 true，否则返回 false。
示例1：
输入：nums = [2,3,1,1,4]
输出：true
说明：从索引 0 跳 1 步到 1，然后跳 3 步到最后一个索引。
示例2：
输入：nums = [3,2,1,0,4]
输出：假
说明：无论如何，你总是会到达索引 3。它的最大跳转长度为0，这使得它无法到达最后一个索引。
限制：
1
0
错误代码
public boolean canJump(int[] nums) {
//find whether achive the last element so that we only can see whether can reach the second last element
for(int i=0; i<nums.length-1;){
int size = nums[i];
int next = 0;
int nextVal = 0;
if(size == 0){
return false;
}
if(i+size >= nums.length){
return true;
}
//find the max steps among the current step
for(int j=0; j<=size; j++){
// calculate max for both index and value
if(i+j+nums[i+j]>next){
next = i+j+nums[i+j];
}
}
i = next;
}
return true;
}
登录后复制
错误代码2
public boolean canJump(int[] nums) {
if(nums.length==1){
return true;
}
if(nums[0] == 0){
return false;
}
for(int i=0; i<nums.length-1; i++){
if(i+nums[i]>=nums.length-1){
return true;
}
}
return false;
}
登录后复制
public boolean canJump(int[] nums) {
if(nums.length==1){
return true;
}
int range = 0;
for(int i=0; i<=range; i++){
range = Math.max(range, i+nums[i]);
if(range >= nums.length-1){
return true;
}
}
return false;
}
登录后复制
45. 跳跃游戏二
给定一个长度为 n 的 0 索引整数 nums 数组。您最初位于 nums[0].
每个元素nums[i]代表从索引i向前跳转的最大长度。换句话说，如果你在 nums[i]，你可以跳转到任何 nums[i + j]，其中：
0
i+j＜ n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以达到 nums[n - 1]。
示例1：
输入：nums = [2,3,1,1,4]
输出：2
说明：到达最后一个索引的最小跳转次数为 2。从索引 0 到 1 跳转 1 步，然后跳转 3 步到最后一个索引。
示例2：
输入：nums = [2,3,0,1,4]
输出：2
限制：
1
0
保证你能达到nums[n - 1]。
public int jump(int[] nums) {
if(nums.length == 1){
return 0;
}
int step = 0;
int range = 0;
int preRange = 0;
for(int i=0; i<nums.length-1; i++){
range = Math.max(range, i+nums[i]);
if(range >= nums.length-1){
step++;
break;
}
if(i == preRange){
preRange = range;
step++;
}
}
return step;
}
登录后复制
以上是LeetCode Day 贪心算法 第 2 部分的详细内容。更多信息请关注PHP中文网其他相关文章！
