学php网站开发好吗,wordpress 主题安装 ftp,自己在家搭建服务器,攀枝花网站推广力扣面试经典150题在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题#xff0c;安装 Debug LeetCode 插件可以免费 debug本文使用 python 语言解题#xff0c;文中 “数组” 通常指 python 列表#xff1b;文中 “指针” 通常指 python 列表索引 文章目录 6. [中等] 轮转…力扣面试经典150题在 VScode 中安装 LeetCode 插件即可使用 VScode 刷题安装 Debug LeetCode 插件可以免费 debug本文使用 python 语言解题文中 “数组” 通常指 python 列表文中 “指针” 通常指 python 列表索引 文章目录 6. [中等] 轮转数组6.1 解法1使用额外的数组6.2 解法2数组翻转 7. [简单] 买卖股票的最佳时机7.1 解法1暴力法7.2 解法2贪心 8. [中等] 买卖股票的最佳时机II8.1 解法1贪心8.2 解法2动态规划 9. [中等] 跳跃游戏9.1 解法1贪心模拟9.2 解法2贪心 10. [中等] 跳跃游戏II10.1 解法1贪心模拟 6. [中等] 轮转数组
题目链接标签数组、数学、双指针
6.1 解法1使用额外的数组
借助一个额外数据将各个元素放到新位置。注意到从整体上看输出数组可以看作是在 k % len(nums) 位置截断然后重新组合可以用 python 的列表操作简单地如下实现class Solution:def rotate(self, nums: List[int], k: int) - None:k k % len(nums)res nums[-k:] nums[:-k]nums[:] res这其实等价于用两个指针分别遍历截断的两部分并将元素依次复制到辅助数组时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( n ) O(n) O(n)
6.2 解法2数组翻转
和方法一一样注意到输出数组可以看作是在 k % len(nums) 位置截断然后重新组合这可以通过三次列表翻转实现示意如下nums -------; k 3
result -------;reverse ------- we can get -------
reverse -- we can get -------
reverse ----- we can get -------下面给出代码使用双指针进行翻转操作class Solution:def rotate(self, nums: List[int], k: int) - None:def _reverse(start, end):while start end:t nums[start]nums[start] nums[end]nums[end] tstart 1end - 1k k % len(nums)_reverse(0, len(nums)-1)_reverse(0, k-1)_reverse(k, len(nums)-1)时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
7. [简单] 买卖股票的最佳时机
题目链接标签数组、动态规划
7.1 解法1暴力法
直接遍历所有可能的买卖组合情况但这种方法会超时def maxProfit(self, prices: List[int]) - int:# 暴力法超时profit -float(inf)for i in range(len(prices)-1):buy prices[i]for j in range(i1, len(prices)):sell prices[j]if sell buy and sell - buy profit:profit sell - buyprofit 0 if profit 0 else profitreturn profit时间复杂度 O ( n 2 ) O(n^2) O(n2)空间复杂度 O ( 1 ) O(1) O(1)
7.2 解法2贪心
只遍历一遍在每个时刻贪心地计算可能的最大利润。为此需要动态地更新截止目前为止的最低买入价class Solution:def maxProfit(self, prices: List[int]) - int:# 贪心动态维护历史最低价进而利用它计算理论最大收益min_price float(inf)max_profit -float(inf)for p in prices:# 动态维护历史最低价if p min_price:min_price p# 基于历史最低价得到在当前时刻卖出的理论最大收益profit p - min_priceif profit max_profit:max_profit profitmax_profit 0 if max_profit 0 else max_profitreturn max_profit时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
8. [中等] 买卖股票的最佳时机II
题目链接标签贪心、数组、动态规划
8.1 解法1贪心
基于贪心的思想实现最大利润意味着每一次可能的盈利都被把握。我们变量把股价曲线折线图在每一个时刻执行收益最大化操作即把每一个上升段都加入总收益中水平或下降段则跳过class Solution:def maxProfit(self, prices: List[int]) - int:max_profit 0for i in range(len(prices)-1):profit prices[i1] - prices[i]if profit 0:max_profit profitreturn max_profit时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
8.2 解法2动态规划
题目设置满足动态规划的三要素 无后效性当前和未来的交易操作不会影响过去交易操作的收益最优子结构在整个交易过程中实现最大收益意味着交易过程中的任意一个时间段的收益都是最优的。问题最优解的结构包含其子问题的最优解重叠子问题当我们递归地自顶向下分解时即把 “最大化前n天收益” 不断地递归分解为 “最大化前n-1天收益同时最大化第n-1天收益” 时出现了要在递归过程中重复求解的重叠子问题比如 “最大化前1天收益”这提示我们使用递推式自底向上的构造解动态规划的自底向上形式或使用带备忘录的递归法动态规划的自顶向下形式 我们使用自底向上的动态规划形式这时需要构造递推公式动态规划中称 “状态转移方程”。定义状态 dp[i][0] 和 dp[i][1] 分别表示第 i i i 天交易完后手里没有和持有股票的最大利润。 对于 dp[i][0] 来说第 i i i 天交易完后手里没有股票意味着要么前一天就没有要么今天卖了递推式为 d p [ i ] [ 0 ] max { d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] p r i c e s [ i ] } dp[i][0]\max\{dp[i−1][0],dp[i−1][1]prices[i]\} dp[i][0]max{dp[i−1][0],dp[i−1][1]prices[i]}对于 dp[i][1] 来说第 i i i 天交易完后手里有股票意味着要么前一天有要么今天刚买递推式为 d p [ i ] [ 1 ] max { d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] } dp[i][1]\max\{dp[i−1][1],dp[i−1][0]−prices[i]\} dp[i][1]max{dp[i−1][1],dp[i−1][0]−prices[i]}根据问题定义第0天交易时有 d p [ 0 ] [ 0 ] 0 , d p [ 0 ] [ 1 ] − p r i c e s [ 0 ] dp[0][0]0,\quad dp[0][1]−prices[0] dp[0][0]0,dp[0][1]−prices[0]由于全部交易结束后持有股票的收益一定低于不持有股票的收益最后返回 d p [ n − 1 ] [ 0 ] dp[n−1][0] dp[n−1][0] 即可 注意到以上状态转移方程1、2中dp[i] 仅与 dp[i-1] 有关而与更早的状态都无关因此不必存储这些无关的状态只需要将 dp[i−1][0] 和 dp[i−1][1] 存放在两个变量中通过它们计算出 dp[i][0] 和 dp[i][1] 并存回对应的变量以便于第 i 1 i1 i1 天的状态转移计算即可class Solution:def maxProfit(self, prices: List[int]) - int:dp0 0 # 今日交易完后手里没有股票的最大利润dp1 -prices[0] # 今日交易完后手里有一支股票的最大利润for i in range(1, len(prices)):dp0_ max(dp0, dp1 prices[i])dp1_ max(dp1, dp0 - prices[i])dp0, dp1 dp0_, dp1_ return dp0时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
9. [中等] 跳跃游戏
题目链接标签贪心、数组、动态规划
9.1 解法1贪心模拟
直接模拟整个转移过程每次都贪心地跳到能去向的最远处直到达到终点或无法前进class Solution:def canJump(self, nums: List[int]) - bool:cur_pos next_pos 0max_range nums[cur_pos] # 当前可达的最大索引位置while True:# 若从当前位置可以直接到目标退出if max_range len(nums) - 1:return True# 考察从当前位置可达的每个新位置可覆盖的最大范围, 贪心地选择可达范围最大处作为转移到的索引位置 next_posfor steps in range(1, nums[cur_pos] 1):next_range cur_pos steps nums[cur_pos steps]if next_range max_range:next_pos cur_pos stepsmax_range next_range# 如果当前位置已经是最佳的且已知当前 max_range 无法到达目标退出if next_pos cur_pos:return False# 去向新索引位置cur_pos next_pos时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
9.2 解法2贪心
对于每一个可达位置 x x x它使得 x 1 , x 2 , ⋯ , x nums [ x ] x1,x2,⋯ ,x\text{nums}[x] x1,x2,⋯ ,xnums[x] 这些连续的位置都可以到达。利用贪心的思想我们遍历数组并在每一步维护当前可达的最大状态如果发现最后的位置可达则返回 true反之若遍历结束后最后位置仍不可达则返回 falseclass Solution:def canJump(self, nums: List[int]) - bool:max_range 0for i, step in enumerate(nums):if i max_range:if i step max_range:max_range i stepif max_range len(nums) - 1:return Truereturn False时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
10. [中等] 跳跃游戏II
题目链接标签贪心、数组、动态规划
10.1 解法1贪心模拟
和 9.1 完全一直直接模拟整个转移过程每次都贪心地跳到能去向的最远处直到达到终点或无法前进。模拟的同时记录总跳跃次数并返回class Solution:def jump(self, nums: List[int]) - int:# 特殊情况直接退出if len(nums) 1:return 0cur_pos next_pos step_cnt 0max_range nums[cur_pos]while True:# 若从当前位置可以直接到目标退出if max_range len(nums) - 1:return step_cnt 1# 考察每一个新位置可以覆盖的最大范围next_pos 设置为范围最大新索引位置for steps in range(1, nums[cur_pos] 1):next_range cur_pos steps nums[cur_pos steps]if next_range max_range:next_pos cur_pos stepsmax_range next_range# 去向新索引位置cur_pos next_posstep_cnt 1时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
