弱鸡刷题打卡贴

532. K-diff Pairs in an Array

用一个Map记录array中每个element出现的次数。 然后在分k>0和k=0两种情况在map中寻找

706. Design HashMap

常规的 Hashtable: 每个index是一个linkedlist.

333. Largest BST Subtree


isBST: 当前node 用一个range去检查

largest number of node: 用DFS 从下往上传值

250. Count Univalue Subtrees

DFS从下往上 给self.count + 1
572. Subtree of Another Tree

基本做法: O(|s|*|t|)
高级做法: Merkle hashing + DFS O(|s|+|t|)

572. Subtree of Another Tree
做法1：两层recursion: isSubTree和isSame
做法2：merkle hasing +dfs


21. Merge Two Sorted Lists

recusive做法: 谁小移谁。 递归思想类似reverse linked list

206. Reverse Linked List

iterative做法： while loop结束后还需要reverse最后一个(new head)

7. Reverse Integer
先取得符号。 最后return时check结果。 Python 可以有这样的boolean: -1*2**31 <= res <= 2**31

617. Merge Two Binary Trees

104. Maximum Depth of Binary Tree

110. Balanced Binary Tree

用数字同时表示高度和是否balance: -1(unbalanced), 0, 1 ...
使得从下往上传值时，只要出现一个-1即可直接return False

173. Binary Search Tree Iterator
Inorder traversal分解到init()和next()因为是stack所以先root再root.left

init:  从root开始一路push left child到stack

next:

def next(self):
    node = self.stack.pop()
    x = node.right
    while x:
        self.stack.append(x)
        x = x.left
    return node.val

11. Container With Most Water

两个指针从两端往中间iterate直到相遇。记录下当前最大面积。左右指针谁矮移谁

35. Search Insert Position
binary search. 移L,R时用M-1/M+1。
每个ITERATION同时检查是否出界