本文的目的是收集一些典型的题目，记住其写法，理解其思想，即可做到一通百通。欢迎大家提出宝贵意见！

Python 语言

二分查找

最明显的题目就是34. Find First and Last Position of Element in Sorted Array

模板：

区间定义：[l, r) 左闭右开

其中f(m)函数代表找到了满足条件的情况，有这个条件的判断就返回对应的位置，如果没有这个条件的判断就是lowwer_bound和higher_bound.

  1. def binary_search(l, r):
  2.     while l < r:
  3.         m = l + (r - l) // 2
  4.         if f(m):    # 判断找了没有，optional
  5.             return m
  6.         if g(m):
  7.             r = m   # new range [l, m)
  8.         else:
  9.             l = m + 1 # new range [m+1, r)
  10.     return l    # or not found

lower bound: find index of i, such that A[i] >= x

  1. def lowwer_bound(self, nums, target):
  2.     # find in range [left, right)
  3.     left, right = 0, len(nums)
  4.     while left < right:
  5.         mid = left + (right - left) // 2
  6.         if nums[mid] < target:
  7.             left = mid + 1
  8.         else:
  9.             right = mid
  10.     return left

upper bound: find index of i, such that A[i] > x

  1. def higher_bound(self, nums, target):
  2.     # find in range [left, right)
  3.     left, right = 0, len(nums)
  4.     while left < right:
  5.         mid = left + (right - left) // 2
  6.         if nums[mid] <= target:
  7.             left = mid + 1
  8.         else:
  9.             right = mid
  10.     return left

比如，题目69. Sqrt(x)。

  1. class Solution(object):
  2.     def mySqrt(self, x):
  3.         """
  4.         :type x: int
  5.         :rtype: int
  6.         """
  7.         left, right = 0, x + 1
  8.         # [left, right)
  9.         while left < right:
  10.             mid = left + (right - left) // 2
  11.             if mid ** 2 == x:
  12.                 return mid
  13.             if mid ** 2 < x:
  14.                 left = mid + 1
  15.             else:
  16.                 right = mid
  17.         return left - 1

排序的写法

C++的排序方法，使用sort并且重写comparator，如果需要使用外部变量，需要在中括号中放入&。

题目451. Sort Characters By Frequency。

  1. class Solution {
  2. public:
  3.     string frequencySort(string s) {
  4.         unordered_map<char, int> m;
  5.         for (char c : s) ++m[c];
  6.         sort(s.begin(), s.end(), [&](char& a, char& b){
  7.             return m[a] > m[b] || (m[a] == m[b] && a < b);
  8.         });
  9.         return s;
  10.     }
  11. };

BFS的写法

下面的这个写法是在一个邻接矩阵中找出离某一个点距离是k的点。

来自文章：【LeetCode】863. All Nodes Distance K in Binary Tree 解题报告（Python）

  1. # BFS
  2. bfs = [target.val]
  3. visited = set([target.val])
  4. for k in range(K):
  5.     bfs = [y for x in bfs for y in conn[x] if y not in visited]
  6.     visited |= set(bfs)
  7. return bfs
  1. Word Ladder

在BFS中保存已走过的步，并把已经走的合法路径删除掉。

  1. class Solution(object):
  2.     def ladderLength(self, beginWord, endWord, wordList):
  3.         """
  4.         :type beginWord: str
  5.         :type endWord: str
  6.         :type wordList: List[str]
  7.         :rtype: int
  8.         """
  9.         wordset = set(wordList)
  10.         bfs = collections.deque()
  11.         bfs.append((beginWord, 1))
  12.         while bfs:
  13.             word, length = bfs.popleft()
  14.             if word == endWord:
  15.                 return length
  16.             for i in range(len(word)):
  17.                 for c in "abcdefghijklmnopqrstuvwxyz":
  18.                     newWord = word[:i] + c + word[i + 1:]
  19.                     if newWord in wordset and newWord != word:
  20.                         wordset.remove(newWord)
  21.                         bfs.append((newWord, length + 1))
  22.         return 0

778. Swim in Rising Water

