# 算法学习之旅，终点亦是起点

## 数据结构

• 一维：

基础：数组 array (string), 链表 linked list

高级：栈 stack, 队列 queue, 双端队列 deque, 集合 set, 映射 map (hash or map), etc

• 二维：

基础：树 tree, 图 graph

高级：二叉搜索树 binary search tree (red-black tree, AVL), 堆 heap, 并查集 disjoint set, 字典树 Trie, etc

• 特殊：

位运算 Bitwise, 布隆过滤器 BloomFilter

LRU Cache

## 时间复杂度

www.bigocheatsheet.com/

## 算法

• If-else, switch —> branch

• for, while loop —> Iteration

• 递归 Recursion (Divide & Conquer, Backtrace)

• 搜索 Search: 深度优先搜索 Depth first search, 广度优先搜索 Breadth first search, A*, etc

• 动态规划 Dynamic Programming

• 二分查找 Binary Search

• 贪心 Greedy

• 数学 Math , 几何 Geometry

## 部分代码模板 （仅供参考）

### 递归

``````// java
public  void  recur(int level, int param) {

// terminator

if (level > MAX_LEVEL) {

// process result

return;

}

// process current logic

process(level, param);

// drill down

recur( level: level + 1, newParam);

// restore current status

}
``````

### 分治、回溯

``````// java
private  static  int  divide_conquer(Problem problem, ) {

if (problem == NULL) {

int  res = process_last_result();

return res;

}

subProblems = split_problem(problem)

res0 = divide_conquer(subProblems[0])

res1 = divide_conquer(subProblems[1])

result = process_result(res0, res1);

return result;

}
``````

### DFS

``````// java
public  List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> allResults = new  ArrayList<>();

if(root==null){

return allResults;

}

travel(root,0,allResults);

return allResults;

}

private  void  travel(TreeNode root,int level,List<List<Integer>> results){

if(results.size()==level){

}

if(root.left!=null){

travel(root.left,level+1,results);

}

if(root.right!=null){

travel(root.right,level+1,results);

}

}
``````

``````# Python
def  DFS(self, tree):

if tree.root is  None:

return []

visited, stack = [], [tree.root]

while stack:

node = stack.pop()

process (node)

nodes = generate_related_nodes(node)

stack.push(nodes)

# other processing work

...
``````

### BFS

``````# Python
def  BFS(graph, start, end):

visited = set()

queue = []

queue.append([start])

while queue:

node = queue.pop()

process(node)

nodes = generate_related_nodes(node)

queue.push(nodes)

# other processing work

...
``````

### 二分查找

``````// Java
public  int  binarySearch(int[] array, int target) {

int  left = 0, right = array.length - 1, mid;

while (left <= right) {

mid = (right - left) / 2 + left;

if (array[mid] == target) {

return mid;

} else  if (array[mid] > target) {

right = mid - 1;

} else {

left = mid + 1;

}

}

return -1;

}
``````

### 动态规划

• 动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构）

• 共性：找到重复子问题

• 差异性：最优子结构、中途可以淘汰次优解

DP顺推模板

``````# 伪代码
function DP():

dp = [][] # 二维情况

for i = 0 .. M {

for j = 0 .. N {

dp[i][j] = _Function(dp[i’][j’]...)

}

}

return dp[M][N];
``````

### Trie 树（字典树）

``````// java
class  Trie {

private  boolean  isEnd;

private  Trie[] next;

/** Initialize your data structure here. */

public  Trie() {

isEnd = false;

next = new  Trie[26];

}

/** Inserts a word into the trie. */

public  void  insert(String  word) {

if (word == null || word.length() == 0) return;

Trie  curr = this;

char[] words = word.toCharArray();

for (int  i = 0;i < words.length;i++) {

int  n = words[i] - 'a';

if (curr.next[n] == null) curr.next[n] = new  Trie();

curr = curr.next[n];

}

curr.isEnd = true;

}

/** Returns if the word is in the trie. */

public  boolean  search(String  word) {

Trie  node = searchPrefix(word);

return node != null && node.isEnd;

}

/** Returns if there is any word in the trie that starts with the given prefix. */

public  boolean  startsWith(String  prefix) {

Trie  node = searchPrefix(prefix);

return node != null;

}

private  Trie  searchPrefix(String  word) {

Trie  node = this;

char[] words = word.toCharArray();

for (int  i = 0;i < words.length;i++) {

node = node.next[words[i] - 'a'];

if (node == null) return  null;

}

return node;

}

}
``````

### 并查集

``````// java
class  UnionFind {

private  int  count = 0;

private  int[] parent;

public  UnionFind(int  n) {

count = n;

parent = new  int[n];

for (int  i = 0; i < n; i++) {

parent[i] = i;

}

}

public  int  find(int  p) {

while (p != parent[p]) {

parent[p] = parent[parent[p]];

p = parent[p];

}

return p;

}

public  void  union(int  p, int  q) {

int  rootP = find(p);

int  rootQ = find(q);

if (rootP == rootQ) return;

parent[rootP] = rootQ;

count--;

}

}
``````

### 布隆过滤器

