122.买卖股票的最佳时机 II 🌟🌟
力扣链接 🌟🌟
题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
- 输入: [1,2,3,4,5]
- 输出: 4
- 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
- 输入: [7,6,4,3,1]
- 输出: 0
- 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 40 <= prices[i] <= 10 ^ 4
解题思路
选低点买入，选高点卖出，再选低点买入，高点卖出.....循环
// [7,1,5,3,6,4]
// 第一天买入 -> 第三天卖出
price[2] - price[0] = -2
// 第一天买入 -> 第二天卖出 + 第二天买入 => 第三天卖出
price[1] - price[0] + (price[2] - price[1]) = -2
// 两种方式结果一样，所以这种情况下，不管怎么分，只要把每天的利润加起来，总和都是一样的
因此，可以把利润分解为每天为单位的维度
局部最优：计算每天利润，只要正利润，正数收集全局最优：收集所有的正数之和
代码
var maxProfit = function (prices) {
let result = 0
for (let i = 0; i < prices.length; i++) {
const price = prices[i + 1] - prices[i]
if (price > 0) {
result += price
}
}
return result
}
55. 跳跃游戏 🌟🌟
力扣链接 🌟🌟
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
- 输入: [2,3,1,1,4]
- 输出: true
- 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
- 输入: [3,2,1,0,4]
- 输出: false
- 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
解题思路
当前位置为 3 时，跳一步、两步还是三步呢？
其实跳几步无所谓，关键在于可跳的覆盖范围！即最大的跳跃步数就是可跳跃的覆盖范围，在这个范围内，不管怎么调，一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围可不可以覆盖到终点
局部最优：每次移动取最大跳跃步数，不断更新覆盖范围整体最优：得到最大的覆盖范围，看是否到达终点
- 初始化覆盖范围 cover = 0
- 遍历 cover：计算当前步可覆盖范围 i+nums[i],不断更新 cover
- cover 能到数组最后一项，则返回 true
代码
var canJump = function (nums) {
if (nums.length === 1) return true
let cover = 0
for (let i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i])
// 检查是否到达终点
if (cover >= nums.length - 1) return true
}
return false
}
45.跳跃游戏 II 🌟🌟
力扣链接 🌟🌟
题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
- 输入: [2,3,1,1,4]
- 输出: 2
- 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
解题思路
每次在当前的跳跃范围内，找到能跳的最远的位置，然后跳到那个位置，这样每一步都尽可能跳得远，从而减少总次数。
局部最优：每次移动取最大跳跃步数，如果还没到终点，步数再加一整体最优：一步尽可能多走，得到最小的跳跃步数
- 初始化变量：jumps 记录跳跃次数，currentEnd 表示当前跳跃的边界，farthest 记录全局最远可达位置
- 遍历数组：从第一个位置遍历到倒数第二个位置（最后一个位置无需处理）
- 更新最远可达位置：每一步计算当前位置能到达的最远位置 i + nums[i]，并更新 farthest
- 到达边界时跳跃：当遍历到当前跳跃的边界 currentEnd 时，增加跳跃次数，并将边界更新为全局最远位置 farthest
- 提前终止条件：若更新后的边界已超过或等于终点，提前终止循环
- 返回结果：最终返回最小跳跃次数 jumps
var jump = function (nums) {
let jumps = 0
let currentEnd = 0
let farthest = 0
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(i + num[i], farthest)
if (i === currentEnd) {
jumps++
currentEnd = farthest
// 提前终止条件：若更新后的边界已超过或等于终点，提前终止循环。
if (currentEnd >= nums.length - 1) break
}
}
return jumps
}
1005.K 次取反后最大化的数组和 🌟
力扣链接 🌟
题目描述
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：
- 输入：A = [4,2,3], K = 1
- 输出：5
- 解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。
示例 2：
- 输入：A = [3,-1,0,2], K = 3
- 输出：6
- 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
- 输入：A = [2,-3,-1,5,-4], K = 2
- 输出：13
- 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
- 1 <= A.length <= 10000
- 1 <= K <= 10000
- -100 <= A[i] <= 100
解题思路
此题需要使用两次贪心算法
使数组和最大，那么尽可能将最小的负数变为正数
局部最优：让最小的负数变为正数，当前数值和达到最大整体最优：整个数组和达到最大
当负数都为正数，且 K 还不为 0 时
局部最优：让最小的正数变为负数，当前数值和达到最大整体最优：整个数组和达到最大
排序数组：按绝对值从大到小排序，确保优先处理绝对值大的负数
翻转负数：遍历数组，尽可能将负数翻转为正数，同时减少剩余次数 k
处理剩余次数：若剩余的 k 为奇数，翻转绝对值最小的元素（即第一个元素）以使损失最小
计算总和：累加数组所有元素得到最大和
var largestSumAfterKNegations = function (nums, K) {
nums.sort((a, b) => Math.abs(a) - Math.abs(b))
for (let i = nums.length - 1; i >= 0; i--) {
const num = nums[i]
if (num < 0) {
nums[i] = -num
K--
if (K === 0) break
}
}
while (K > 0) {
nums[0] = -nums[0]
k--
}
return nums.reduce((a, b) => a + b)
}
京ICP备2022027737号
Copyright © 2022 - present @wangxiang