正反遍历 leetcode第238题除自身以外数组的乘积 class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: ans = [] tmp = 1 for i in nums: ans.append(tmp) tmp *= i tmp = 1 for i in range(len(nums)-1, -1, -1): ans[i] *= tmp tmp *= nums[i] return ans 语法分析

删除链表指定（非末尾）节点 狸猫换太子 class Solution: def deleteNode(self, node): """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """ node.val = node.next.val node.next = node.next.next

树默认所有节点的值都是唯一的 二叉搜索树从根节点到某节点的路径 def getPath(root: 'TreeNode', target: 'TreeNode') -'TreeNode': path = [] while root != target: path.append(root) if root.val > target.val: root = root.left else: root = root.right path.append(root) return path 二叉搜索树的最近共同祖先

python //= python math.log2() math.trunc(3.14) 位运算 leetcode第231题2的幂 获取二进制最右边的1：x & (-x) -x 是 x 按位取反再加1，算 -x 先 x - 1 再按位取反 def isPowerOfTwo(self, n): return n != 0 and n &

第k个最小元素 假设k总是有效的，1 <= k <= 元素个数 二叉搜索树/二叉查找树 左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。 查询效率高

Big-O是在充分大的输入下，算法的相对快慢 root是树唯一没有入边的节点 叶节点是没有子节点/出边的节点 兄弟节点sibling 层级是根节点到

最大值堆、最小值堆 维护动态数据的最大最小值，考虑堆 第K个最大元素，建立容量为K的最小值堆，堆顶的元素为所求 只用k个容量的优先队列，而不用全部

堆的性质 父节点大于子节点 堆排序 构建大根堆 def heap_adjust(L, start, end): temp = L[start] i = start j = 2 * i while j <= end: if j < end and L[j] < L[j + 1]: j += 1 if temp < L[j]: L[i] = L[j] i = j j = 2 * i else: break L[i]

反转链表 leetcode第206题反转链表 复杂的递归 class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head ptr1, ptr2 = head, head.next while ptr2.next: ptr1 = ptr1.next ptr2 = ptr2.next ptr2.next = ptr1 ptr1.next = None self.reverseList(head) return ptr2 反复的迭代 class

python max key a = {1: 2, 2: 1} max(a.keys(), key=lambda x: a[x]) max(a.keys(), key=a.get) max(a, key=a.get) a = [1, -2] max(a, key=abs) python sum a = [1, -2] sum(i for i in a) 随机找答案并验证 期望的时间复杂度 额外的数组空间与栈空间 经典分治法 摩尔投票