使用优先级队列来优先走比较矮的路，最后保存最高的那个格子的高度。

  1. class Solution(object):
  2.     def swimInWater(self, grid):
  3.         """
  4.         :type grid: List[List[int]]
  5.         :rtype: int
  6.         """
  7.         n = len(grid)
  8.         visited, pq = set((0, 0)), [(grid[0][0], 0, 0)]
  9.         res = 0
  10.         while pq:
  11.             T, i, j = heapq.heappop(pq)
  12.             res = max(res, T)
  13.             directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
  14.             if i == j == n - 1:
  15.                 break
  16.             for dir in directions:
  17.                 x, y = i + dir[0], j + dir[1]
  18.                 if x < 0 or x >= n or y < 0 or y >= n or (x, y) in visited:
  19.                     continue
  20.                 heapq.heappush(pq, (grid[x][y], x, y))
  21.                 visited.add((x, y))
  22.         return res

847. Shortest Path Visiting All Nodes

需要找出某顶点到其他顶点的最短路径。出发顶点不是确定的，每个顶点有可能访问多次。使用N位bit代表访问过的顶点的状态。如果到达了最终状态，那么现在步数就是所求。这个题把所有的节点都放入了起始队列中，相当于每次都是所有的顶点向前走一步。

  1. class Solution(object):
  2.     def shortestPathLength(self, graph):
  3.         """
  4.         :type graph: List[List[int]]
  5.         :rtype: int
  6.         """
  7.         N = len(graph)
  8.         que = collections.deque()
  9.         step = 0
  10.         goal = (1 << N) - 1
  11.         visited = [[0 for j in range(1 << N)] for i in range(N)]
  12.         for i in range(N):
  13.             que.append((i, 1 << i))
  14.         while que:
  15.             s = len(que)
  16.             for i in range(s):
  17.                 node, state = que.popleft()
  18.                 if state == goal:
  19.                     return step
  20.                 if visited[node][state]:
  21.                     continue
  22.                 visited[node][state] = 1
  23.                 for nextNode in graph[node]:
  24.                     que.append((nextNode, state | (1 << nextNode)))
  25.             step += 1
  26.         return step

429. N-ary Tree Level Order Traversal多叉树的层次遍历，这个BFS写法我觉得很经典。适合记忆。

  1. """
  2. # Definition for a Node.
  3. class Node(object):
  4.     def __init__(self, val, children):
  5.         self.val = val
  6.         self.children = children
  7. """
  8. class Solution(object):
  9.     def levelOrder(self, root):
  10.         """
  11.         :type root: Node
  12.         :rtype: List[List[int]]
  13.         """
  14.         res = []
  15.         que = collections.deque()
  16.         que.append(root)
  17.         while que:
  18.             level = []
  19.             size = len(que)
  20.             for _ in range(size):
  21.                 node = que.popleft()
  22.                 if not node:
  23.                     continue
  24.                 level.append(node.val)
  25.                 for child in node.children:
  26.                     que.append(child)
  27.             if level:
  28.                 res.append(level)
  29.         return res

DFS的写法

329. Longest Increasing Path in a Matrix

417. Pacific Atlantic Water Flow

778. Swim in Rising Water

二分查找+DFS

  1. class Solution(object):
  2.     def swimInWater(self, grid):
  3.         """
  4.         :type grid: List[List[int]]
  5.         :rtype: int
  6.         """
  7.         n = len(grid)
  8.         left, right = 0, n * n - 1
  9.         while left <= right:
  10.             mid = left + (right - left) / 2
  11.             if self.dfs([[False] * n for _ in range(n)], grid, mid, n, 0, 0):
  12.                 right = mid - 1
  13.             else:
  14.                 left = mid + 1
  15.         return left
  17.     def dfs(self, visited, grid, mid, n, i, j):
  18.         visited[i][j] = True
  19.         if i == n - 1 and j == n - 1:
  20.             return True
  21.         directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
  22.         for dir in directions:
  23.             x, y = i + dir[0], j + dir[1]
  24.             if x < 0 or x >= n or y < 0 or y >= n or visited[x][y] or max(mid, grid[i][j]) != max(mid, grid[x][y]):
  25.                 continue
  26.             if self.dfs(visited, grid, mid, n, x, y):
  27.                 return True
  28.         return False

回溯法

下面这个题使用了回溯法，但是写的不够简单干练，遇到更好的解法的时候，要把这个题进行更新。

这个回溯思想，先去添加一个新的状态，看在这个状态的基础上，能不能找结果，如果找不到结果的话，那么就回退，即把这个结果和访问的记录给去掉。这个题使用了return True的方法让我们知道已经找出了结果，所以不用再递归了。

