本题如果用动态规划,可能会超时,采用贪心的策略,从后往前遍历数组,记录可到达当前点的最大消耗值,最终判断是否可从初始点到达 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def maxJumpGrade(self , nums: List[int]) -> int: # write code here n = len(nums) if n == 0: return -1 if n == 1: return nums[0] star...

栈,将 s 根据 "/" 分割, 遇到 "" 或 "." 不入栈, 遇到 ".." 且栈有值的情况下，栈顶出栈 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param path string字符串 # @return string字符串 # class Solution: def simplifyPath(self , path: str) -> str: # write code here stack = [] for p in path.split("/"): if p == "" or p == ".": continue if ...

如果给定的数据长度较小，可以采用动态规划，设置 dp, dp[i] 表示 是否可以调到该位置; 状态转移方程为 dp[i] = dp[j] and data[j] + j >= i j < i,由于数据的长度较大，双重循环遍历会超时,采用贪心策略，从后向前遍历数组，看当前位置 + 值 是否 >= 给定的位置,最终判断是否为 0 import sys n = int(sys.stdin.readline().strip()) data = list(map(int, sys.stdin.readline().strip().split())) start = n - 1 for...

二维 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[i][j] 由 dp[i + 1][j] 或 dp[i][j + 1] 中较大的一个转移而来,因为取的是最大值. 初始值, dp[i][i] = 1 i < len(s) 代码如下: import sys s = sys.stdin.readline().strip() n = len(s) ...

动态规划,由于 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(1) exit() if n == 2: print(2) exit() dp = [0 for _ in range(n + 1)] dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, n + 1): for j in range(i): dp[i] += d...

动态规划, 每次走的步骤取决于前两个的状态; 状态转移方程: 当长度 < 2 时,直接返回 cost[0]; 当长度 >= 2 时,当前值取决于min(dp[i-1], dp[i-2]) + cost[i]; 代码如下: class Solution: def minCostClimbingStairs(self , cost: List[int]) -> int: # write code here if len(cost) == 1: return cost[0] n = len(cost) dp = [cost[0], cost[1]] for i in range(2...

dfs, 给每个数字添加一个运算符，直到数字字符串结尾，比较计算结果和目标值是否相同 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param num string字符串 # @param target int整型 # @return string字符串一维数组 # class Solution: def addOpt(self , num: str, target: int) -> List[str]: # write code here res = set() def dfs(idx, path, t): nonlocal res i...

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] > letters[j][1]  # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param letters int整型二维数组 # @return int整型 # class Solution: def maxLetters(self , letters: ...

根据规律计算; 由于数字按照顺序排列: 0,1,2,3,4,5,6,7,8,9 10 ** 1 以内, 步长(位数)为 1 10, 11, 12 ... 99, 10 ** 2 以内,步长为2 100, 101, ... 999, 10 ** 3 以内,步长为3 ... 则设置当前值为 base = 0 n 所在的位置应该在 (base, base + (10 ** step - 10 ** (step - 1)) * step) 之间, n 比累加 base 多了 k = n - base, n 前一个最大的位数为 last = 10 ** (step - 1), n 位所处的数字应在 di...

相同字母不同排列的方式算作一个,则设置 defaultdict 记录每个排序好的字符的相关字符串集合,再根据集合长度排序并加入到最终的结果集中 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param strs string字符串一维数组 # @return string字符串二维数组 # from collections import defaultdict class Solution: def groupAnagrams(self , strs: List[str]) -> List[List[str]]: # write code...

利用动态规划的思想，最大子链表的和只与之前子链表+当前值 和 当前值有关，并用一个全局值记录整个过程中出现的最大值 # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return int整型 # class Solution: def FindGreatestSumOfSubArray(self , head: ListNode) -> int...

自顶向下，判断叶子节点的父节点，如果是将其删除，注意左右子节点有一个是叶子节点即可 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param root TreeNode类 # @return TreeNode类 # class Solution: def pruneLeaves(self , root ): # write code here def l...

二维 dp 问题,初始值 dp[0][0] = grid[0][0] 状态转移方程为： dp[i][j] = dp[i][j - 1] + grid[i][j] i == 0 & j > 0 dp[i][j] = dp[i - 1][j] + grid[i][j] i > 0 & j == 0 dp[i][j] = max(dp[i -1][j], dp[i][j - 1]) + grid[i][j] 最终到达右下角值为 获取礼物的最大价值 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param grid int整...

使用 dp 的思路会超时,利用二分法查找每个数所在的位置,最终排序数组的长度即为最长上升子序列的长度 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 该数组最长严格上升子序列的长度 # @param a int整型一维数组 给定的数组 # @return int整型 # import bisect class Solution: def LIS(self , a: List[int]) -> int: # write code here if not a: return 0 res = 0 data = [] for ai in a: idx =...