Home

题目链接 这个也做过，树是二叉树而非BST所以不能靠数字来判断，可以考虑找到根节点到两个目标节点的路径，然后依次判断从哪个节点开始节点开始不同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode'...

题目链接 我第一眼看到这个题想到的是类似于前缀和的思路，不过仔细想想应该是不对的，而且也不知道具体该怎么写。看了一下官方题解，来把思路捋一遍。首先，为了算出最大的路径和，我们考虑将该路径分成三部分，分别是节点，左子树和右子树。要求最大的路径和我们需要找到左右子树里各自的最大贡献值。这个贡献值定义是以某个节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值和最大。具体而言，空节点的最大贡献值等于0，非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。因此，如果我们求出了某个节点的左右子节点的最大贡献值，只要将这俩贡献值加上该节点的值就可以求的一个局部的最大路径和，当然如果左右子节点中某个节点的最大贡献值为负数，我们就不会...

题目链接 这个也做过，树是二叉树而非BST所以不能靠数字来判断，可以考虑找到根节点到两个目标节点的路径，然后依次判断从哪个节点开始节点开始不同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode'...

题目链接 我第一眼看到这个题想到的是类似于前缀和的思路，不过仔细想想应该是不对的，而且也不知道具体该怎么写。看了一下官方题解，来把思路捋一遍。首先，为了算出最大的路径和，我们考虑将该路径分成三部分，分别是节点，左子树和右子树。要求最大的路径和我们需要找到左右子树里各自的最大贡献值。这个贡献值定义是以某个节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值和最大。具体而言，空节点的最大贡献值等于0，非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。因此，如果我们求出了某个节点的左右子节点的最大贡献值，只要将这俩贡献值加上该节点的值就可以求的一个局部的最大路径和，当然如果左右子节点中某个节点的最大贡献值为负数，我们就不会...

题目链接 在做lc124.二叉树中的最大路径和的时候顺手做的，没想到没用多久直接一遍就过了，不过我的实现为什么比较慢啊，看了一下别人的哦原来是我可以直接将hasPathSum这个函数本身作为递归的一部分而不需用重新再在里面定义另外一个函数，所以就慢了4ms左右。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def...

题目链接 试着写了一下之前做过的类似的题用的方法，不过好像效率不太高。 这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] def recursion(x): if x == len(nums)-1: cp = copy.deepcopy(nums) res.append(cp) return d = set() ...

题目链接 先是自己写了一下，emmm写的是考察临接的左右子节点是否满足条件，并没有保证整棵子树。要保证正确的话在递归的时候要传递相应的上下界才行。递归的话时间复杂度是O（N），空间复杂度是O（N）。除了递归之外还有一种做法就是利用二叉搜索树的中序遍历能产生一个严格递增的数组的性质，如2所示。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class ...

题目链接 emmm直接把列表里的单词每个都按顺序翻译了一遍再检查是否是已经按照英语的排序正确了。这个算法的时间复杂度是O（NlogN），空间复杂度是O（N）。但是由于我们这样将每个字符都翻译了一遍其实没有必要，更快的实现如2所示，依次比较相邻的两个单词即可，比较都过程是依次比较第一个不同的字母的index是否满足顺序关系，这种方法的一个特殊情况就是当单词不等长的时候要先判断一下。这个算法的时间复杂度是O（N），空间复杂度是O（1）。 class Solution: def isAlienSorted1(self, words: List[str], order: str) -> bool: eng = [chr(ord("a")+x) for x in...

题目链接 这个题，一开始是觉得应该用滑动窗口做，或者动态规划做，可是思路感觉不是特别清晰。看了答案之后才懂的，如1所示是未优化过的，这个算法的时间复杂度是O（N），空间复杂度是O（N）。这个思路简单地说就是用前缀和，在遍历数组的过程中，将前缀和一一记下，并且判断某个时刻所对应的“k-前缀和”的值是否在字典中以及为多少，将该数字加到答案上。啊话说不知道为什么，用现成的defaultdict反而速度快一点。 class Solution: def subarraySum1(self, nums: List[int], k: int) -> int: preSum, ans = 0, 0 preSumFreq = collections.de...

题目链接 一开始我还以为要考虑两个完全一样的词要不要排除呢看来不需要那么更简单了，介绍两种思路，一种是将单词里的字母排序，另外一种是用26个数字编码单词。前一个个算法的时间复杂度是O（NKlogK），K是字符串的最大长度。空间复杂度是O（NK）。后一个算法的时间和空间复杂度都是O（NK）。 class Solution: def groupAnagrams1(self, strs: List[str]) -> List[List[str]]: res = collections.defaultdict(list) for s in strs: ranked = "".join(sorted(s)) ...