753. Cracking the Safe

  1. class Solution(object):
  2.     def crackSafe(self, n, k):
  3.         """
  4.         :type n: int
  5.         :type k: int
  6.         :rtype: str
  7.         """
  8.         res = ["0"] * n
  9.         size = k ** n
  10.         visited = set()
  11.         visited.add("".join(res))
  12.         if self.dfs(res, visited, size, n, k):
  13.             return "".join(res)
  14.         return ""
  16.     def dfs(self, res, visited, size, n, k):
  17.         if len(visited) == size:
  18.             return True
  19.         node = "".join(res[len(res) - n + 1:])
  20.         for i in range(k):
  21.             node = node + str(i)
  22.             if node not in visited:
  23.                 res.append(str(i))
  24.                 visited.add(node)
  25.                 if self.dfs(res, visited, size, n, k):
  26.                     return True
  27.                 res.pop()
  28.                 visited.remove(node)
  29.             node = node[:-1]

312. Burst Balloons

  1. class Solution(object):
  2.     def maxCoins(self, nums):
  3.         """
  4.         :type nums: List[int]
  5.         :rtype: int
  6.         """
  7.         n = len(nums)
  8.         nums.insert(0, 1)
  9.         nums.append(1)
  10.         c = [[0] * (n + 2) for _ in range(n + 2)]
  11.         return self.dfs(nums, c, 1, n)
  13.     def dfs(self, nums, c, i, j):
  14.         if i > j: return 0
  15.         if c[i][j] > 0: return c[i][j]
  16.         if i == j: return nums[i - 1] * nums[i] * nums[i + 1]
  17.         res = 0
  18.         for k in range(i, j + 1):
  19.             res = max(res, self.dfs(nums, c, i, k - 1) + nums[i - 1] * nums[k] * nums[j + 1] + self.dfs(nums, c, k + 1, j))
  20.         c[i][j] = res
  21.         return c[i][j]
  23. class Solution {
  24. public:
  25.     int countArrangement(int N) {
  26.         int res = 0;
  27.         vector<int> visited(N + 1, 0);
  28.         helper(N, visited, 1, res);
  29.         return res;
  30.     }
  31. private:
  32.     void helper(int N, vector<int>& visited, int pos, int& res) {
  33.         if (pos > N) {
  34.             res++;
  35.             return;
  36.         }
  37.         for (int i = 1; i <= N; i++) {
  38.             if (visited[i] == 0 && (i % pos == 0 || pos % i == 0)) {
  39.                 visited[i] = 1;
  40.                 helper(N, visited, pos + 1, res);
  41.                 visited[i] = 0;
  42.             }
  43.         }
  44.     }
  45. };

如果需要保存路径的回溯法：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> permute(vector<int>& nums) {
  4.         const int N = nums.size();
  5.         vector<vector<int>> res;
  6.         vector<int> path;
  7.         vector<int> visited(N, 0);
  8.         dfs(nums, 0, visited, res, path);
  9.         return res;
  10.     }
  11. private:
  12.     void dfs(vector<int>& nums, int pos, vector<int>& visited, vector<vector<int>>& res, vector<int>& path) {
  13.         const int N = nums.size();
  14.         if (pos == N) {
  15.             res.push_back(path);
  16.             return;
  17.         }
  18.         for (int i = 0; i < N; i++) {
  19.             if (!visited[i]) {
  20.                 visited[i] = 1;
  21.                 path.push_back(nums[i]);
  22.                 dfs(nums, pos + 1, visited, res, path);
  23.                 path.pop_back();
  24.                 visited[i] = 0;
  25.             }
  26.         }
  27.     }
  28. };

树

递归

617. Merge Two Binary Trees把两个树重叠，重叠部分求和，不重叠部分是两个树不空的节点。

  1. class Solution:
  2.     def mergeTrees(self, t1, t2):
  3.         if not t2:
  4.             return t1
  5.         if not t1:
  6.             return t2
  7.         newT = TreeNode(t1.val + t2.val)
  8.         newT.left = self.mergeTrees(t1.left, t2.left)
  9.         newT.right = self.mergeTrees(t1.right, t2.right)
  10.         return newT

迭代

226. Invert Binary Tree

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def invertTree(self, root):
  10.         """
  11.         :type root: TreeNode
  12.         :rtype: TreeNode
  13.         """
  14.         stack = []
  15.         stack.append(root)
  16.         while stack:
  17.             node = stack.pop()
  18.             if not node:
  19.                 continue
  20.             node.left, node.right = node.right, node.left
  21.             stack.append(node.left)
  22.             stack.append(node.right)
  23.         return root

