当前位置：首页 > news >正文

代码随想录算法训练营第二十八天

news 2025/7/23 22:10:05

LeetCode.122 买卖股票的最佳时机 II

题目链接买卖股票的最佳时机 II

题解

解题思路

LeetCode.55 跳跃游戏

题目链接跳跃游戏

题解

解题思路

LeetCode.45 跳跃游戏 II

题目链接跳跃游戏 II

题解

解题思路

LeetCode.1005 K次取反后最大化的数组和

题目链接 K次取反后最大化的数组和

题解

解题思路

LeetCode.122 买卖股票的最佳时机 II

题目链接买卖股票的最佳时机 II

题解

class Solution {public int maxProfit(int[] prices) {int res = 0;for(int i = 0;i<prices.length-1;i++){int tmp = prices[i+1] - prices[i]; if(tmp > 0) res += tmp; }   return res;}
}

解题思路

这段代码实现了一个计算股票最大利润的算法。它采用了一种 "贪心" 策略，通过捕捉每一个上涨的机会来实现最大利润。

算法的核心思想是：只要第二天的股价高于当天股价，就进行一次交易（当天买入，第二天卖出），将所有这些正的差价累加起来，就得到了最大利润。

这种方法的时间复杂度是 O (n)，其中 n 是股票价格数组的长度，因为只需要遍历一次数组。空间复杂度是 O (1)，只使用了常数个额外变量。

这个解法适用于 "可以进行多次交易，但不能同时参与多笔交易" 的场景，也就是必须在卖出股票后才能再次买入。

LeetCode.55 跳跃游戏

题目链接跳跃游戏

题解

class Solution {public boolean canJump(int[] nums) {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;}
}

解题思路

这段代码实现了判断能否到达数组最后一个位置的功能，采用了贪心算法的思想，效率较高。

算法的核心思路是：

维护一个变量range，表示当前能够到达的最远索引位置
遍历数组，对于每个索引i，如果i在当前可到达范围内，就更新range为i + nums[i]（从当前位置能到达的最远位置）和原range中的较大值
如果在遍历过程中，range已经大于等于数组最后一个索引，说明能到达终点，直接返回true
如果循环结束后仍未到达终点，则返回false

这种解法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，只使用了常数个额外变量。

LeetCode.45 跳跃游戏 II

题目链接跳跃游戏 II

题解

class Solution {public int jump(int[] nums) {if(nums.length == 1) return 0;int curRange = 0;int maxRange = 0;int count = 0;for(int i = 0;i<=curRange;i++){maxRange = Math.max(maxRange,nums[i] + i);if(maxRange >= nums.length - 1){count ++;break;} if(i == curRange){curRange = maxRange;count ++;}}return count;}
}

解题思路

这段代码实现了求解 "跳跃游戏 II" 的功能，即计算从数组第一个位置跳到最后一个位置所需的最少跳跃次数。这是一道经典的贪心算法应用题目。

算法的核心思路是：

维护两个变量：curRange表示当前跳跃所能到达的最远位置，maxRange表示在当前可到达范围内，下一步能跳的最远位置
遍历数组，不断更新maxRange为当前能到达的最远位置
当遍历到curRange的边界时，说明需要进行一次跳跃，将curRange更新为maxRange，并增加跳跃次数
如果在任何时候maxRange已经覆盖了数组最后一个位置，再跳一次即可到达终点

具体步骤解析：

特殊情况处理：如果数组长度为 1，无需跳跃，直接返回 0
遍历数组中当前可到达的范围（i <= curRange）
每次更新maxRange为当前位置能到达的最远点
当maxRange覆盖终点时，增加一次跳跃次数并结束循环
当到达当前跳跃范围的边界时，进行一次跳跃（更新curRange和count）

该算法的时间复杂度是 O (n)，只需要遍历一次数组；空间复杂度是 O (1)，仅使用了常数个额外变量。

LeetCode.1005 K次取反后最大化的数组和

题目链接 K次取反后最大化的数组和

题解

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {PriorityQueue<Integer> minHeap = new PriorityQueue<>(Arrays.stream(nums).boxed().collect(Collectors.toList()));for(int i = 0;i<k;i++){int tmp = - minHeap.poll();minHeap.offer(tmp);}int res = 0;while (!minHeap.isEmpty()) {res += minHeap.poll();}return res;}
}