思路：动态规划，dp的i + 1位存储nums的i字符可翻译成字符串的个数 1、如果当前位可以翻译成1-9（a-i），dp[i+1] += dp[i] 2、如果当前位位10-26的个位（j-z），dp[i+1] += dp[i-1] class Solution: def solve(self , nums: str) -> int: # write code here if len(nums) == 0: return 0 dp = [0] * (len(nums) + ...

思路：使用dic记录每一个字符上一次出现的位置（未出现过为-1），当前待判断字符位置 - max（上一次不同字符出现位置，上一次当前字符出现我位置），避免出现（abcba）的情况 class Solution: def lengthOfLongestSubstring(self , s: str) -> int: # write code here if len(s) <= 1: return len(s) dic = {} i = -1 ...

思路：动态规划 1、i == 0，上累加 2、j == 0，左累加 3、i > 0 and j > 0，max(上，左) + 当前 class Solution: def maxValue(self , grid: List[List[int]]) -> int: # write code here if len(grid) == 0 or len(grid[0]) == 0: return 0 dp = [[0]*len(grid[0]) for _ in range(len(...

思路：动态规划 dp[i] = max(dp[i-1] + array[i], array[i]) class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> int: # write code here if len(array) == 0: return 0 dp = [0] * len(array) dp[0] = array[0] ...

思路：强行使用二分查找方法 1、二分查找找最左k，二分查找找最右k 2、位置间距离既为答案 class Solution: def GetNumberOfK(self , data: List[int], k: int) -> int: if k not in data: return 0 if len(data) <= 1: return len(data) left_index = self.get_left_k(data, k) right...

思路：各个区间的数值总个数为 （top - bottom）* position_num 1、判断n是其所在区间的第几位：n - 前面区间的总位数，再除以当前区间每位的position_num 2、判断n的val是什么，bottom + n为其所在区间的位数 3、n % position_num为n指向的val的具***置 注意：bottom，top = 0， 10 bottom，top = top， top * 10 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int整型 # @return int整型 # c...

思路：顺序遍历字符串，取当前字符串与除去当前字符串的全排列中的元素组成新的组合作为结果 注意：递归出口，当字符串为1时，返回当前字符串 class Solution: def Permutation(self , str: str) -> List[str]: if len(str) <= 1: return str result = [] for i in range(len(str)): s1 = str[i] fo...

思路：折半查找，把right坐标值作为target，逐渐缩小最小数字的目标范围 注意： 1、基于旋转数组特性，一定要以right，而不是left作为target 2、数组中出现重复数字时，要先将其移动过相同数值范围，且只移动一个指针，否则可能会跳过最小值 3、最终最小数字在left、right中出现 class Solution: def minNumberInRotateArray(self , rotateArray: List[int]) -> int: # write code here if len(rotateArra...

思路：同样可以采取二叉树最近公共祖先的算法 1、深度优先遍历dfs，判断当前节点是否为o1、o2，先找到的必为祖先 2、递归左右子树 左右子树中均分布o1、o2，则公共祖先为当前节点 均在左，则返回左，均在右，则返回右 注意： 此题有一个小坑，由于存在值为0的val，所以不能用not root判断无结果返回 class Solution: def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int: if not root: return ...

思路：基于二叉搜索树的特点，左边小于根节点，右边大于根节点 1、o1、o2分布在当前节点两边，则当前节点为公共祖先 2、当前节点为o1或o2，当前节点为祖先 3、o1、o2均在当前节点左边，递归查找左子树 4、o1、o2均在当前节点右边，递归查找右子树 class Solution: def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int: if not root: return -1 if (root....

思路： 1、序列化当前节点，序列化左、右子树，返回序列化表示 2、基于序列化表示，找出节点值、节点左子树、右子树的序列化表示形式 3、递归建立当前节点，左子树、右子树，然后拼接后返回当前节点 class Solution: def Serialize(self, root): # write code here if not root: return "{}" left = self.Serialize(root.left) right = self.Serialize(root....

思路： 1、两棵树p1、p2, p1与p2，p1的左与p2的右，p1的右与p2的左相同，则对称 2、递归判断全部节点 class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: # write code here if not pRoot: return True return self.check(pRoot, pRoot) def check(self, p1, p2): ...

思路： 1、判断当前节点是否平衡：左右子树高度之差小于等于1 2、递归判断全部节点是否平衡 class Solution: def IsBalanced_Solution(self , pRoot: TreeNode) -> bool: return self.check(pRoot) def check(self, p): if not p: return True left = self.getHigh(p.left) righ...

思路：先序遍历首位为根，然后基于根在中序遍历中拆分左、右子树，依次递归构建 注意： 1、root：1 2、idx：vin[root.val] 3、len(left) = [:idx] 4、len(right) = [idx+1:] class Solution: def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode: if len(pre) == 0 and len(vin) == 0: return ...