前序遍历

144. Binary Tree Preorder Traversal

迭代写法：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def preorderTraversal(self, root):
  10.         """
  11.         :type root: TreeNode
  12.         :rtype: List[int]
  13.         """
  14.         if not root: return []
  15.         res = []
  16.         stack = []
  17.         stack.append(root)
  18.         while stack:
  19.             node = stack.pop()
  20.             if not node:
  21.                 continue
  22.             res.append(node.val)
  23.             stack.append(node.right)
  24.             stack.append(node.left)
  25.         return res

中序遍历

94. Binary Tree Inorder Traversal

迭代写法：

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Solution(object):
  9.     def inorderTraversal(self, root):
  10.         """
  11.         :type root: TreeNode
  12.         :rtype: List[int]
  13.         """
  14.         stack = []
  15.         answer = []
  16.         while True:
  17.             while root:
  18.                 stack.append(root)
  19.                 root = root.left
  20.             if not stack:
  21.                 return answer
  22.             root = stack.pop()
  23.             answer.append(root.val)
  24.             root = root.right

后序遍历

145. Binary Tree Postorder Traversal

迭代写法如下：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     vector<int> postorderTraversal(TreeNode* root) {
  13.         vector<int> res;
  14.         if (!root) return res;
  15.         stack<TreeNode*> st;
  16.         st.push(root);
  17.         while (!st.empty()) {
  18.             TreeNode* node = st.top(); st.pop();
  19.             if (!node) continue;
  20.             res.push_back(node->val);
  21.             st.push(node->left);
  22.             st.push(node->right);
  23.         }
  24.         reverse(res.begin(), res.end());
  25.         return res;
  26.     }
  27. };

构建完全二叉树

完全二叉树是每一层都满的，因此找出要插入节点的父亲节点是很简单的。如果用数组tree保存着所有节点的层次遍历，那么新节点的父亲节点就是tree[(N -1)/2]，N是未插入该节点前的树的元素个数。
构建树的时候使用层次遍历，也就是BFS把所有的节点放入到tree里。插入的时候直接计算出新节点的父亲节点。获取root就是数组中的第0个节点。

919. Complete Binary Tree Inserter

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class CBTInserter(object):
  10.     def __init__(self, root):
  11.         """
  12.         :type root: TreeNode
  13.         """
  14.         self.tree = list()
  15.         queue = collections.deque()
  16.         queue.append(root)
  17.         while queue:
  18.             node = queue.popleft()
  19.             self.tree.append(node)
  20.             if node.left:
  21.                 queue.append(node.left)
  22.             if node.right:
  23.                 queue.append(node.right)
  25.     def insert(self, v):
  26.         """
  27.         :type v: int
  28.         :rtype: int
  29.         """
  30.         _len = len(self.tree)
  31.         father = self.tree[(_len - 1) / 2]
  32.         node = TreeNode(v)
  33.         if not father.left:
  34.             father.left = node
  35.         else:
  36.             father.right = node
  37.         self.tree.append(node)
  38.         return father.val
  41.     def get_root(self):
  42.         """
  43.         :rtype: TreeNode
  44.         """
  45.         return self.tree[0]
  48. # Your CBTInserter object will be instantiated and called as such:
  49. # obj = CBTInserter(root)
  50. # param_1 = obj.insert(v)
  51. # param_2 = obj.get_root()

并查集

不包含rank的话，代码很简短，应该背会。

  1. Accounts Merge
    https://leetcode.com/articles/accounts-merge/
  1. class DSU:
  2.     def __init__(self):
  3.         self.par = range(10001)
  5.     def find(self, x):
  6.         if x != self.par[x]:
  7.             self.par[x] = self.find(self.par[x])
  8.         return self.par[x]
  10.     def union(self, x, y):
  11.         self.par[self.find(x)] = self.find(y)
  13.     def same(self, x, y):
  14.         return self.find(x) == self.find(y)

C++版本如下：

  1. vector<int> map_; //i的parent，默认是i
  2. int f(int a) {
  3.     if (map_[a] == a)
  4.         return a;
  5.     return f(map_[a]);
  6. }
  7. void u(int a, int b) {
  8.     int pa = f(a);
  9.     int pb = f(b);
  10.     if (pa == pb)
  11.         return;
  12.     map_[pa] = pb;
  13. }

