fred-coder

题解

/ 注册

全部文章 / 题解（共137篇）

题解 | #几步可以从头跳到尾#

由于数组的长度为 10 ** 5, 双重循环会超时,利用一维 dp, 设置 dp[i] 表示跳至 i 阶时最小的步数, 则 dp[i] = dp[j] + 1, j < i and j 从距离 i 最远的点跳过来, 即 A[j] 在 A[j:i] 中最大(最接近 i); 初始 dp = [...

Python3 动态规划数组

2022-02-24

0 395

题解 | #跳跃游戏(三)#

贪心解法,先判断是否可以走到最后,如果可以,设置 end 为可以跳的最远距离,根据当前位置能跳的最远距离更新 end,代码如下 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型...

Python3 贪心

2022-02-24

0 435

题解 | #跳跃游戏(二)#

本题如果用动态规划,可能会超时,采用贪心的策略,从后往前遍历数组,记录可到达当前点的最大消耗值,最终判断是否可从初始点到达 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 #...

Python3 贪心数组

2022-02-23

0 345

题解 | #简化目录路径#

栈,将 s 根据 "/" 分割, 遇到 "" 或 "." 不入栈, 遇到 ".." 且栈有值的情况下，栈顶出栈 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param path string字符串 # @return string字符串 # c...

Python3 栈

2022-02-23

0 392

题解 | #跳跃游戏(一)#

如果给定的数据长度较小，可以采用动态规划，设置 dp, dp[i] 表示是否可以调到该位置; 状态转移方程为 dp[i] = dp[j] and data[j] + j >= i j < i,由于数据的长度较大，双重循环遍历会超时,采用贪心策略，从后向前遍历数组，看当前位置 + 值是...

Python3 数组贪心

2022-02-22

2 514

题解 | #最长回文子序列#

二维 dp 问题; 设置二维 dp， dp[i][j] 表示以 i 为开始, j 为结束的回文子序列的最长长度; 当 s[i] = s[j] 时, dp[i][j] 由 dp[i + 1][j - 1] 转移过来 + s[i] 和 s[j] 的长度 2 当 s[i] != s[j] 时, dp[...

Python3 字符串动态规划

2022-02-20

5 539

题解 | #跳台阶扩展问题#

动态规划,由于 n 个台阶可以 1, ... n 都可以调过来,状态转移通过 0, 1, ... n - 1 转移 dp[i] = dp[j] j < i import sys n = int(sys.stdin.readline().strip()) if n == 1: print...

Python3 数组动态规划

2022-02-18

3 596

题解 | #最小花费爬楼梯#

动态规划, 每次走的步骤取决于前两个的状态; 状态转移方程: 当长度 < 2 时,直接返回 cost[0]; 当长度 >= 2 时,当前值取决于min(dp[i-1], dp[i-2]) + cost[i]; 代码如下: class Solution: def minCostCl...

Python3 动态规划

2022-02-17

6 1027

题解 | #给表达式添加运算符#

dfs, 给每个数字添加一个运算符，直到数字字符串结尾，比较计算结果和目标值是否相同 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param num string字符串 # @param target int整型 # @return stri...

Python3 字符串递归

2022-02-16

1 519

题解 | #信封嵌套问题#

dp 最大递增子序列问题。先对 letters 进行排序初始化 dp, dp[0] = 1 dp[i] = max(dp[j] + 1, dp[i]) j < i and letters[i][0] > letters[j][0] and letters[i][1] > le...

Python3 数组动态规划

2022-02-16

0 397