greyireland · Jun 23, 2020 · Jun 23, 2020 · Jun 24, 2020 · Jun 24, 2020 · Jun 27, 2020
diff --git a/README.md b/README.md
@@ -1,6 +1,8 @@
-# 算法模板
+# 说明
+
+本项目为原项目 [algorithm-pattern](https://github.com/greyireland/algorithm-pattern) 的 Python3 语言实现版本，原项目使用 go 语言实现，目前已获 ![GitHub stars](https://img.shields.io/github/stars/greyireland/algorithm-pattern?style=social)。在原项目基础上，本项目添加了优先级队列，并查集，图相关算法等内容，基本覆盖了所有基础数据结构和算法，非常适合找工刷题的同学快速上手。以下为原项目 README，目录部分增加了本项目的新内容。
 
-![来刷题了](https://img.fuiboom.com/img/title.png)
+# 算法模板
 
 算法模板，最科学的刷题方式，最快速的刷题路径，一个月从入门到 offer，你值得拥有 🐶~
 
@@ -18,28 +20,31 @@
 
 ### 入门篇 🐶
 
-- [go 语言入门](https://github.com/greyireland/algorithm-pattern/blob/master/introduction/golang.md)
-- [算法快速入门](https://github.com/greyireland/algorithm-pattern/blob/master/introduction/quickstart.md)
+- [使用 Python3 写算法题](./introduction/python.md)
+- [算法快速入门](./introduction/quickstart.md)
 
 ### 数据结构篇 🐰
 
-- [二叉树](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/binary_tree.md)
-- [链表](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/linked_list.md)
-- [栈和队列](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/stack_queue.md)
-- [二进制](https://github.com/greyireland/algorithm-pattern/blob/master/data_structure/binary_op.md)
+- [二叉树](./data_structure/binary_tree.md)
+- [链表](./data_structure/linked_list.md)
+- [栈和队列](./data_structure/stack_queue.md)
+- [优先级队列 (堆)](./data_structure/heap.md)
+- [并查集](./data_structure/union_find.md)
+- [二进制](./data_structure/binary_op.md)
 
 ### 基础算法篇 🐮
 
-- [二分搜索](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/binary_search.md)
-- [排序算法](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/sort.md)
-- [动态规划](https://github.com/greyireland/algorithm-pattern/blob/master/basic_algorithm/dp.md)
+- [二分搜索](./basic_algorithm/binary_search.md)
+- [排序算法](./basic_algorithm/sort.md)
+- [动态规划](./basic_algorithm/dp.md)
+- [图相关算法](./basic_algorithm/graph/)
 
 ### 算法思维 🦁
 
-- [递归思维](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/recursion.md)
-- [滑动窗口思想](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/slide_window.md)
-- [二叉搜索树](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/binary_search_tree.md)
-- [回溯法](https://github.com/greyireland/algorithm-pattern/blob/master/advanced_algorithm/backtrack.md)
+- [递归思维](./advanced_algorithm/recursion.md)
+- [滑动窗口思想](./advanced_algorithm/slide_window.md)
+- [二叉搜索树](./advanced_algorithm/binary_search_tree.md)
+- [回溯法](./advanced_algorithm/backtrack.md)
 
 ## 心得体会
 
@@ -75,7 +80,7 @@
 
 ![剑指offer](https://img.fuiboom.com/img/leetcode_jzoffer.png)
 
-刷题时间可以合理分配，如果打算准备面试了，建议前面两部分 一个半月 （6 周）时间刷完，最后剑指 offer 半个月刷完，边刷可以边投简历进行面试，遇到不会的不用着急，往模板上套就对了，如果面试管给你提示，那就好好做，不要错过这大好机会~
+刷题时间可以合理分配，如果打算准备面试了，建议前面两部分 一个半月 （6 周）时间刷完，最后剑指 offer 半个月刷完，边刷可以边投简历进行面试，遇到不会的不用着急，往模板上套就对了，如果面试官给你提示，那就好好做，不要错过这大好机会~
 
 > 注意点：如果为了找工作刷题，遇到 hard 的题如果有思路就做，没思路先跳过，先把基础打好，再来刷 hard 可能效果会更好~
 

diff --git a/advanced_algorithm/backtrack.md b/advanced_algorithm/backtrack.md
diff --git a/advanced_algorithm/binary_search_tree.md b/advanced_algorithm/binary_search_tree.md
@@ -7,164 +7,165 @@
 
 ## 应用
 
-[validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
+### [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
 
 > 验证二叉搜索树
 
-```go
-/**
- * Definition for a binary tree node.
- * type TreeNode struct {
- *     Val int
- *     Left *TreeNode
- *     Right *TreeNode
- * }
- */
-func isValidBST(root *TreeNode) bool {
-    return dfs(root).valid
-}
-type ResultType struct{
-    max int
-    min int
-    valid bool
-}
-func dfs(root *TreeNode)(result ResultType){
-    if root==nil{
-        result.max=-1<<63
-        result.min=1<<63-1
-        result.valid=true
-        return
-    }
-
-    left:=dfs(root.Left)
-    right:=dfs(root.Right)
-
-    // 1、满足左边最大值<root<右边最小值 && 左右两边valid
-    if root.Val>left.max && root.Val<right.min && left.valid && right.valid {
-        result.valid=true
-    }
-    // 2、更新当前节点的最大最小值
-    result.max=Max(Max(left.max,right.max),root.Val)
-    result.min=Min(Min(left.min,right.min),root.Val)
-    return
-}
-func Max(a,b int)int{
-    if a>b{
-        return a
-    }
-    return b
-}
-func Min(a,b int)int{
-    if a>b{
-        return b
-    }
-    return a
-}
-
+```Python
+class Solution:
+    def isValidBST(self, root: TreeNode) -> bool:
+
+        if root is None:
+            return True
+
+        s = [(root, float('-inf'), float('inf'))]
+        while len(s) > 0:
+            node, low, up = s.pop()
+            if node.left is not None:
+                if node.left.val <= low or node.left.val >= node.val:
+                    return False
+                s.append((node.left, low, node.val))
+            if node.right is not None:
+                if node.right.val <= node.val or node.right.val >= up:
+                    return False
+                s.append((node.right, node.val, up))
+        return True
 ```
 
-[insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
+### [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
 
 > 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
 
-```go
-func insertIntoBST(root *TreeNode, val int) *TreeNode {
-    if root==nil{
-        return &TreeNode{Val:val}
-    }
-    if root.Val<val{
-        root.Right=insertIntoBST(root.Right,val)
-    }else{
-        root.Left=insertIntoBST(root.Left,val)
-    }
-    return root
-}
+```Python
+class Solution:
+    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
+
+        if root is None:
+            return TreeNode(val)
+
+        if val > root.val:
+            root.right = self.insertIntoBST(root.right, val)
+        else:
+            root.left = self.insertIntoBST(root.left, val)
+
+        return root
 ```
 
-[delete-node-in-a-bst](https://leetcode-cn.com/problems/delete-node-in-a-bst/)
+### [delete-node-in-a-bst](https://leetcode-cn.com/problems/delete-node-in-a-bst/)
 
 > 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的  key  对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 
-```go
-/**
- * Definition for a binary tree node.
- * type TreeNode struct {
- *     Val int
- *     Left *TreeNode
- *     Right *TreeNode
- * }
- */
-func deleteNode(root *TreeNode, key int) *TreeNode {
-    // 删除节点分为三种情况：
-    // 1、只有左节点 替换为右
-    // 2、只有右节点 替换为左
-    // 3、有左右子节点 左子节点连接到右边最左节点即可
-    if root ==nil{
-        return root
-    }
-    if root.Val<key{
-        root.Right=deleteNode(root.Right,key)
-    }else if root.Val>key{
-        root.Left=deleteNode(root.Left,key)
-    }else if root.Val==key{
-        if root.Left==nil{
-            return root.Right
-        }else if root.Right==nil{
-            return root.Left
-        }else{
-            cur:=root.Right
-            // 一直向左找到最后一个左节点即可
-            for cur.Left!=nil{
-                cur=cur.Left
-            }
-            cur.Left=root.Left
-            return root.Right
-        }
-    }
-    return root
-}
+```Python
+class Solution:
+    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
+
+        # try to find the node
+        dummy = TreeNode(left=root)
+        parent, node = dummy, root
+        isleft = True
+        while node is not None and node.val != key:
+            parent = node
+            isleft = key < node.val
+            node = node.left if isleft else node.right 
+
+        # if found
+        if node is not None:
+            if node.right is None:
+                if isleft:
+                    parent.left = node.left
+                else:
+                    parent.right = node.left
+            elif node.left is None:
+                if isleft:
+                    parent.left = node.right
+                else:
+                    parent.right = node.right
+            else: 
+                p, n = node, node.left
+                while n.right is not None:
+                    p, n = n, n.right
+                if p != node:
+                    p.right = n.left
+                else:
+                    p.left = n.left
+                n.left, n.right = node.left, node.right
+                if isleft:
+                    parent.left = n
+                else:
+                    parent.right = n
+
+        return dummy.left   
 ```
 
-[balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
+### [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
 
 > 给定一个二叉树，判断它是否是高度平衡的二叉树。
 
-```go
-type ResultType struct{
-    height int
-    valid bool
-}
-func isBalanced(root *TreeNode) bool {
-    return dfs(root).valid
-}
-func dfs(root *TreeNode)(result ResultType){
-    if root==nil{
-        result.valid=true
-        result.height=0
-        return
-    }
-    left:=dfs(root.Left)
-    right:=dfs(root.Right)
-    // 满足所有特点：二叉搜索树&&平衡
-    if left.valid&&right.valid&&abs(left.height,right.height)<=1{
-        result.valid=true
-    }
-    result.height=Max(left.height,right.height)+1
-    return
-}
-func abs(a,b int)int{
-    if a>b{
-        return a-b
-    }
-    return b-a
-}
-func Max(a,b int)int{
-    if a>b{
-        return a
-    }
-    return b
-}
+```Python
+class Solution:
+    def isBalanced(self, root: TreeNode) -> bool:
+
+        # post-order iterative
+
+        s = [[TreeNode(), -1, -1]]
+        node, last = root, None
+        while len(s) > 1 or node is not None:
+            if node is not None:
+                s.append([node, -1, -1])
+                node = node.left
+                if node is None:
+                    s[-1][1] = 0
+            else:
+                peek = s[-1][0]
+                if peek.right is not None and last != peek.right:
+                    node = peek.right
+                else:
+                    if peek.right is None:
+                        s[-1][2] = 0
+                    last, dl, dr = s.pop()
+                    if abs(dl - dr) > 1:
+                        return False
+                    d = max(dl, dr) + 1
+                    if s[-1][1] == -1:
+                        s[-1][1] = d
+                    else:
+                        s[-1][2] = d
+
+        return True
+```
+
+### [valid-bfs-of-bst](./bst_bfs.py)
+
+> 给定一个整数数组，求问此数组是不是一个 BST 的 BFS 顺序。
+
+此题是面试真题，但是没有在 leetcode 上找到原题。由于做法比较有趣也很有 BST 的特点，补充在这供参考。
+
+```Python
+import collections
+
+def bst_bfs(A):
+
+    N = len(A)
+    interval = collections.deque([(float('-inf'), A[0]), (A[0], float('inf'))])
+
+    for i in range(1, N):
+        while interval:
+            lower, upper = interval.popleft()
+            if lower < A[i] < upper:
+                interval.append((lower, A[i]))
+                interval.append((A[i], upper))
+                break
+
+        if not interval:
+            return False
+
+    return True
 
+if __name__ == "__main__":
+    A = [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 12]
+    print(bst_bfs(A))
+    A = [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 7]
+    print(bst_bfs(A))
 ```
 
 ## 练习

diff --git a/advanced_algorithm/bst_bfs.py b/advanced_algorithm/bst_bfs.py
@@ -0,0 +1,25 @@
+import collections
+
+def bst_bfs(A):
+
+    N = len(A)
+    interval = collections.deque([(float('-inf'), A[0]), (A[0], float('inf'))])
+
+    for i in range(1, N):
+        while interval:
+            lower, upper = interval.popleft()
+            if lower < A[i] < upper:
+                interval.append((lower, A[i]))
+                interval.append((A[i], upper))
+                break
+
+        if not interval:
+            return False
+
+    return True
+
+if __name__ == "__main__":
+    A = [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 12]
+    print(bst_bfs(A))
+    A = [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 7]
+    print(bst_bfs(A))
diff --git a/advanced_algorithm/recursion.md b/advanced_algorithm/recursion.md
@@ -6,114 +6,99 @@
 
 ## 示例
 
-[reverse-string](https://leetcode-cn.com/problems/reverse-string/)
+### [reverse-string](https://leetcode-cn.com/problems/reverse-string/)
 
 > 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组  `char[]`  的形式给出。
 
-```go
-func reverseString(s []byte) {
-	res := make([]byte, 0)
-	reverse(s, 0, &res)
-	for i := 0; i < len(s); i++ {
-		s[i] = res[i]
-	}
-}
-func reverse(s []byte, i int, res *[]byte) {
-	if i == len(s) {
-		return
-	}
-	reverse(s, i+1, res)
-	*res = append(*res, s[i])
-}
+```Python
+class Solution:
+    def reverseString(self, s: List[str]) -> None:
+        """
+        Do not return anything, modify s in-place instead.
+        """
+        def rev_rec(s, i, j):
+            if i >= j:
+                return
+            s[i], s[j] = s[j], s[i]
+            rev_rec(s, i + 1, j - 1)
+            return
+
+        rev_rec(s, 0, len(s) - 1)
+
+        return
 ```
 
-[swap-nodes-in-pairs](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
+### [swap-nodes-in-pairs](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
 
 > 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 > **你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。
 
-```go
-func swapPairs(head *ListNode) *ListNode {
-    // 思路：将链表翻转转化为一个子问题，然后通过递归方式依次解决
-    // 先翻转两个，然后将后面的节点继续这样翻转，然后将这些翻转后的节点连接起来
-    return helper(head)
-}
-func helper(head *ListNode)*ListNode{
-    if head==nil||head.Next==nil{
+```Python
+class Solution:
+    def swapPairs(self, head: ListNode) -> ListNode:
+
+        if head is not None and head.next is not None:
+            head_next_pair = self.swapPairs(head.next.next)
+            p = head.next
+            head.next = head_next_pair
+            p.next = head
+            head = p
+
         return head
-    }
-    // 保存下一阶段的头指针
-    nextHead:=head.Next.Next
-    // 翻转当前阶段指针
-    next:=head.Next
-    next.Next=head
-    head.Next=helper(nextHead)
-    return next
-}
 ```
 
-[unique-binary-search-trees-ii](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)
+### [unique-binary-search-trees-ii](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)
 
 > 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
 
-```go
-func generateTrees(n int) []*TreeNode {
-    if n==0{
-        return nil
-    }
-    return generate(1,n)
-
-}
-func generate(start,end int)[]*TreeNode{
-    if start>end{
-        return []*TreeNode{nil}
-    }
-    ans:=make([]*TreeNode,0)
-    for i:=start;i<=end;i++{
-        // 递归生成所有左右子树
-        lefts:=generate(start,i-1)
-        rights:=generate(i+1,end)
-        // 拼接左右子树后返回
-        for j:=0;j<len(lefts);j++{
-            for k:=0;k<len(rights);k++{
-                root:=&TreeNode{Val:i}
-                root.Left=lefts[j]
-                root.Right=rights[k]
-                ans=append(ans,root)
-            }
-        }
-    }
-    return ans
-}
+注意：此题用来训练递归思维有理论意义，但是实际上算法返回的树并不是 deep copy，多个树之间会共享子树。
+
+```Python
+class Solution:
+    def generateTrees(self, n: int) -> List[TreeNode]:
+
+        def generateTrees_rec(i, j):
+
+            if i > j:
+                return [None]
+
+            result = []
+            for m in range(i, j + 1):
+                left = generateTrees_rec(i, m - 1)
+                right = generateTrees_rec(m + 1, j)
+
+                for l in left:
+                    for r in right:
+                        result.append(TreeNode(m, l, r))
+
+            return result
+
+        return generateTrees_rec(1, n) if n > 0 else []
 ```
 
-## 递归+备忘录
+## 递归 + 备忘录 (recursion with memorization, top-down DP)
 
-[fibonacci-number](https://leetcode-cn.com/problems/fibonacci-number/)
+### [fibonacci-number](https://leetcode-cn.com/problems/fibonacci-number/)
 
 > 斐波那契数，通常用  F(n) 表示，形成的序列称为斐波那契数列。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 > F(0) = 0,   F(1) = 1
 > F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 > 给定  N，计算  F(N)。
 
-```go
-func fib(N int) int {
-    return dfs(N)
-}
-var m map[int]int=make(map[int]int)
-func dfs(n int)int{
-    if n < 2{
-        return n
-    }
-    // 读取缓存
-    if m[n]!=0{
-        return m[n]
-    }
-    ans:=dfs(n-2)+dfs(n-1)
-    // 缓存已经计算过的值
-    m[n]=ans
-    return ans
-}
+```Python
+class Solution:
+    def fib(self, N: int) -> int:
+
+        mem = [-1] * (N + 2)
+
+        mem[0], mem[1] = 0, 1
+
+        def fib_rec(n):
+            if mem[n] == -1:
+                mem[n] = fib_rec(n - 1) + fib_rec(n - 2)
+            return mem[n]
+
+        return fib_rec(N)
 ```
 
 ## 练习
@@ -122,3 +107,4 @@ func dfs(n int)int{
 - [ ] [swap-nodes-in-pairs](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
 - [ ] [unique-binary-search-trees-ii](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)
 - [ ] [fibonacci-number](https://leetcode-cn.com/problems/fibonacci-number/)
+
diff --git a/advanced_algorithm/slide_window.md b/advanced_algorithm/slide_window.md
@@ -44,158 +44,138 @@ void slidingWindow(string s, string t) {
 
 ## 示例
 
-[minimum-window-substring](https://leetcode-cn.com/problems/minimum-window-substring/)
+### [minimum-window-substring](https://leetcode-cn.com/problems/minimum-window-substring/)
 
 > 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
 
-```go
-func minWindow(s string, t string) string {
-	// 保存滑动窗口字符集
-	win := make(map[byte]int)
-	// 保存需要的字符集
-	need := make(map[byte]int)
-	for i := 0; i < len(t); i++ {
-		need[t[i]]++
-	}
-	// 窗口
-	left := 0
-	right := 0
-	// match匹配次数
-	match := 0
-	start := 0
-	end := 0
-	min := math.MaxInt64
-	var c byte
-	for right < len(s) {
-		c = s[right]
-		right++
-		// 在需要的字符集里面，添加到窗口字符集里面
-		if need[c] != 0 {
-			win[c]++
-			// 如果当前字符的数量匹配需要的字符的数量，则match值+1
-			if win[c] == need[c] {
-				match++
-			}
-		}
-
-		// 当所有字符数量都匹配之后，开始缩紧窗口
-		for match == len(need) {
-			// 获取结果
-			if right-left < min {
-				min = right - left
-				start = left
-				end = right
-			}
-			c = s[left]
-			left++
-			// 左指针指向不在需要字符集则直接跳过
-			if need[c] != 0 {
-				// 左指针指向字符数量和需要的字符相等时，右移之后match值就不匹配则减一
-				// 因为win里面的字符数可能比较多，如有10个A，但需要的字符数量可能为3
-				// 所以在压死骆驼的最后一根稻草时，match才减一，这时候才跳出循环
-				if win[c] == need[c] {
-					match--
-				}
-				win[c]--
-			}
-		}
-	}
-	if min == math.MaxInt64 {
-		return ""
-	}
-	return s[start:end]
-}
+```Python
+class Solution:
+    def minWindow(self, s: str, t: str) -> str:
+        
+        target = collections.defaultdict(int)
+        window = collections.defaultdict(int)
+        
+        for c in t:
+            target[c] += 1
+            
+        min_size = len(s) + 1
+        min_str = ''
+        
+        l, r, count, num_char = 0, 0, 0, len(target)
+        
+        while r < len(s):
+            c = s[r]
+            r += 1
+
+            if c in target:
+                window[c] += 1
+                
+                if window[c] == target[c]:
+                    count += 1
+                    
+                    if count == num_char:
+                        while l < r and count == num_char:
+                            c = s[l]
+                            l += 1
+                            
+                            if c in target:
+                                window[c] -= 1
+                                
+                                if window[c] == target[c] - 1:
+                                    count -= 1
+                                    
+                        if min_size > r - l + 1:
+                            min_size = r - l + 1
+                            min_str = s[l - 1:r]
+        
+        return min_str
 ```
 
-[permutation-in-string](https://leetcode-cn.com/problems/permutation-in-string/)
+### [permutation-in-string](https://leetcode-cn.com/problems/permutation-in-string/)
 
 > 给定两个字符串  **s1**  和  **s2**，写一个函数来判断  **s2**  是否包含  **s1 **的排列。
 
-```go
-func checkInclusion(s1 string, s2 string) bool {
-	win := make(map[byte]int)
-	need := make(map[byte]int)
-	for i := 0; i < len(s1); i++ {
-		need[s1[i]]++
-	}
-	left := 0
-	right := 0
-	match := 0
-	for right < len(s2) {
-		c := s2[right]
-		right++
-		if need[c] != 0 {
-			win[c]++
-			if win[c] == need[c] {
-				match++
-			}
-		}
-		// 当窗口长度大于字符串长度，缩紧窗口
-		for right-left >= len(s1) {
-			// 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件
-			if match == len(need) {
-				return true
-			}
-			d := s2[left]
-			left++
-			if need[d] != 0 {
-				if win[d] == need[d] {
-					match--
-				}
-				win[d]--
-			}
-		}
-	}
-	return false
-}
-
+```Python
+class Solution:
+    def checkInclusion(self, s1: str, s2: str) -> bool:
+
+        target = collections.defaultdict(int)
+
+        for c in s1:
+            target[c] += 1
+
+        r, num_char = 0, len(target)
+
+        while r < len(s2):
+            if s2[r] in target:
+                l, count = r, 0
+                window = collections.defaultdict(int)
+                while r < len(s2):
+                    c = s2[r]
+                    if c not in target:
+                        break
+                    window[c] += 1
+                    if window[c] == target[c]:
+                        count += 1
+                        if count == num_char:
+                            return True
+                    while window[c] > target[c]:
+                        window[s2[l]] -= 1
+                        if window[s2[l]] == target[s2[l]] - 1:
+                            count -= 1
+                        l += 1
+                    r += 1
+            else:
+                r += 1
+
+        return False
 ```
 
-[find-all-anagrams-in-a-string](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)
+### [find-all-anagrams-in-a-string](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)
 
 > 给定一个字符串  **s **和一个非空字符串  **p**，找到  **s **中所有是  **p **的字母异位词的子串，返回这些子串的起始索引。
 
-```go
-func findAnagrams(s string, p string) []int {
-    win := make(map[byte]int)
-	need := make(map[byte]int)
-	for i := 0; i < len(p); i++ {
-		need[p[i]]++
-	}
-	left := 0
-	right := 0
-	match := 0
-    ans:=make([]int,0)
-	for right < len(s) {
-		c := s[right]
-		right++
-		if need[c] != 0 {
-			win[c]++
-			if win[c] == need[c] {
-				match++
-			}
-		}
-		// 当窗口长度大于字符串长度，缩紧窗口
-		for right-left >= len(p) {
-			// 当窗口长度和字符串匹配，并且里面每个字符数量也匹配时，满足条件
-			if right-left == len(p)&& match == len(need) {
-				ans=append(ans,left)
-			}
-			d := s[left]
-			left++
-			if need[d] != 0 {
-				if win[d] == need[d] {
-					match--
-				}
-				win[d]--
-			}
-		}
-	}
-	return ans
-}
+```Python
+class Solution:
+    def findAnagrams(self, s: str, p: str) -> List[int]:
+        
+        target = collections.defaultdict(int)
+        
+        for c in p:
+            target[c] += 1
+        
+        r, num_char = 0, len(target)
+        
+        results = []
+        while r < len(s):
+            if s[r] in target:
+                l, count = r, 0
+                window = collections.defaultdict(int)
+                while r < len(s):
+                    c = s[r]
+                    if c not in target:
+                        break
+                    window[c] += 1
+                    if window[c] == target[c]:
+                        count += 1
+                        if count == num_char:
+                            results.append(l)
+                            window[s[l]] -= 1
+                            count -= 1
+                            l += 1
+                    while window[c] > target[c]:
+                        window[s[l]] -= 1
+                        if window[s[l]] == target[s[l]] - 1:
+                            count -= 1
+                        l += 1
+                    r += 1
+            else:
+                r += 1
+        
+        return results
 ```
 
-[longest-substring-without-repeating-characters](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
+### [longest-substring-without-repeating-characters](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
 
 > 给定一个字符串，请你找出其中不含有重复字符的   最长子串   的长度。
 > 示例  1:
@@ -204,37 +184,20 @@ func findAnagrams(s string, p string) []int {
 > 输出: 3
 > 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 
-```go
-func lengthOfLongestSubstring(s string) int {
-    // 滑动窗口核心点：1、右指针右移 2、根据题意收缩窗口 3、左指针右移更新窗口 4、根据题意计算结果
-    if len(s)==0{
-        return 0
-    }
-    win:=make(map[byte]int)
-    left:=0
-    right:=0
-    ans:=1
-    for right<len(s){
-        c:=s[right]
-        right++
-        win[c]++
-        // 缩小窗口
-        for win[c]>1{
-            d:=s[left]
-            left++
-            win[d]--
-        }
-        // 计算结果
-        ans=max(right-left,ans)
-    }
-    return ans
-}
-func max(a,b int)int{
-    if a>b{
-        return a
-    }
-    return b
-}
+```Python
+class Solution:
+    def lengthOfLongestSubstring(self, s: str) -> int:
+
+        last_idx = {}
+
+        l, max_length = 0, 0
+        for r, c in enumerate(s):
+            if c in last_idx and last_idx[c] >= l:
+                max_length = max(max_length, r - l)
+                l = last_idx[c] + 1
+            last_idx[c] = r
+
+        return max(max_length, len(s) - l) # note that the last substring is not judged in the loop
 ```
 
 ## 总结

diff --git a/basic_algorithm/binary_search.md b/basic_algorithm/binary_search.md
diff --git a/basic_algorithm/dp.md b/basic_algorithm/dp.md
diff --git a/basic_algorithm/graph/README.md b/basic_algorithm/graph/README.md
@@ -0,0 +1,14 @@
+# 图相关算法
+
+图 (graph) 是一种相当复杂的数据结构，相关算法也多种多样，以下总结一些比较基础且常见的图算法。
+
+### [深度优先搜索，广度优先搜索](./bfs_dfs.md)
+
+### [拓扑排序](./topological_sorting.md)
+
+### [最小生成树](./mst.md)
+
+### [最短路径](./shortest_path.md)
+
+### [图的表示](./graph_representation.md)
+
diff --git a/basic_algorithm/graph/bfs_dfs.md b/basic_algorithm/graph/bfs_dfs.md
@@ -0,0 +1,235 @@
+# 深度优先搜索，广度优先搜索
+
+### 深度优先搜索模板
+
+- 先序，递归
+
+```Python
+def DFS(x):
+    visit(x)
+    for n in neighbor(x):
+        if not visited(n):
+            DFS(n)
+    return
+```
+
+- 先序，迭代，出栈时访问
+
+```Python
+def DFS(x):
+    dfs = [x] # implement by a stack
+    while dfs:
+        v = dfs.pop()
+        if not visited(v):
+            visit(v)
+            for n in neighbor(v):
+                if not visited(n):
+                    dfs.append(n)
+    return
+```
+
+- 后序，递归
+
+```Python
+def DFS(x): # used when need to aggregate results from children
+    discovering(x)
+    for n in neighbor(x):
+        if not discovering(n) and not visited(n):
+            DFS(n)
+    visit(x)
+    return
+```
+
+### 广度优先搜索模板
+
+相对于 dfs 可能收敛更慢，但是可以用来找不带权的最短路径
+
+- 以结点为单位搜索
+
+```Python
+def BFS(x):
+    visit(x)
+    bfs = collections.deque([x])
+    while bfs:
+        v = bfs.popleft()
+        for n in neighbor(v):
+            if not visited(n):
+                visit(n)
+                bfs.append(n)
+    return
+```
+
+- 以层为单位搜索，典型应用是找不带权的最短路径
+
+```Python
+def BFS(x):
+    visit(x)
+    bfs = collections.deque([x])
+    while bfs:
+        num_level = len(bfs)
+        for _ in range(num_level)
+            v = bfs.popleft()
+            for n in neighbor(v):
+                if not visited(v):
+                    visit(n)
+                    bfs.append(n)
+    return
+```
+
+## 例题
+
+### [walls-and-gates](https://leetcode-cn.com/problems/walls-and-gates/)
+
+> 给定一个二维矩阵，矩阵中元素 -1 表示墙或是障碍物，0 表示一扇门，INF (2147483647) 表示一个空的房间。你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。
+
+- 思路：典型的多源最短路径问题，将所有源作为 BFS 的第一层即可
+
+```Python
+inf = 2147483647
+
+class Solution:
+    def wallsAndGates(self, rooms: List[List[int]]) -> None:
+        """
+        Do not return anything, modify rooms in-place instead.
+        """
+
+        if not rooms or not rooms[0]:
+            return
+
+        M, N = len(rooms), len(rooms[0])
+
+        bfs = collections.deque([])
+
+        for i in range(M):
+            for j in range(N):
+                if rooms[i][j] == 0:
+                    bfs.append((i, j))
+
+        dist = 1
+        while bfs:
+            num_level = len(bfs)
+            for _ in range(num_level):
+                r, c = bfs.popleft()
+
+                if r - 1 >= 0 and rooms[r - 1][c] == inf:
+                    rooms[r - 1][c] = dist
+                    bfs.append((r - 1, c))
+
+                if r + 1 < M and rooms[r + 1][c] == inf:
+                    rooms[r + 1][c] = dist
+                    bfs.append((r + 1, c))
+
+                if c - 1 >= 0 and rooms[r][c - 1] == inf:
+                    rooms[r][c - 1] = dist
+                    bfs.append((r, c - 1))
+
+                if c + 1 < N and rooms[r][c + 1] == inf:
+                    rooms[r][c + 1] = dist
+                    bfs.append((r, c + 1))
+
+            dist += 1
+
+        return
+```
+
+### [shortest-bridge](https://leetcode-cn.com/problems/shortest-bridge/)
+
+> 在给定的 01 矩阵 A 中，存在两座岛 (岛是由四面相连的 1 形成的一个连通分量)。现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。
+>
+
+- 思路：DFS 遍历连通分量找边界，从边界开始 BFS找最短路径
+
+```Python
+class Solution:
+    def shortestBridge(self, A: List[List[int]]) -> int:
+
+        M, N = len(A), len(A[0])
+        neighors = ((-1, 0), (1, 0), (0, -1), (0, 1))
+
+        dfs = []
+        bfs = collections.deque([])
+
+        for i in range(M):
+            for j in range(N):
+                if A[i][j] == 1: # start from a 1
+                    dfs.append((i, j))
+                    break
+            if dfs:
+                break
+
+        while dfs:
+            r, c = dfs.pop()
+            if A[r][c] == 1:
+                A[r][c] = -1
+
+                for dr, dc in neighors:
+                    nr, nc = r + dr, c + dc
+                    if 0<= nr < M and 0 <= nc < N:
+                        if A[nr][nc] == 0: # meet and edge
+                            A[nr][nc] = -2
+                            bfs.append((nr, nc))
+                        elif A[nr][nc] == 1:
+                            dfs.append((nr, nc))
+
+        flip = 1
+        while bfs:
+            num_level = len(bfs)
+            for _ in range(num_level):
+                r, c = bfs.popleft()
+
+                for dr, dc in neighors:
+                    nr, nc = r + dr, c + dc
+                    if 0<= nr < M and 0 <= nc < N:
+                        if A[nr][nc] == 0:
+                            A[nr][nc] = -2
+                            bfs.append((nr, nc))
+                        elif A[nr][nc] == 1:
+                            return flip
+            flip += 1
+```
+
+### [sliding-puzzle](https://leetcode-cn.com/problems/sliding-puzzle)
+
+```Python
+class Solution:
+    def slidingPuzzle(self, board: List[List[int]]) -> int:
+
+        next_move = {
+            0: [1, 3],
+            1: [0, 2, 4],
+            2: [1, 5],
+            3: [0, 4],
+            4: [1, 3, 5],
+            5: [2, 4]
+        }
+
+        start = tuple(itertools.chain(*board))
+        target = (1, 2, 3, 4, 5, 0)
+
+        if start == target:
+            return 0
+
+        SPT = set([start])
+        bfs = collections.deque([(start, start.index(0))])
+
+        step = 1
+        while bfs:
+            num_level = len(bfs)
+            for _ in range(num_level):
+                state, idx0 = bfs.popleft()
+
+                for next_step in next_move[idx0]:
+                    next_state = list(state)
+                    next_state[idx0], next_state[next_step] = next_state[next_step], next_state[idx0]
+                    next_state = tuple(next_state)
+
+                    if next_state == target:
+                        return step
+
+                    if next_state not in SPT:
+                        SPT.add(next_state)
+                        bfs.append((next_state, next_step))
+            step += 1
+        return -1
+```
+
diff --git a/basic_algorithm/graph/graph_representation.md b/basic_algorithm/graph/graph_representation.md
@@ -0,0 +1,69 @@
+# 图的表示
+
+图的邻接表和邻接矩阵表示最为常用，但是有时需要建图时这两种表示效率不是很高，因为需要构造每个结点和每一条边。此时使用一些隐式的表示方法可以提升建图效率。
+
+### [word-ladder](https://leetcode-cn.com/problems/word-ladder/)
+
+```Python
+class Solution:
+    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
+
+        N, K = len(wordList), len(beginWord)
+
+        find_end = False
+        for i in range(N):
+            if wordList[i] == endWord:
+                find_end = True
+                break
+
+        if not find_end:
+            return 0
+
+        wordList.append(beginWord)
+        N += 1
+
+        # clustering nodes for efficiency compare to adjacent list
+        cluster = collections.defaultdict(list)
+        for i in range(N):
+            node = wordList[i]
+            for j in range(K):
+                cluster[node[:j] + '*' + node[j + 1:]].append(node)
+
+        # bidirectional BFS
+        visited_start, visited_end = set([beginWord]), set([endWord])
+        bfs_start, bfs_end = collections.deque([beginWord]), collections.deque([endWord])
+        step = 2
+        while bfs_start and bfs_end:
+
+            # start
+            num_level = len(bfs_start)
+            while num_level > 0:
+                node = bfs_start.popleft()
+                for j in range(K):
+                    key = node[:j] + '*' + node[j + 1:]
+                    for n in cluster[key]:
+                        if n in visited_end:
+                            return step * 2 - 2
+                        if n not in visited_start:
+                            visited_start.add(n)
+                            bfs_start.append(n)
+                num_level -= 1
+
+            # end
+            num_level = len(bfs_end)
+            while num_level > 0:
+                node = bfs_end.popleft()
+                for j in range(K):
+                    key = node[:j] + '*' + node[j + 1:]
+                    for n in cluster[key]:
+                        if n in visited_start:
+                            return step * 2 - 1
+                        if n not in visited_end:
+                            visited_end.add(n)
+                            bfs_end.append(n)
+                num_level -= 1
+            step += 1
+
+        return 0
+```
+
diff --git a/basic_algorithm/graph/mst.md b/basic_algorithm/graph/mst.md
@@ -0,0 +1,85 @@
+# 最小生成树
+
+### [minimum-risk-path](https://www.lintcode.com/problem/minimum-risk-path/description)
+
+> 地图上有 m 条无向边，每条边 (x, y, w) 表示位置 m 到位置 y 的权值为 w。从位置 0 到 位置 n 可能有多条路径。我们定义一条路径的危险值为这条路径中所有的边的最大权值。请问从位置 0 到 位置 n 所有路径中最小的危险值为多少？
+
+最小危险值为最小生成树中 0 到 n 路径上的最大边权。以此题为例给出最小生成树的两种经典算法。
+
+- 算法 1: [Kruskal's algorithm]([https://en.wikipedia.org/wiki/Kruskal%27s_algorithm](https://en.wikipedia.org/wiki/Kruskal's_algorithm))，使用[并查集](../../data_structure/union_find.md)实现。
+
+```Python
+# Kruskal's algorithm
+class Solution:
+    def getMinRiskValue(self, N, M, X, Y, W):
+
+        # Kruskal's algorithm with union-find
+        parent = list(range(N + 1))
+        rank = [1] * (N + 1)
+
+        def find(x):
+            if parent[parent[x]] != parent[x]:
+                parent[x] = find(parent[x])
+            return parent[x]
+
+        def union(x, y):
+            px, py = find(x), find(y)
+            if px == py:
+                return False
+
+            if rank[px] > rank[py]:
+                parent[py] = px
+            elif rank[px] < rank[py]:
+                parent[px] = py
+            else:
+                parent[px] = py
+                rank[py] += 1
+
+            return True
+
+        edges = sorted(zip(W, X, Y))
+
+        for w, x, y in edges:
+            if union(x, y) and find(0) == find(N): # early return without constructing MST
+                return w
+```
+
+- 算法 2: [Prim's algorithm]([https://en.wikipedia.org/wiki/Prim%27s_algorithm](https://en.wikipedia.org/wiki/Prim's_algorithm))，使用[优先级队列 (堆)](../../data_structure/heap.md)实现
+
+```Python
+# Prim's algorithm
+class Solution:
+    def getMinRiskValue(self, N, M, X, Y, W):
+
+        # construct graph
+        adj = collections.defaultdict(list)
+        for i in range(M):
+            adj[X[i]].append((Y[i], W[i]))
+            adj[Y[i]].append((X[i], W[i]))
+
+        # Prim's algorithm with min heap
+        MST = collections.defaultdict(list)
+        min_heap = [(w, 0, v) for v, w in adj[0]]
+        heapq.heapify(min_heap)
+
+        while N not in MST:
+            w, p, v = heapq.heappop(min_heap)
+            if v not in MST:
+                MST[p].append((v, w))
+                MST[v].append((p, w))
+                for n, w in adj[v]:
+                    if n not in MST:
+                        heapq.heappush(min_heap, (w, v, n))
+
+        # dfs to search route from 0 to n
+        dfs = [(0, None, float('-inf'))]
+        while dfs:
+            v, p, max_w = dfs.pop()
+            for n, w in MST[v]:
+                cur_max_w = max(max_w, w)
+                if n == N:
+                    return cur_max_w
+                if n != p:
+                    dfs.append((n, v, cur_max_w))
+```
+
diff --git a/basic_algorithm/graph/shortest_path.md b/basic_algorithm/graph/shortest_path.md
@@ -0,0 +1,359 @@
+# 最短路径问题
+
+## BFS
+
+在处理不带权图的最短路径问题时可以使用 BFS。
+
+### [walls-and-gates](https://leetcode-cn.com/problems/walls-and-gates/)
+
+> 给定一个二维矩阵，矩阵中元素 -1 表示墙或是障碍物，0 表示一扇门，INF (2147483647) 表示一个空的房间。你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。
+
+- 思路：典型的多源最短路径问题，将所有源作为 BFS 的第一层即可
+
+```Python
+inf = 2147483647
+
+class Solution:
+    def wallsAndGates(self, rooms: List[List[int]]) -> None:
+        """
+        Do not return anything, modify rooms in-place instead.
+        """
+
+        if not rooms or not rooms[0]:
+            return
+
+        M, N = len(rooms), len(rooms[0])
+
+        bfs = collections.deque([])
+
+        for i in range(M):
+            for j in range(N):
+                if rooms[i][j] == 0:
+                    bfs.append((i, j))
+
+        dist = 1
+        while bfs:
+            num_level = len(bfs)
+            for _ in range(num_level):
+                r, c = bfs.popleft()
+
+                if r - 1 >= 0 and rooms[r - 1][c] == inf:
+                    rooms[r - 1][c] = dist
+                    bfs.append((r - 1, c))
+
+                if r + 1 < M and rooms[r + 1][c] == inf:
+                    rooms[r + 1][c] = dist
+                    bfs.append((r + 1, c))
+
+                if c - 1 >= 0 and rooms[r][c - 1] == inf:
+                    rooms[r][c - 1] = dist
+                    bfs.append((r, c - 1))
+
+                if c + 1 < N and rooms[r][c + 1] == inf:
+                    rooms[r][c + 1] = dist
+                    bfs.append((r, c + 1))
+
+            dist += 1
+
+        return
+```
+
+### [shortest-bridge](https://leetcode-cn.com/problems/shortest-bridge/)
+
+> 在给定的 01 矩阵 A 中，存在两座岛 (岛是由四面相连的 1 形成的一个连通分量)。现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。
+
+- 思路：DFS 遍历连通分量找边界，从边界开始 BFS找最短路径
+
+```Python
+class Solution:
+    def shortestBridge(self, A: List[List[int]]) -> int:
+
+        M, N = len(A), len(A[0])
+        neighors = ((-1, 0), (1, 0), (0, -1), (0, 1))
+
+        dfs = []
+        bfs = collections.deque([])
+
+        for i in range(M):
+            for j in range(N):
+                if A[i][j] == 1: # start from a 1
+                    dfs.append((i, j))
+                    break
+            if dfs:
+                break
+
+        while dfs:
+            r, c = dfs.pop()
+            if A[r][c] == 1:
+                A[r][c] = -1
+
+                for dr, dc in neighors:
+                    nr, nc = r + dr, c + dc
+                    if 0<= nr < M and 0 <= nc < N:
+                        if A[nr][nc] == 0: # meet and edge
+                            A[nr][nc] = -2
+                            bfs.append((nr, nc))
+                        elif A[nr][nc] == 1:
+                            dfs.append((nr, nc))
+
+        flip = 1
+        while bfs:
+            num_level = len(bfs)
+            for _ in range(num_level):
+                r, c = bfs.popleft()
+
+                for dr, dc in neighors:
+                    nr, nc = r + dr, c + dc
+                    if 0<= nr < M and 0 <= nc < N:
+                        if A[nr][nc] == 0:
+                            A[nr][nc] = -2
+                            bfs.append((nr, nc))
+                        elif A[nr][nc] == 1:
+                            return flip
+            flip += 1
+```
+
+## Dijkstra's Algorithm
+
+用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。
+
+### [network-delay-time](https://leetcode-cn.com/problems/network-delay-time/)
+
+- 标准的单源最短路径问题，使用朴素的 Dijikstra 算法即可。
+
+```Python
+class Solution:
+    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, t in times:
+            graph_neighbor[s].append((e, t))
+
+        # Dijkstra
+        SPT = {}
+        min_heap = [(0, K)]
+
+        while min_heap:
+            delay, node = heapq.heappop(min_heap)
+            if node not in SPT:
+                SPT[node] = delay
+                for n, d in graph_neighbor[node]:
+                    if n not in SPT:
+                        heapq.heappush(min_heap, (d + delay, n))
+
+        return max(SPT.values()) if len(SPT) == N else -1
+```
+
+### [cheapest-flights-within-k-stops](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/)
+
+- 在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。
+
+```Python
+class Solution:
+    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, p in flights:
+            graph_neighbor[s].append((e, p))
+
+        # modified Dijkstra
+        prices, steps = {}, {}
+        min_heap = [(0, 0, src)]
+
+        while len(min_heap) > 0:
+            price, step, node = heapq.heappop(min_heap)
+
+            if node == dst: # early return
+                return price
+
+            if node not in prices:
+                prices[node] = price
+
+            steps[node] = step
+            if step <= K:
+                step += 1
+                for n, p in graph_neighbor[node]:
+                    if n not in prices or step < steps[n]:
+                        heapq.heappush(min_heap, (p + price, step, n))
+
+        return -1
+```
+
+## 补充
+
+## Bidrectional BFS
+
+当求点对点的最短路径时，BFS遍历结点数目随路径长度呈指数增长，为缩小遍历结点数目可以考虑从起点 BFS 的同时从终点也做 BFS，当路径相遇时得到最短路径。
+
+### [word-ladder](https://leetcode-cn.com/problems/word-ladder/)
+
+```Python
+class Solution:
+    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
+
+        N, K = len(wordList), len(beginWord)
+
+        find_end = False
+        for i in range(N):
+            if wordList[i] == endWord:
+                find_end = True
+                break
+
+        if not find_end:
+            return 0
+
+        wordList.append(beginWord)
+        N += 1
+
+        # clustering nodes for efficiency compare to adjacent list
+        cluster = collections.defaultdict(list)
+        for i in range(N):
+            node = wordList[i]
+            for j in range(K):
+                cluster[node[:j] + '*' + node[j + 1:]].append(node)
+
+        # bidirectional BFS
+        visited_start, visited_end = set([beginWord]), set([endWord])
+        bfs_start, bfs_end = collections.deque([beginWord]), collections.deque([endWord])
+        step = 2
+        while bfs_start and bfs_end:
+
+            # start
+            num_level = len(bfs_start)
+            while num_level > 0:
+                node = bfs_start.popleft()
+                for j in range(K):
+                    key = node[:j] + '*' + node[j + 1:]
+                    for n in cluster[key]:
+                        if n in visited_end: # if meet, route from start larger by 1 than route from end
+                            return step * 2 - 2
+                        if n not in visited_start:
+                            visited_start.add(n)
+                            bfs_start.append(n)
+                num_level -= 1
+
+            # end
+            num_level = len(bfs_end)
+            while num_level > 0:
+                node = bfs_end.popleft()
+                for j in range(K):
+                    key = node[:j] + '*' + node[j + 1:]
+                    for n in cluster[key]:
+                        if n in visited_start: # if meet, route from start equals route from end
+                            return step * 2 - 1
+                        if n not in visited_end:
+                            visited_end.add(n)
+                            bfs_end.append(n)
+                num_level -= 1
+            step += 1
+
+        return 0
+```
+
+## A* Algorithm
+
+当需要求解有目标的最短路径问题时，BFS 或 Dijkstra's algorithm 可能会搜索过多冗余的其他目标从而降低搜索效率，此时可以考虑使用 A* algorithm。原理不展开，有兴趣可以自行搜索。实现上和 Dijkstra’s algorithm 非常相似，只是优先级需要加上一个到目标点距离的估值，这个估值严格小于等于真正的最短距离时保证得到最优解。当 A* algorithm 中的距离估值为 0 时 退化为 BFS 或 Dijkstra’s algorithm。
+
+### [sliding-puzzle](https://leetcode-cn.com/problems/sliding-puzzle)
+
+- 方法 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。
+
+```Python
+class Solution:
+    def slidingPuzzle(self, board: List[List[int]]) -> int:
+
+        next_move = {
+            0: [1, 3],
+            1: [0, 2, 4],
+            2: [1, 5],
+            3: [0, 4],
+            4: [1, 3, 5],
+            5: [2, 4]
+        }
+
+        start = tuple(itertools.chain(*board))
+        target = (1, 2, 3, 4, 5, 0)
+        target_wrong = (1, 2, 3, 5, 4, 0)
+
+        SPT = set()
+        bfs = collections.deque([(0, start, start.index(0))])
+
+        while bfs:
+            step, state, idx0 = bfs.popleft()
+
+            if state == target:
+                return step
+
+            if state == target_wrong:
+                return -1
+
+            if state not in SPT:
+                SPT.add(state)
+
+                for next_step in next_move[idx0]:
+                    next_state = list(state)
+                    next_state[idx0], next_state[next_step] = next_state[next_step], next_state[idx0]
+                    next_state = tuple(next_state)
+
+                    if next_state not in SPT:
+                        bfs.append((step + 1, next_state, next_step))
+        return -1
+```
+
+- 方法 2：A* algorithm
+
+```Python
+class Solution:
+    def slidingPuzzle(self, board: List[List[int]]) -> int:
+
+        next_move = {
+            0: [1, 3],
+            1: [0, 2, 4],
+            2: [1, 5],
+            3: [0, 4],
+            4: [1, 3, 5],
+            5: [2, 4]
+        }
+
+        start = tuple(itertools.chain(*board))
+        target, target_idx = (1, 2, 3, 4, 5, 0), (5, 0, 1, 2, 3, 4)
+        target_wrong = (1, 2, 3, 5, 4, 0)
+
+        @functools.lru_cache(maxsize=None)
+        def taxicab_dist(x, y):
+            return abs(x // 3 - y // 3) + abs(x % 3 - y % 3)
+
+        def taxicab_sum(state, t_idx):
+            result = 0
+            for i, num in enumerate(state):
+                result += taxicab_dist(i, t_idx[num])
+            return result
+
+        SPT = set()
+        min_heap = [(0 + taxicab_sum(start, target_idx), 0, start, start.index(0))]
+
+        while min_heap:
+            cur_cost, step, state, idx0 = heapq.heappop(min_heap)
+
+            if state == target:
+                return step
+
+            if state == target_wrong:
+                return -1
+
+            if state not in SPT:
+                SPT.add(state)
+
+                for next_step in next_move[idx0]:
+                    next_state = list(state)
+                    next_state[idx0], next_state[next_step] = next_state[next_step], next_state[idx0]
+                    next_state = tuple(next_state)
+                    next_cost = step + 1 + taxicab_sum(next_state, target_idx)
+
+                    if next_state not in SPT:
+                        heapq.heappush(min_heap, (next_cost, step + 1, next_state, next_step))
+        return -1
+```
+
diff --git a/basic_algorithm/graph/topological_sorting.md b/basic_algorithm/graph/topological_sorting.md
@@ -0,0 +1,209 @@
+# 拓扑排序
+
+图的拓扑排序 (topological sorting) 一般用于给定一系列偏序关系，求一个全序关系的题目中。以元素为结点，以偏序关系为边构造有向图，然后应用拓扑排序算法即可得到全序关系。
+
+### [course-schedule-ii](https://leetcode-cn.com/problems/course-schedule-ii/)
+
+> 给定课程的先修关系，求一个可行的修课顺序
+
+非常经典的拓扑排序应用。下面给出 3 种实现方法，可以当做模板使用。
+
+- 方法 1：DFS 的递归实现
+
+```Python
+NOT_VISITED = 0
+DISCOVERING = 1
+VISITED = 2
+
+class Solution:
+    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for course, pre in prerequisites:
+            graph_neighbor[pre].append(course)
+
+        # recursive postorder DFS for topological sort
+        tsort_rev = []
+        status = [NOT_VISITED] * numCourses
+
+        def dfs(course):
+            status[course] = DISCOVERING
+            for n in graph_neighbor[course]:
+                if status[n] == DISCOVERING or (status[n] == NOT_VISITED and not dfs(n)):
+                    return False
+            tsort_rev.append(course)
+            status[course] = VISITED
+            return True
+
+        for course in range(numCourses):
+            if status[course] == NOT_VISITED and not dfs(course):
+                return []
+
+        return tsort_rev[::-1]
+```
+
+- 方法 2：DFS 的迭代实现
+
+```Python
+NOT_VISITED = 0
+DISCOVERING = 1
+VISITED = 2
+
+class Solution:
+    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for course, pre in prerequisites:
+            graph_neighbor[pre].append(course)
+
+        # iterative postorder DFS for topological sort
+        tsort_rev = []
+        status = [NOT_VISITED] * numCourses
+
+        dfs = []
+        for course in range(numCourses):
+            if status[course] == NOT_VISITED:
+                dfs.append(course)
+                status[course] = DISCOVERING
+
+                while dfs:
+                    if graph_neighbor[dfs[-1]]:
+                        n = graph_neighbor[dfs[-1]].pop()
+                        if status[n] == DISCOVERING:
+                            return []
+                        if status[n] == NOT_VISITED:
+                            dfs.append(n)
+                            status[n] = DISCOVERING
+                    else:
+                        tsort_rev.append(dfs.pop())
+                        status[tsort_rev[-1]] = VISITED
+
+        return tsort_rev[::-1]
+```
+
+- 方法 3：[Kahn's algorithm](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm)
+
+```Python
+class Solution:
+    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
+
+        # construct graph with indegree data
+        graph_neighbor = collections.defaultdict(list)
+        indegree = collections.defaultdict(int)
+
+        for course, pre in prerequisites:
+            graph_neighbor[pre].append(course)
+            indegree[course] += 1
+
+        # Kahn's algorithm
+        src_cache = [] # can also use queue
+        for i in range(numCourses):
+            if indegree[i] == 0:
+                src_cache.append(i)
+
+        tsort = []
+        while src_cache:
+            tsort.append(src_cache.pop())
+            for n in graph_neighbor[tsort[-1]]:
+                indegree[n] -= 1
+                if indegree[n] == 0:
+                    src_cache.append(n)
+
+        return tsort if len(tsort) == numCourses else []
+```
+
+### [alien-dictionary](https://leetcode-cn.com/problems/alien-dictionary/)
+
+```Python
+class Solution:
+    def alienOrder(self, words: List[str]) -> str:
+
+        N = len(words)
+
+        if N == 0:
+            return ''
+
+        if N == 1:
+            return words[0]
+
+        # construct graph
+        indegree = {c: 0 for word in words for c in word}
+        graph = collections.defaultdict(list)
+
+        for i in range(N - 1):
+            first, second = words[i], words[i + 1]
+            len_f, len_s = len(first), len(second)
+            find_different = False
+            for j in range(min(len_f, len_s)):
+                f, s = first[j], second[j]
+                if f != s:
+                    if s not in graph[f]:
+                        graph[f].append(s)
+                        indegree[s] += 1
+                    find_different = True
+                    break
+
+            if not find_different and len_f > len_s:
+                return ''
+
+        tsort = []
+        src_cache = [c for c in indegree if indegree[c] == 0]
+
+        while src_cache:
+            tsort.append(src_cache.pop())
+            for n in graph[tsort[-1]]:
+                indegree[n] -= 1
+                if indegree[n] == 0:
+                    src_cache.append(n)
+
+        return ''.join(tsort) if len(tsort) == len(indegree) else ''
+```
+
+### [sequence-reconstruction](https://leetcode-cn.com/problems/sequence-reconstruction/)
+
+Kahn's algorithm 可以判断拓扑排序是否唯一。
+
+```Python
+class Solution:
+    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
+
+        N = len(org)
+        inGraph = [False] * (N + 1)
+        graph_set = collections.defaultdict(set)
+        for seq in seqs:
+            if seq:
+                if seq[0] > N or seq[0] < 1:
+                    return False
+                inGraph[seq[0]] = True
+                for i in range(1, len(seq)):
+                    if seq[i] > N or seq[i] < 1:
+                        return False
+                    inGraph[seq[i]] = True 
+                    graph_set[seq[i - 1]].add(seq[i])
+
+        indegree = collections.defaultdict(int)
+        for node in graph_set:
+            for n in graph_set[node]:
+                indegree[n] += 1
+
+        num_valid, count0, src = 0, -1, 0
+        for i in range(1, N + 1):
+            if inGraph[i] and indegree[i] == 0:
+                count0 += 1
+                src = i
+
+        i = 0
+        while count0 == i and src == org[i]:
+            num_valid += 1
+            for n in graph_set[src]:
+                indegree[n] -= 1
+                if indegree[n] == 0:
+                    count0 += 1
+                    src = n
+            i += 1
+
+        return num_valid == N
+```
+
diff --git a/basic_algorithm/heapsort.py b/basic_algorithm/heapsort.py
@@ -0,0 +1,39 @@
+def heap_adjust(A, start=0, end=None):
+    if end is None:
+        end = len(A)
+
+    while start is not None and start < end // 2:
+        l, r = start * 2 + 1, start * 2 + 2
+        swap = None
+
+        if A[l] > A[start]:
+            swap = l
+        if r < end and A[r] > A[start] and (swap is None or A[r] > A[l]):
+            swap = r
+
+        if swap is not None:
+            A[start], A[swap] = A[swap], A[start]
+
+        start = swap
+
+    return
+
+def heapsort(A):
+
+    # construct max heap
+    n = len(A)
+    for i in range(n // 2 - 1, -1, -1):
+        heap_adjust(A, i)
+
+    # sort
+    for i in range(n - 1, 0, -1):
+        A[0], A[i] = A[i], A[0]
+        heap_adjust(A, end=i)
+
+    return A
+
+# test
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(heapsort(a))
diff --git a/basic_algorithm/mergesort.py b/basic_algorithm/mergesort.py
@@ -0,0 +1,33 @@
+def merge(A, B):
+    C = []
+    i, j = 0, 0
+    while i < len(A) and j < len(B):
+        if A[i] <= B[j]:
+            C.append(A[i])
+            i += 1
+        else:
+            C.append(B[j])
+            j += 1
+
+    if i < len(A):
+        C += A[i:]
+
+    if j < len(B):
+        C += B[j:]
+
+    return C
+
+def mergsort(A):
+    n = len(A)
+    if n < 2:
+        return A[:]
+
+    left = mergsort(A[:n // 2])
+    right = mergsort(A[n // 2:])
+
+    return merge(left, right)
+
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(mergsort(a))
diff --git a/basic_algorithm/quicksort.py b/basic_algorithm/quicksort.py
@@ -0,0 +1,32 @@
+import random
+
+def partition(nums, left, right):
+    if left >= right:
+        return
+
+    pivot_idx = random.randint(left, right)
+    pivot = nums[pivot_idx]
+
+    nums[right], nums[pivot_idx] = nums[pivot_idx], nums[right]
+
+    partition_idx = left
+    for i in range(left, right):
+        if nums[i] < pivot:
+            nums[partition_idx], nums[i] = nums[i], nums[partition_idx]
+            partition_idx += 1
+
+    nums[right], nums[partition_idx] = nums[partition_idx], nums[right]
+
+    partition(nums, partition_idx + 1, right)
+    partition(nums, left, partition_idx - 1)
+
+    return
+
+def quicksort(A):
+    partition(A, 0, len(A) - 1)
+    return A
+
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(quicksort(a))
diff --git a/basic_algorithm/sort.md b/basic_algorithm/sort.md
@@ -4,84 +4,77 @@
 
 ### 快速排序
 
-```go
-func QuickSort(nums []int) []int {
-    // 思路：把一个数组分为左右两段，左段小于右段
-    quickSort(nums, 0, len(nums)-1)
-    return nums
-
-}
-// 原地交换，所以传入交换索引
-func quickSort(nums []int, start, end int) {
-    if start < end {
-        // 分治法：divide
-        pivot := partition(nums, start, end)
-        quickSort(nums, 0, pivot-1)
-        quickSort(nums, pivot+1, end)
-    }
-}
-// 分区
-func partition(nums []int, start, end int) int {
-    // 选取最后一个元素作为基准pivot
-    p := nums[end]
-    i := start
-    // 最后一个值就是基准所以不用比较
-    for j := start; j < end; j++ {
-        if nums[j] < p {
-            swap(nums, i, j)
-            i++
-        }
-    }
-    // 把基准值换到中间
-    swap(nums, i, end)
-    return i
-}
-// 交换两个元素
-func swap(nums []int, i, j int) {
-    t := nums[i]
-    nums[i] = nums[j]
-    nums[j] = t
-}
+```Python
+import random
+
+def partition(nums, left, right):
+    if left >= right:
+        return
+
+    pivot_idx = random.randint(left, right)
+    pivot = nums[pivot_idx]
+
+    nums[right], nums[pivot_idx] = nums[pivot_idx], nums[right]
+
+    partition_idx = left
+    for i in range(left, right):
+        if nums[i] < pivot:
+            nums[partition_idx], nums[i] = nums[i], nums[partition_idx]
+            partition_idx += 1
+
+    nums[right], nums[partition_idx] = nums[partition_idx], nums[right]
+
+    partition(nums, partition_idx + 1, right)
+    partition(nums, left, partition_idx - 1)
+
+    return
+
+def quicksort(A):
+    partition(A, 0, len(A) - 1)
+    return A
+
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(quicksort(a))
 ```
 
 ### 归并排序
 
-```go
-func MergeSort(nums []int) []int {
-    return mergeSort(nums)
-}
-func mergeSort(nums []int) []int {
-    if len(nums) <= 1 {
-        return nums
-    }
-    // 分治法：divide 分为两段
-    mid := len(nums) / 2
-    left := mergeSort(nums[:mid])
-    right := mergeSort(nums[mid:])
-    // 合并两段数据
-    result := merge(left, right)
-    return result
-}
-func merge(left, right []int) (result []int) {
-    // 两边数组合并游标
-    l := 0
-    r := 0
-    // 注意不能越界
-    for l < len(left) && r < len(right) {
-        // 谁小合并谁
-        if left[l] > right[r] {
-            result = append(result, right[r])
-            r++
-        } else {
-            result = append(result, left[l])
-            l++
-        }
-    }
-    // 剩余部分合并
-    result = append(result, left[l:]...)
-    result = append(result, right[r:]...)
-    return
-}
+```Python
+def merge(A, B):
+    C = []
+    i, j = 0, 0
+    while i < len(A) and j < len(B):
+        if A[i] <= B[j]:
+            C.append(A[i])
+            i += 1
+        else:
+            C.append(B[j])
+            j += 1
+
+    if i < len(A):
+        C += A[i:]
+
+    if j < len(B):
+        C += B[j:]
+
+    return C
+
+def mergsort(A):
+    n = len(A)
+    if n < 2:
+        return A[:]
+
+    left = mergsort(A[:n // 2])
+    right = mergsort(A[n // 2:])
+
+    return merge(left, right)
+
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(mergsort(a))
 ```
 
 ### 堆排序
@@ -98,57 +91,109 @@ func merge(left, right []int) (result []int) {
 
 核心代码
 
-```go
-package main
-
-func HeapSort(a []int) []int {
-    // 1、无序数组a
-	// 2、将无序数组a构建为一个大根堆
-	for i := len(a)/2 - 1; i >= 0; i-- {
-		sink(a, i, len(a))
-	}
-	// 3、交换a[0]和a[len(a)-1]
-	// 4、然后把前面这段数组继续下沉保持堆结构，如此循环即可
-	for i := len(a) - 1; i >= 1; i-- {
-		// 从后往前填充值
-		swap(a, 0, i)
-		// 前面的长度也减一
-		sink(a, 0, i)
-	}
-	return a
-}
-func sink(a []int, i int, length int) {
-	for {
-		// 左节点索引(从0开始，所以左节点为i*2+1)
-		l := i*2 + 1
-		// 有节点索引
-		r := i*2 + 2
-		// idx保存根、左、右三者之间较大值的索引
-		idx := i
-		// 存在左节点，左节点值较大，则取左节点
-		if l < length && a[l] > a[idx] {
-			idx = l
-		}
-		// 存在有节点，且值较大，取右节点
-		if r < length && a[r] > a[idx] {
-			idx = r
-		}
-		// 如果根节点较大，则不用下沉
-		if idx == i {
-			break
-		}
-		// 如果根节点较小，则交换值，并继续下沉
-		swap(a, i, idx)
-		// 继续下沉idx节点
-		i = idx
-	}
-}
-func swap(a []int, i, j int) {
-	a[i], a[j] = a[j], a[i]
-}
+```Python
+def heap_adjust(A, start=0, end=None):
+    if end is None:
+        end = len(A)
+
+    while start is not None and start < end // 2:
+        l, r = start * 2 + 1, start * 2 + 2
+        swap = None
+
+        if A[l] > A[start]:
+            swap = l
+        if r < end and A[r] > A[start] and (swap is None or A[r] > A[l]):
+            swap = r
+
+        if swap is not None:
+            A[start], A[swap] = A[swap], A[start]
+
+        start = swap
+
+    return
+
+def heapsort(A):
+
+    # construct max heap
+    n = len(A)
+    for i in range(n // 2 - 1, -1, -1):
+        heap_adjust(A, i)
+
+    # sort
+    for i in range(n - 1, 0, -1):
+        A[0], A[i] = A[i], A[0]
+        heap_adjust(A, end=i)
+
+    return A
+
+# test
+if __name__ == '__main__':
+    a = [7, 6, 8, 5, 2, 1, 3, 4, 0, 9, 10]
+    print(a)
+    print(heapsort(a))
+```
+
+## 题目
+
+### [kth-largest-element-in-an-array](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)
+
+- 思路 1: sort 后取第 k 个，最简单直接，复杂度 O(N log N) 代码略
+
+- 思路 2: 使用最小堆，复杂度 O(N log k)
 
+```Python
+class Solution:
+    def findKthLargest(self, nums: List[int], k: int) -> int:
+        # note that in practice there is a more efficient python build-in function heapq.nlargest(k, nums)
+        min_heap = []
+
+        for num in nums:
+            if len(min_heap) < k:
+                heapq.heappush(min_heap, num)
+            else:
+                if num > min_heap[0]:
+                    heapq.heappushpop(min_heap, num)
+
+        return min_heap[0]
 ```
 
+- 思路 3: [Quick select](https://en.wikipedia.org/wiki/Quickselect)，方式类似于快排，每次 partition 后检查 pivot 是否为第 k 个元素，如果是则直接返回，如果比 k 大，则继续 partition 小于 pivot 的元素，如果比 k 小则继续 partition 大于 pivot 的元素。相较于快排，quick select 每次只需 partition 一侧，因此平均复杂度为 O(N)。
+
+```Python
+class Solution:
+    def findKthLargest(self, nums: List[int], k: int) -> int:
+
+        k -= 1 # 0-based index
+
+        def partition(left, right):
+            pivot_idx = random.randint(left, right)
+            pivot = nums[pivot_idx]
+
+            nums[right], nums[pivot_idx] = nums[pivot_idx], nums[right]
+
+            partition_idx = left
+            for i in range(left, right):
+                if nums[i] > pivot:
+                    nums[partition_idx], nums[i] = nums[i], nums[partition_idx]
+                    partition_idx += 1
+
+            nums[right], nums[partition_idx] = nums[partition_idx], nums[right]
+
+            return partition_idx
+
+        left, right = 0, len(nums) - 1
+        while True:
+            partition_idx = partition(left, right)
+            if partition_idx == k:
+                return nums[k]
+            elif partition_idx < k:
+                left = partition_idx + 1
+            else:
+                right = partition_idx - 1
+```
+
+
+
 ## 参考
 
 [十大经典排序](https://www.cnblogs.com/onepixel/p/7674659.html)

diff --git a/data_structure/binary_op.md b/data_structure/binary_op.md
@@ -28,164 +28,167 @@ diff=(n&(n-1))^n
 
 ## 常见题目
 
-[single-number](https://leetcode-cn.com/problems/single-number/)
+### [single-number](https://leetcode-cn.com/problems/single-number/)
 
 > 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 
-```go
-func singleNumber(nums []int) int {
-    // 10 ^10 == 00
-    // 两个数异或就变成0
-    result:=0
-    for i:=0;i<len(nums);i++{
-        result=result^nums[i]
-    }
-    return result
-}
+```Python
+class Solution:
+    def singleNumber(self, nums: List[int]) -> int:
+
+        out = 0
+        for num in nums:
+            out ^= num
+
+        return out
 ```
 
-[single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)
+### [single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)
 
 > 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
 
-```go
-func singleNumber(nums []int) int {
-	// 统计每位1的个数
-	var result int
-	for i := 0; i < 64; i++ {
-		sum := 0
-		for j := 0; j < len(nums); j++ {
-			// 统计1的个数
-			sum += (nums[j] >> i) & 1
-		}
-		// 还原位00^10=10 或者用| 也可以
-		result ^= (sum % 3) << i
-	}
-	return result
-}
+```Python
+class Solution:
+    def singleNumber(self, nums: List[int]) -> int:
+        seen_once = seen_twice = 0
+
+        for num in nums:
+            seen_once = ~seen_twice & (seen_once ^ num)
+            seen_twice = ~seen_once & (seen_twice ^ num)
+
+        return seen_once
 ```
 
-[single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)
+### [single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)
 
 > 给定一个整数数组  `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
 
-```go
-func singleNumber(nums []int) []int {
-    // a=a^b
-    // b=a^b
-    // a=a^b
-    // 关键点怎么把a^b分成两部分,方案：可以通过diff最后一个1区分
-
-    diff:=0
-    for i:=0;i<len(nums);i++{
-        diff^=nums[i]
-    }
-    result:=[]int{diff,diff}
-    // 去掉末尾的1后异或diff就得到最后一个1的位置
-    diff=(diff&(diff-1))^diff
-    for i:=0;i<len(nums);i++{
-        if diff&nums[i]==0{
-            result[0]^=nums[i]
-        }else{
-            result[1]^=nums[i]
-        }
-    }
-    return result
-}
+```Python
+class Solution:
+    def singleNumber(self, nums: int) -> List[int]:
+        # difference between two numbers (x and y) which were seen only once
+        bitmask = 0
+        for num in nums:
+            bitmask ^= num
+
+        # rightmost 1-bit diff between x and y
+        diff = bitmask & (-bitmask)
+
+        x = 0
+        for num in nums:
+            # bitmask which will contain only x
+            if num & diff:
+                x ^= num
+
+        return [x, bitmask^x]
 ```
 
-[number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)
+### [number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)
 
 > 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’  的个数（也被称为[汉明重量](https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F)）。
 
-```go
-func hammingWeight(num uint32) int {
-    res:=0
-    for num!=0{
-        num=num&(num-1)
-        res++
-    }
-    return res
-}
+```Python
+class Solution:
+    def hammingWeight(self, n: int) -> int:
+        num_ones = 0
+        while n > 0:
+            num_ones += 1
+            n &= n - 1
+        return num_ones
 ```
 
-[counting-bits](https://leetcode-cn.com/problems/counting-bits/)
+### [counting-bits](https://leetcode-cn.com/problems/counting-bits/)
 
 > 给定一个非负整数  **num**。对于  0 ≤ i ≤ num  范围中的每个数字  i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 
-```go
-func countBits(num int) []int {
-    res:=make([]int,num+1)
-
-    for i:=0;i<=num;i++{
-        res[i]=count1(i)
-    }
-    return res
-}
-func count1(n int)(res int){
-    for n!=0{
-        n=n&(n-1)
-        res++
-    }
-    return
-}
+- 思路：利用上一题的解法容易想到 O(nk) 的解法，k 为位数。但是实际上可以利用动态规划将复杂度降到 O(n)，想法其实也很简单，即当前数的 1 个数等于比它少一个 1 的数的结果加 1。下面给出三种 DP 解法
+
+```Python
+# x <- x // 2
+class Solution:
+    def countBits(self, num: int) -> List[int]:
+
+        num_ones = [0] * (num + 1)
+
+        for i in range(1, num + 1):
+            num_ones[i] = num_ones[i >> 1] + (i & 1) # 注意位运算的优先级
+
+        return num_ones
+```
+
+```Python
+# x <- x minus right most 1
+class Solution:
+    def countBits(self, num: int) -> List[int]:
+
+        num_ones = [0] * (num + 1)
+
+        for i in range(1, num + 1):
+            num_ones[i] = num_ones[i & (i - 1)] + 1
+
+        return num_ones
 ```
 
-另外一种动态规划解法
-
-```go
-func countBits(num int) []int {
-    res:=make([]int,num+1)
-    for i:=1;i<=num;i++{
-        // 上一个缺1的元素+1即可
-        res[i]=res[i&(i-1)]+1
-    }
-    return res
-}
+```Python
+# x <- x minus left most 1
+class Solution:
+    def countBits(self, num: int) -> List[int]:
+
+        num_ones = [0] * (num + 1)
+
+        left_most = 1
+
+        while left_most <= num:
+            for i in range(left_most):
+                if i + left_most > num:
+                    break
+                num_ones[i + left_most] = num_ones[i] + 1
+            left_most <<= 1
+
+        return num_ones
 ```
 
-[reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)
+### [reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)
 
 > 颠倒给定的 32 位无符号整数的二进制位。
 
-思路：依次颠倒即可
-
-```go
-func reverseBits(num uint32) uint32 {
-    var res uint32
-    var pow int=31
-    for num!=0{
-        // 把最后一位取出来，左移之后累加到结果中
-        res+=(num&1)<<pow
-        num>>=1
-        pow--
-    }
-    return res
-}
+思路：简单想法依次颠倒即可。更高级的想法是考虑到处理超长比特串时可能出现重复的pattern，此时如果使用 cache 记录出现过的 pattern 并在重复出现时直接调用结果可以节约时间复杂度，具体可以参考 leetcode 给出的解法。
+
+```Python
+import functools
+
+class Solution:
+    def reverseBits(self, n):
+        ret, power = 0, 24
+        while n:
+            ret += self.reverseByte(n & 0xff) << power
+            n = n >> 8
+            power -= 8
+        return ret
+
+    # memoization with decorator
+    @functools.lru_cache(maxsize=256)
+    def reverseByte(self, byte):
+        return (byte * 0x0202020202 & 0x010884422010) % 1023
 ```
 
-[bitwise-and-of-numbers-range](https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/)
+### [bitwise-and-of-numbers-range](https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/)
 
 > 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
 
-```go
-func rangeBitwiseAnd(m int, n int) int {
-    // m 5 1 0 1
-    //   6 1 1 0
-    // n 7 1 1 1
-    // 把可能包含0的全部右移变成
-    // m 5 1 0 0
-    //   6 1 0 0
-    // n 7 1 0 0
-    // 所以最后结果就是m<<count
-    var count int
-    for m!=n{
-        m>>=1
-        n>>=1
-        count++
-    }
-    return m<<count
-}
+思路：直接从 m 到 n 遍历一遍显然不是最优。一个性质，如果 m 不等于 n，则结果第一位一定是 0 （中间必定包含一个偶数）。利用这个性质，类似的将 m 和 n 右移后我们也可以判断第三位、第四位等等，免去了遍历的时间复杂度。
+
+```Python
+class Solution:
+    def rangeBitwiseAnd(self, m: int, n: int) -> int:
+
+        shift = 0
+        while m < n:
+            shift += 1
+            m >>= 1
+            n >>= 1
+
+        return m << shift
 ```
 
 ## 练习

diff --git a/data_structure/binary_tree.md b/data_structure/binary_tree.md
diff --git a/data_structure/heap.md b/data_structure/heap.md
@@ -0,0 +1,325 @@
+# 优先级队列 (堆)
+
+用到优先级队列 (priority queue) 或堆 (heap) 的题一般需要维护一个动态更新的池，元素会被频繁加入到池中或从池中被取走，每次取走的元素为池中优先级最高的元素 (可以简单理解为最大或者最小)。用堆来实现优先级队列是效率非常高的方法，加入或取出都只需要 O(log N) 的复杂度。
+
+## Kth largest/smallest
+
+找数据中第 K 个最大/最小数据是堆的一个典型应用。以找最大为例，遍历数据时，使用一个最小堆来维护当前最大的 K 个数据，堆顶数据为这 K 个数据中最小，即是你想要的第 k 个最大数据。每检查一个新数据，判断是否大于堆顶，若大于，说明堆顶数据小于了 K 个值，不是我们想找的第 K 个最大，则将新数据 push 进堆并 pop 掉堆顶，若小于则不操作，这样当遍历完全部数据后堆顶即为想要的结果。找最小时换成最大堆即可。
+
+### [kth-largest-element-in-a-stream](https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/)
+
+> 设计一个找到数据流中第K大元素的类。
+
+```Python
+class KthLargest:
+
+    def __init__(self, k: int, nums: List[int]):
+        self.K = k
+        self.min_heap = []
+        for num in nums:
+            if len(self.min_heap) < self.K:
+                heapq.heappush(self.min_heap, num)
+            elif num > self.min_heap[0]:
+                heapq.heappushpop(self.min_heap, num)
+
+    def add(self, val: int) -> int:
+        if len(self.min_heap) < self.K:
+            heapq.heappush(self.min_heap, val)
+        elif val > self.min_heap[0]:
+            heapq.heappushpop(self.min_heap, val)
+
+        return self.min_heap[0]
+```
+
+### [kth-smallest-element-in-a-sorted-matrix](https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/)
+
+> 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
+
+- 此题使用 heap 来做并不是最优做法，相当于 N 个 sorted list 里找第 k 个最小，列有序的条件没有充分利用，但是却是比较容易想且比较通用的做法。
+
+```Python
+class Solution:
+    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
+
+        N = len(matrix)
+
+        min_heap = []
+        for i in range(min(k, N)): # 这里用了一点列有序的性质，第k个最小只可能在前k行中(k行以后的数至少大于了k个数)
+            min_heap.append((matrix[i][0], i, 0))
+
+        heapq.heapify(min_heap)
+
+        while k > 0:
+            num, r, c = heapq.heappop(min_heap)
+
+            if c < N - 1:
+                heapq.heappush(min_heap, (matrix[r][c + 1], r, c + 1))
+
+            k -= 1
+
+        return num
+```
+
+### [find-k-pairs-with-smallest-sums](https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/)
+
+```Python
+class Solution:
+    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
+
+        m, n = len(nums1), len(nums2)
+        result = []
+
+        if m * n == 0:
+            return result
+
+        min_heap = [(nums1[0] + nums2[0], 0, 0)]
+        seen = set()
+
+        while min_heap and len(result) < k:
+            _, i1, i2 = heapq.heappop(min_heap)
+            result.append([nums1[i1], nums2[i2]])
+            if i1 < m - 1 and (i1 + 1, i2) not in seen:
+                heapq.heappush(min_heap, (nums1[i1 + 1] + nums2[i2], i1 + 1, i2))
+                seen.add((i1 + 1, i2))
+            if i2 < n - 1 and (i1, i2 + 1) not in seen:
+                heapq.heappush(min_heap, (nums1[i1] + nums2[i2 + 1], i1, i2 + 1))
+                seen.add((i1, i2 + 1))
+
+        return result
+```
+
+## Greedy + Heap
+
+Heap 可以高效地取出或更新当前池中优先级最高的元素，因此适用于一些需要 greedy 算法的场景。
+
+### [maximum-performance-of-a-team](https://leetcode-cn.com/problems/maximum-performance-of-a-team/)
+
+> 公司有 n 个工程师，给两个数组 speed 和 efficiency，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的团队的最大表现值。表现值的定义为：一个团队中所有工程师速度的和乘以他们效率值中的最小值。
+>
+
+- [See my review here.](https://leetcode.com/problems/maximum-performance-of-a-team/discuss/741822/Met-this-problem-in-my-interview!!!-(Python3-greedy-with-heap)) [或者这里(中文)](https://leetcode-cn.com/problems/maximum-performance-of-a-team/solution/greedy-with-min-heap-lai-zi-zhen-shi-mian-shi-de-j/)
+
+```Python
+# similar question: LC 857
+class Solution:
+    def maxPerformance(self, n, speed, efficiency, k):
+
+        people = sorted(zip(speed, efficiency), key=lambda x: -x[1])
+
+        result, sum_speed = 0, 0
+        min_heap = []
+
+        for i, (s, e) in enumerate(people):
+            if i < k:
+                sum_speed += s
+                heapq.heappush(min_heap, s)
+            elif s > min_heap[0]:
+                sum_speed += s - heapq.heappushpop(min_heap, s)
+
+            result = max(result, sum_speed * e)
+
+        return result #% 1000000007
+```
+
+### [ipo](https://leetcode-cn.com/problems/ipo/)
+
+- 贪心策略为每次做当前成本范围内利润最大的项目。
+
+```Python
+class Solution:
+    def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:
+        N = len(Profits)
+        projects = sorted([(-Profits[i], Capital[i]) for i in range(N)], key=lambda x: x[1])
+
+        projects.append((0, float('inf')))
+
+        max_profit_heap = []
+
+        for i in range(N + 1):
+            while projects[i][1] > W and len(max_profit_heap) > 0 and k > 0:
+                W -= heapq.heappop(max_profit_heap)
+                k -= 1
+
+            if projects[i][1] > W or k == 0:
+                break
+
+            heapq.heappush(max_profit_heap, projects[i][0])
+
+        return W
+```
+
+### [meeting-rooms-ii](https://leetcode-cn.com/problems/meeting-rooms-ii/)
+
+- 此题用 greedy + heap 解并不是很 intuitive，存在复杂度相同但更简单直观的做法。
+
+```Python
+class Solution:
+    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
+
+        if len(intervals) == 0: return 0
+
+        intervals.sort(key=lambda item: item[0])
+        end_times = [intervals[0][1]]
+
+        for interval in intervals[1:]:
+            if end_times[0] <= interval[0]:
+                heapq.heappop(end_times)
+
+            heapq.heappush(end_times, interval[1])
+
+        return len(end_times)
+```
+
+### [reorganize-string](https://leetcode-cn.com/problems/reorganize-string/)
+
+> 给定一个字符串 S，检查是否能重新排布其中的字母，使得任意两相邻的字符不同。若可行，输出任意可行的结果。若不可行，返回空字符串。
+
+- 贪心策略为每次取前两个最多数量的字母加入到结果。
+
+```Python
+class Solution:
+    def reorganizeString(self, S: str) -> str:
+
+        max_dup = (len(S) + 1) // 2
+        counts = collections.Counter(S)
+
+        heap = []
+        for c, f in counts.items():
+            if f > max_dup:
+                return ''
+            heap.append([-f, c])
+        heapq.heapify(heap)
+
+        result = []
+        while len(heap) > 1:
+            first = heapq.heappop(heap)
+            result.append(first[1])
+            first[0] += 1
+            second = heapq.heappop(heap)
+            result.append(second[1])
+            second[0] += 1
+
+            if first[0] < 0:
+                heapq.heappush(heap, first)
+            if second[0] < 0:
+                heapq.heappush(heap, second)
+
+        if len(heap) == 1:
+            result.append(heap[0][1])
+
+        return ''.join(result)
+```
+
+### Prim's Algorithm
+
+实现上是 greedy + heap 的一个应用，用于构造图的最小生成树 (MST)。
+
+### [minimum-risk-path](https://www.lintcode.com/problem/minimum-risk-path/description)
+
+> 地图上有 m 条无向边，每条边 (x, y, w) 表示位置 m 到位置 y 的权值为 w。从位置 0 到 位置 n 可能有多条路径。我们定义一条路径的危险值为这条路径中所有的边的最大权值。请问从位置 0 到 位置 n 所有路径中最小的危险值为多少？
+
+- 最小危险值为最小生成树中 0 到 n 路径上的最大边权。
+
+```Python
+class Solution:
+    def getMinRiskValue(self, N, M, X, Y, W):
+
+        # construct graph
+        adj = collections.defaultdict(list)
+        for i in range(M):
+            adj[X[i]].append((Y[i], W[i]))
+            adj[Y[i]].append((X[i], W[i]))
+
+        # Prim's algorithm with min heap
+        MST = collections.defaultdict(list)
+        min_heap = [(w, 0, v) for v, w in adj[0]]
+        heapq.heapify(min_heap)
+
+        while N not in MST:
+            w, p, v = heapq.heappop(min_heap)
+            if v not in MST:
+                MST[p].append((v, w))
+                MST[v].append((p, w))
+                for n, w in adj[v]:
+                    if n not in MST:
+                        heapq.heappush(min_heap, (w, v, n))
+
+        # dfs to search route from 0 to n
+        dfs = [(0, None, float('-inf'))]
+        while dfs:
+            v, p, max_w = dfs.pop()
+            for n, w in MST[v]:
+                cur_max_w = max(max_w, w)
+                if n == N:
+                    return cur_max_w
+                if n != p:
+                    dfs.append((n, v, cur_max_w))
+```
+
+### Dijkstra's Algorithm
+
+实现上是 greedy + heap 的一个应用，用于求解图的单源最短路径相关的问题，生成的树为最短路径树 (SPT)。
+
+### [network-delay-time](https://leetcode-cn.com/problems/network-delay-time/)
+
+- 标准的单源最短路径问题，使用朴素的的 Dijikstra 算法即可，可以当成模板使用。
+
+```Python
+class Solution:
+    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, t in times:
+            graph_neighbor[s].append((e, t))
+
+        # Dijkstra
+        SPT = {}
+        min_heap = [(0, K)]
+
+        while min_heap:
+            delay, node = heapq.heappop(min_heap)
+            if node not in SPT:
+                SPT[node] = delay
+                for n, d in graph_neighbor[node]:
+                    if n not in SPT:
+                        heapq.heappush(min_heap, (d + delay, n))
+
+        return max(SPT.values()) if len(SPT) == N else -1
+```
+
+### [cheapest-flights-within-k-stops](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/)
+
+- 在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。
+
+```Python
+class Solution:
+    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
+
+        # construct graph
+        graph_neighbor = collections.defaultdict(list)
+        for s, e, p in flights:
+            graph_neighbor[s].append((e, p))
+
+        # modified Dijkstra
+        prices, steps = {}, {}
+        min_heap = [(0, 0, src)]
+
+        while len(min_heap) > 0:
+            price, step, node = heapq.heappop(min_heap)
+
+            if node == dst: # early return
+                return price
+
+            if node not in prices:
+                prices[node] = price
+
+            steps[node] = step
+            if step <= K:
+                step += 1
+                for n, p in graph_neighbor[node]:
+                    if n not in prices or step < steps[n]:
+                        heapq.heappush(min_heap, (p + price, step, n))
+
+        return -1
+```