包含rank的，这里的rank表示树的高度：

684. Redundant Connection

  1. class DSU(object):
  2.     def __init__(self):
  3.         self.par = range(1001)
  4.         self.rnk = [0] * 1001
  6.     def find(self, x):
  7.         if self.par[x] != x:
  8.             self.par[x] = self.find(self.par[x])
  9.         return self.par[x]
  11.     def union(self, x, y):
  12.         xr, yr = self.find(x), self.find(y)
  13.         if xr == yr:
  14.             return False
  15.         elif self.rnk[xr] < self.rnk[yr]:
  16.             self.par[xr] = yr
  17.         elif self.rnk[xr] > self.rnk[yr]:
  18.             self.par[yr] = xr
  19.         else:
  20.             self.par[yr] = xr
  21.             self.rnk[xr] += 1
  22.         return True

另外一种rank方法是，保存树中节点的个数。

547. Friend Circles，代码如下：

  1. class Solution(object):
  2.     def findCircleNum(self, M):
  3.         """
  4.         :type M: List[List[int]]
  5.         :rtype: int
  6.         """
  7.         dsu = DSU()
  8.         N = len(M)
  9.         for i in range(N):
  10.             for j in range(i, N):
  11.                 if M[i][j]:
  12.                     dsu.u(i, j)
  13.         res = 0
  14.         for i in range(N):
  15.             if dsu.f(i) == i:
  16.                 res += 1
  17.         return res
  19. class DSU(object):
  20.     def __init__(self):
  21.         self.d = range(201)
  22.         self.r = [0] * 201
  24.     def f(self, a):
  25.         return a if a == self.d[a] else self.f(self.d[a])
  27.     def u(self, a, b):
  28.         pa = self.f(a)
  29.         pb = self.f(b)
  30.         if (pa == pb):
  31.             return
  32.         if self.r[pa] < self.r[pb]:
  33.             self.d[pa] = pb
  34.             self.r[pb] += self.r[pa]
  35.         else:
  36.             self.d[pb] = pa
  37.             self.r[pa] += self.r[pb]

前缀树

前缀树的题目可以使用字典解决，代码还是需要背一下的，C++版本的前缀树如下：

208. Implement Trie (Prefix Tree)这个题是纯考Trie的。参考代码如下：

  1. class TrieNode {
  2. public:
  3.     vector<TrieNode*> child;
  4.     bool isWord;
  5.     TrieNode() : isWord(false), child(26, nullptr) {
  6.     }
  7.     ~TrieNode() {
  8.         for (auto& c : child)
  9.             delete c;
  10.     }
  11. };
  13. class Trie {
  14. public:
  15.     /** Initialize your data structure here. */
  16.     Trie() {
  17.         root = new TrieNode();
  18.     }
  20.     /** Inserts a word into the trie. */
  21.     void insert(string word) {
  22.         TrieNode* p = root;
  23.         for (char a : word) {
  24.             int i = a - 'a';
  25.             if (!p->child[i])
  26.                 p->child[i] = new TrieNode();
  27.             p = p->child[i];
  28.         }
  29.         p->isWord = true;
  30.     }
  32.     /** Returns if the word is in the trie. */
  33.     bool search(string word) {
  34.         TrieNode* p = root;
  35.         for (char a : word) {
  36.             int i = a - 'a';
  37.             if (!p->child[i])
  38.                 return false;
  39.             p = p->child[i];
  40.         }
  41.         return p->isWord;
  42.     }
  44.     /** Returns if there is any word in the trie that starts with the given prefix. */
  45.     bool startsWith(string prefix) {
  46.         TrieNode* p = root;
  47.         for (char a : prefix) {
  48.             int i = a - 'a';
  49.             if (!p->child[i])
  50.                 return false;
  51.             p = p->child[i];
  52.         }
  53.         return true;
  54.     }
  55. private:
  56.     TrieNode* root;
  57. };
  59. /**
  60.  * Your Trie object will be instantiated and called as such:
  61.  * Trie obj = new Trie();
  62.  * obj.insert(word);
  63.  * bool param_2 = obj.search(word);
  64.  * bool param_3 = obj.startsWith(prefix);
  65.  */

