欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 维修 > leetcode【面试经典150系列】(一)

leetcode【面试经典150系列】(一)

2025/3/16 7:14:28 来源:https://blog.csdn.net/weixin_51781852/article/details/146202723  浏览:    关键词:leetcode【面试经典150系列】(一)

目录

121.买卖股票最佳时机

题目描述

示例

算法分析

代码(python3)

122.买卖股票最佳时机II

 题目描述

示例

算法分析

代码(python3)

55.跳跃游戏

题目描述

示例

算法分析

代码

45.跳跃游戏II

题目描述

示例

算法分析

代码


121.买卖股票最佳时机

题目描述

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0

示例

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

这个问题实际上是利用了“贪心算法”的思想。

算法分析

这个算法的目的是找出股票交易中的最大利润,即买入和卖出股票的最佳时机。算法的核心思想是:

  1. 维护一个最小值(mn):这个变量用于记录遍历过的价格中的最小值。这相当于我们在寻找买入股票的最佳时机(即价格最低的时候)。
  2. 计算利润(ans):对于每一个价格,我们计算如果在这个价格卖出股票,那么利润是多少(即当前价格减去之前记录的最小值)。然后,我们更新记录的最大利润(ans)。

为什么说是贪心算法?

  • 局部最优选择:在每一步,我们都选择到目前为止看到的最小值作为可能的买入点,这是一个局部最优选择,因为我们假设在这一点上买入可以最大化后续可能的利润。
  • 无回溯:一旦我们选择了某个点作为“可能的买入点”,我们就不会回头去改变这个选择(除非遇到一个更低的价格)。这符合贪心算法“一旦做出选择,不再更改”的特点。

代码(python3)

class Solution:def maxProfit(self, prices: List[int]) -> int:# mn用来记录前n个最小的值mn = prices[0]# ans用来记录前n个最小的值与当前值的差值的最大值ans = 0for x in prices:mn = min(mn,x)ans = max(ans,x-mn)return ans

122.买卖股票最佳时机II

 题目描述

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 

示例

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

算法分析

遍历数组,如果当天买入第二天会涨,就在第二天卖出。否则当天就不买入。这个方法,最终利润是最大的。

代码(python3)

class Solution:def maxProfit(self, prices: List[int]) -> int:profit = 0for i in range(1, len(prices)):tmp = prices[i] - prices[i - 1]if tmp > 0:profit += tmpreturn profit

55.跳跃游戏

题目描述

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

示例

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

算法分析

遍历每一项,如果当前位置能到达并且大于前面所能到达的最大位置,就更新最大位置

代码

class Solution:def canJump(self, nums: List[int]) -> bool:# 遍历每一项max_i = 0for i,jump in enumerate(nums):# 如果当前位置能到达并且大于前面所能到达的最大位置,就更新最大位置if max_i>=i and i+jump>max_i:max_i = i+jumpreturn max_i>=len(nums)-1

45.跳跃游戏II

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2,从下标为 0 跳到下标为 1 的位置,跳 1步,然后跳3步到达数组的最后一个位置。

算法分析

想象有一条河,0和m一1分别是河的两岸。一开始,你在0,要到n-1。

把区间[i,i+nums[i]]视作一座桥。一开始只能建一座桥,也就是[0,nums[0]]。比如建造了一座从0到4的桥。

下一座桥要选哪个呢?

在可以选的桥中,选择右端点最大的桥。它会让你走的更远。

重复该过程,到达n-1时退出循环。修建的桥的数量就是答案。

代码

class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur_right = 0  # 已建造的桥的右端点next_right = 0  # 下一座桥的右端点的最大值for i in range(len(nums) - 1):# 遍历的过程中,记录下一座桥的最远点next_right = max(next_right, i + nums[i])if i == cur_right:  # 无路可走,必须建桥cur_right = next_right  # 建桥后,最远可以到达 next_rightans += 1return ans

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词