``````// java
public  class  BloomFilter {

private  static  final  int  DEFAULT_SIZE = 2 << 24;

private  static  final  int[] seeds = new  int[] { 5, 7, 11, 13, 31, 37, 61 };

private  BitSet  bits = new  BitSet(DEFAULT_SIZE);

private  SimpleHash[] func = new  SimpleHash[seeds.length];

public  BloomFilter() {

for (int  i = 0; i < seeds.length; i++) {

func[i] = new  SimpleHash(DEFAULT_SIZE, seeds[i]);

}

}

for (SimpleHash  f  : func) {

bits.set(f.hash(value), true);

}

}

public  boolean  contains(String  value) {

if (value == null) {

return  false;

}

boolean  ret = true;

for (SimpleHash  f  : func) {

ret = ret && bits.get(f.hash(value));

}

return ret;

}

// 内部类，simpleHash

public  static  class  SimpleHash {

private  int  cap;

private  int  seed;

public  SimpleHash(int  cap, int  seed) {

this.cap = cap;

this.seed = seed;

}

public  int  hash(String  value) {

int  result = 0;

int  len = value.length();

for (int  i = 0; i < len; i++) {

result = seed * result + value.charAt(i);

}

return (cap - 1) & result;

}

}

}
``````

### LRU Cache

``````// java 哈希表 + 双链表
class  LRUCache {

/**

* 缓存映射表

*/

private  Map<Integer, DLinkNode> cache = new  HashMap<>();

/**

* 缓存大小

*/

private  int  size;

/**

* 缓存容量

*/

private  int  capacity;

/**

* 链表头部和尾部

*/

public  LRUCache(int  capacity) {

//初始化缓存大小，容量和头尾节点

this.size = 0;

this.capacity = capacity;

}

/**

* 获取节点

* @param  key 节点的键

* @return 返回节点的值

*/

public  int  get(int  key) {

if (node == null) {

return -1;

}

//移动到链表头部

(node);

return  node.value;

}

/**

* 添加节点

* @param  key 节点的键

* @param  value 节点的值

*/

public  void  put(int  key, int  value) {

if (node == null) {

cache.put(key, newNode);

//添加到链表头部

++size;

//如果缓存已满，需要清理尾部节点

if (size > capacity) {

cache.remove(tail.key);

--size;

}

} else {

node.value = value;

//移动到链表头部

}

}

/**

* 删除尾结点

*

* @return 返回删除的节点

*/

removeNode(node);

return node;

}

/**

* 删除节点

* @param  node 需要删除的节点

*/

node.next.prev = node.prev;

node.prev.next = node.next;

}

/**

* 把节点添加到链表头部

*

* @param  node 要添加的节点

*/

}

/**

* 把节点移动到头部

* @param  node 需要移动的节点

*/

removeNode(node);

}

/**

* 链表节点类

*/

Integer  key;

Integer  value;

}

this.key = key;

this.value = value;

}

}

}
``````

### 十大经典排序算法

``````// java
public  static  void  quickSort(int[] array, int begin, int end) {

if (end <= begin) return;

int  pivot = partition(array, begin, end);

quickSort(array, begin, pivot - 1);

quickSort(array, pivot + 1, end);

}

static  int  partition(int[] a, int begin, int end) {

// pivot: 标杆位置，counter: 小于pivot的元素的个数

int  pivot = end, counter = begin;

for (int  i = begin; i < end; i++) {

if (a[i] < a[pivot]) {

int  temp = a[counter]; a[counter] = a[i]; a[i] = temp;

counter++;

}

}

int  temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;

return counter;

}
``````

``````// java
public  static  void  mergeSort(int[] array, int left, int right) {

if (right <= left) return;

int  mid = (left + right) >> 1; // (left + right) / 2

mergeSort(array, left, mid);

mergeSort(array, mid + 1, right);

merge(array, left, mid, right);

}

public  static  void  merge(int[] arr, int left, int mid, int right) {

int[] temp = new  int[right - left + 1]; // 中间数组

int  i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {

temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];

}

while (i <= mid) temp[k++] = arr[i++];

while (j <= right) temp[k++] = arr[j++];

for (int  p = 0; p < temp.length; p++) {

arr[left + p] = temp[p];

}

// 也可以用 System.arraycopy(a, start1, b, start2, length)

}
``````

``````// java
public  static  void  heapSort(int[] array) {

if (array.length == 0) return;

int  length = array.length;

for (int  i = length / 2-1; i >= 0; i-)

heapify(array, length, i);

for (int  i = length - 1; i >= 0; i--) {

int  temp = array[0]; array[0] = array[i]; array[i] = temp;

heapify(array, i, 0);

}

}

static  void  heapify(int[] array, int length, int i) {

int  left = 2 * i + 1, right = 2 * i + 2；

int  largest = i;

if (left < length && array[left] > array[largest]) {

largest = left;

}

if (right < length && array[right] > array[largest]) {

largest = right;

}

if (largest != i) {

int  temp = array[i]; array[i] = array[largest]; array[largest] = temp;

heapify(array, length, largest);

}

}``````

## 结语

《L02 从零构建论坛系统》

《G01 Go 实战入门》

7个月前 评论
chenlixin （楼主） 7个月前

7个月前 评论

12

46

232

329