677. Map Sum Pairs

  1. class MapSum {
  2. public:
  3.     /** Initialize your data structure here. */
  4.     MapSum() {}
  6.     void insert(string key, int val) {
  7.         int inc = val - vals_[key];
  8.         Trie* p = &root;
  9.         for (const char c : key) {
  10.             if (!p->children[c])
  11.                 p->children[c] = new Trie();
  12.             p->children[c]->sum += inc;
  13.             p = p->children[c];
  14.         }
  15.         vals_[key] = val;
  16.     }
  18.     int sum(string prefix) {
  19.         Trie* p = &root;
  20.         for (const char c : prefix) {
  21.             if (!p->children[c])
  22.                 return 0;
  23.             p = p->children[c];
  24.         }
  25.         return p->sum;
  26.     }
  27. private:
  28.     struct Trie {
  29.         Trie():children(128, nullptr), sum(0){}
  30.         ~Trie(){
  31.             for (auto child : children)
  32.                 if (child) delete child;
  33.             children.clear();
  34.         }
  35.         vector<Trie*> children;
  36.         int sum;
  37.     };
  39.     Trie root;
  40.     unordered_map<string, int> vals_;
  41. };

图遍历

743. Network Delay Time这个题很详细。

Dijkstra算法

时间复杂度是O(N ^ 2 + E)，空间复杂度是O(N+E).

  1. class Solution:
  2.     def networkDelayTime(self, times, N, K):
  3.         """
  4.         :type times: List[List[int]]
  5.         :type N: int
  6.         :type K: int
  7.         :rtype: int
  8.         """
  9.         K -= 1
  10.         nodes = collections.defaultdict(list)
  11.         for u, v, w in times:
  12.             nodes[u - 1].append((v - 1, w))
  13.         dist = [float('inf')] * N
  14.         dist[K] = 0
  15.         done = set()
  16.         for _ in range(N):
  17.             smallest = min((d, i) for (i, d) in enumerate(dist) if i not in done)[1]
  18.             for v, w in nodes[smallest]:
  19.                 if v not in done and dist[smallest] + w < dist[v]:
  20.                     dist[v] = dist[smallest] + w
  21.             done.add(smallest)
  22.         return -1 if float('inf') in dist else max(dist)

Floyd-Warshall算法

时间复杂度O(n^3)， 空间复杂度O(n^2)。

  1. class Solution:
  2.     def networkDelayTime(self, times, N, K):
  3.         """
  4.         :type times: List[List[int]]
  5.         :type N: int
  6.         :type K: int
  7.         :rtype: int
  8.         """
  9.         d = [[float('inf')] * N for _ in range(N)]
  10.         for time in times:
  11.             u, v, w = time[0] - 1, time[1] - 1, time[2]
  12.             d[u][v] = w
  13.         for i in range(N):
  14.             d[i][i] = 0
  15.         for k in range(N):
  16.             for i in range(N):
  17.                 for j in range(N):
  18.                     d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  19.         return -1 if float('inf') in d[K - 1] else max(d[K - 1])

Bellman-Ford算法

时间复杂度O(ne)， 空间复杂度O(n)

  1. class Solution:
  2.     def networkDelayTime(self, times, N, K):
  3.         """
  4.         :type times: List[List[int]]
  5.         :type N: int
  6.         :type K: int
  7.         :rtype: int
  8.         """
  9.         dist = [float('inf')] * N
  10.         dist[K - 1] = 0
  11.         for i in range(N):
  12.             for time in times:
  13.                 u = time[0] - 1
  14.                 v = time[1] - 1
  15.                 w = time[2]
  16.                 dist[v] = min(dist[v], dist[u] + w)
  17.         return -1 if float('inf') in dist else max(dist)

最小生成树

1135. Connecting Cities With Minimum Cost

Kruskal算法

  1. class Solution {
  2. public:
  3.     static bool cmp(vector<int> & a,vector<int> & b){
  4.         return a[2] < b[2];
  5.     }
  7.     int find(vector<int> & f,int x){
  8.         while(x != f[x]){
  9.             x = f[x];
  10.         }
  11.         return x;
  12.     }
  14.     bool uni(vector<int> & f,int x,int y){
  15.         int x1 = find(f,x);
  16.         int y1 = find(f,y);
  17.         f[x1] = y1;
  19.         return true;
  20.     }
  22.     int minimumCost(int N, vector<vector<int>>& conections) {
  23.         int ans = 0;
  24.         int count = 0;
  25.         vector<int> father(N+1,0);
  27.         sort(conections.begin(),conections.end(),cmp);
  28.         for(int i = 0;i <= N; ++i){
  29.             father[i] = i;
  30.         }
  32.         for(auto conect : conections){
  33.             if(find(father,conect[0]) != find(father,conect[1])){
  34.                 count++;
  35.                 ans += conect[2];
  36.                 uni(father,conect[0],conect[1]);
  37.                 if(count == N-1){
  38.                     return ans;
  39.                 }
  40.             }
  41.         }
  43.         return -1;
  44.     }
  45. };

Prim算法

  1. struct cmp {
  2.     bool operator () (const vector<int> &a, const vector<int> &b) {
  3.         return a[2] > b[2];
  4.     }
  5. };
  7. class Solution {
  8. public:    
  9.     int minimumCost(int N, vector<vector<int>>& conections) {
  10.         int ans = 0;
  11.         int selected = 0;
  12.         vector<vector<pair<int,int>>> edgs(N+1,vector<pair<int,int>>());
  13.         priority_queue<vector<int>,vector<vector<int>>,cmp> pq;
  14.         vector<bool> visit(N+1,false);
  16.         /*initial*/
  17.         for(auto re : conections){
  18.             edgs[re[0]].push_back(make_pair(re[1],re[2]));
  19.             edgs[re[1]].push_back(make_pair(re[0],re[2]));
  20.         }
  22.         if(edgs[1].size() == 0){
  23.             return -1;
  24.         }
  26.         /*kruskal*/
  27.         selected = 1;
  28.         visit[1] = true;
  29.         for(int i = 0;i < edgs[1].size(); ++i){
  30.             pq.push(vector<int>({1,edgs[1][i].first,edgs[1][i].second}));
  31.         }
  33.         while(!pq.empty()){
  34.             vector<int> curr = pq.top();
  35.             pq.pop();
  37.             if(!visit[curr[1]]){
  38.                 visit[curr[1]] = true;
  39.                 ans += curr[2];
  40.                 for(auto e : edgs[curr[1]]){
  41.                     pq.push(vector<int>({curr[1],e.first,e.second}));
  42.                 }
  43.                 selected++;
  44.                 if(selected == N){
  45.                     return ans;
  46.                 }
  47.             }
  48.         }
  50.         return -1;
  51.     }
  52. };

拓扑排序

BFS方式：

  1. class Solution(object):
  2.     def canFinish(self, N, prerequisites):
  3.         """
  4.         :type N,: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: bool
  7.         """
  8.         graph = collections.defaultdict(list)
  9.         indegrees = collections.defaultdict(int)
  10.         for u, v in prerequisites:
  11.             graph[v].append(u)
  12.             indegrees[u] += 1
  13.         for i in range(N):
  14.             zeroDegree = False
  15.             for j in range(N):
  16.                 if indegrees[j] == 0:
  17.                     zeroDegree = True
  18.                     break
  19.             if not zeroDegree: return False
  20.             indegrees[j] = -1
  21.             for node in graph[j]:
  22.                 indegrees[node] -= 1
  23.         return True

DFS方式：

  1. class Solution(object):
  2.     def canFinish(self, N, prerequisites):
  3.         """
  4.         :type N,: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: bool
  7.         """
  8.         graph = collections.defaultdict(list)
  9.         for u, v in prerequisites:
  10.             graph[u].append(v)
  11.         # 0 = Unknown, 1 = visiting, 2 = visited
  12.         visited = [0] * N
  13.         for i in range(N):
  14.             if not self.dfs(graph, visited, i):
  15.                 return False
  16.         return True
  18.     # Can we add node i to visited successfully?
  19.     def dfs(self, graph, visited, i):
  20.         if visited[i] == 1: return False
  21.         if visited[i] == 2: return True
  22.         visited[i] = 1
  23.         for j in graph[i]:
  24.             if not self.dfs(graph, visited, j):
  25.                 return False
  26.         visited[i] = 2
  27.         return True

如果需要保存拓扑排序的路径：

BFS方式：

  1. class Solution(object):
  2.     def findOrder(self, numCourses, prerequisites):
  3.         """
  4.         :type numCourses: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: List[int]
  7.         """
  8.         graph = collections.defaultdict(list)
  9.         indegrees = collections.defaultdict(int)
  10.         for u, v in prerequisites:
  11.             graph[v].append(u)
  12.             indegrees[u] += 1
  13.         path = []
  14.         for i in range(numCourses):
  15.             zeroDegree = False
  16.             for j in range(numCourses):
  17.                 if indegrees[j] == 0:
  18.                     zeroDegree = True
  19.                     break
  20.             if not zeroDegree:
  21.                 return []
  22.             indegrees[j] -= 1
  23.             path.append(j)
  24.             for node in graph[j]:
  25.                 indegrees[node] -= 1
  26.         return path

DFS方式：

  1. class Solution(object):
  2.     def findOrder(self, numCourses, prerequisites):
  3.         """
  4.         :type numCourses: int
  5.         :type prerequisites: List[List[int]]
  6.         :rtype: List[int]
  7.         """
  8.         graph = collections.defaultdict(list)
  9.         for u, v in prerequisites:
  10.             graph[u].append(v)
  11.         # 0 = Unknown, 1 = visiting, 2 = visited
  12.         visited = [0] * numCourses
  13.         path = []
  14.         for i in range(numCourses):
  15.             if not self.dfs(graph, visited, i, path):
  16.                 return []
  17.         return path
  19.     def dfs(self, graph, visited, i, path):
  20.         if visited[i] == 1: return False
  21.         if visited[i] == 2: return True
  22.         visited[i] = 1
  23.         for j in graph[i]:
  24.             if not self.dfs(graph, visited, j, path):
  25.                 return False
  26.         visited[i] = 2
  27.         path.append(i)
  28.         return True

207. Course Schedule

210. Course Schedule II

310. Minimum Height Trees

双指针

这是一个模板‘ rel=)，里面的map如果是双指针范围内的字符串字频的话，增加和减少的方式如下。

  1. int findSubstring(string s){
  2.         vector<int> map(128,0);
  3.         int counter; // check whether the substring is valid
  4.         int begin=0, end=0; //two pointers, one point to tail and one  head
  5.         int d; //the length of substring
  7.         for() { /* initialize the hash map here */ }
  9.         while(end<s.size()){
  11.             if(map[s[end++]]++ ?){  /* modify counter here */ }
  13.             while(/* counter condition */){ 
  15.                  /* update d here if finding minimum*/
  17.                 //increase begin to make it invalid/valid again
  19.                 if(map[s[begin++]]-- ?){ /*modify counter here*/ }
  20.             }  
  22.             /* update d here if finding maximum*/
  23.         }
  24.         return d;
  25.   }

424. 替换后的最长重复字符

这个题的map是t的字频，所以使用map更方式和上是相反的。

  1. class Solution(object):
  2.     def characterReplacement(self, s, k):
  3.         N = len(s)
  4.         left, right = 0, 0 # [left, right] 都包含
  5.         counter = collections.Counter()
  6.         res = 0
  7.         while right < N:
  8.             counter[s[right]] += 1
  9.             maxCnt = counter.most_common(1)[0][1]
  10.             while right - left + 1 - maxCnt > k:
  11.                 counter[s[left]] -= 1
  12.                 left += 1
  13.             res = max(res, right - left + 1)
  14.             right += 1
  15.         return res

动态规划

状态搜索

688. Knight Probability in Chessboard

62. Unique Paths

63. Unique Paths II

913. Cat and Mouse

576. Out of Boundary Paths

  1. class Solution(object):
  2.     def findPaths(self, m, n, N, i, j):
  3.         """
  4.         :type m: int
  5.         :type n: int
  6.         :type N: int
  7.         :type i: int
  8.         :type j: int
  9.         :rtype: int
  10.         """
  11.         dp = [[0] * n for _ in range(m)]
  12.         for s in range(1, N + 1):
  13.             curStatus = [[0] * n for _ in range(m)]
  14.             for x in range(m):
  15.                 for y in range(n):
  16.                     v1 = 1 if x == 0 else dp[x - 1][y]
  17.                     v2 = 1 if x == m - 1 else dp[x + 1][y]
  18.                     v3 = 1 if y == 0 else dp[x][y - 1]
  19.                     v4 = 1 if y == n - 1 else dp[x][y + 1]
  20.                     curStatus[x][y] = (v1 + v2 + v3 + v4) % (10**9 + 7)
  21.             dp = curStatus
  22.         return dp[i][j]

贪心

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，他所作出的是在某种意义上的局部最优解。贪心算法和动态规划算法都是由局部最优导出全局最优，这里不得不比较下二者的区别

贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解

动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解

贪心是个思想，没有统一的模板。