算法与数据结构&LeetCode

概述

主要结合 LeetCode ，对算法与数据结构进行总结和分析。

复杂度分析

时间复杂度

空间复杂度

  • 空间换时间，升维：在大多数情况下，会选择牺牲空间复杂度，来提高时间复杂度
  • 一般在算法中，更多的是考虑是否为“原地算法”，即是否需要申请额外的空间。

数组与链表

非受限线性表：指的就是不受规则限制，区别于栈和队列。

  • 数组和链表是所有数据结构的基础，基本上所有数据结构都可以基于数组和链表实现。
  • 数组和链表之间重点掌握区别，数组的查找时间复杂度是O(1)，而链表的增加和删除时间复杂度为O(1)。
  • 数组：注意防止越界
  • 链表：单链表、双向链表、循环链表、静态链表（借助数组，伴随向后继节点的指针）

LeetCode

Array

Linked

栈和队列

受限线性表：需要满足一定的规则，即先进后出或者先进先出等。

  • 栈和队列的重点是掌握其在特殊场合下的应用。
  • 栈：先进后出，FILO。应用：浏览器前进后退、括号匹配、表达式计算。
  • 队列：先进先出，FIFO。
  • 队列的拓展：双端队列（两边均可入队和出队），优先队列（根据优先级来出队）。
  • Java PriorityQueue 源码

LeetCode

Stack

Queue

哈希表、映射、集合

  • 哈希表：又称散列表。重点需要注意哈希冲突，设计好的哈希函数可以减少重复性，但不能完全避免哈希冲突。常用拉链表（散列表+链表）解决哈希冲突，如HashMap。
  • 映射：Map。K/V键值对，key不重复
  • 集合：Set。key不重复

    LeetCode

  • 有效的字母异位词
  • 字母异位词分组
  • 两数之和

二叉树、二叉搜索树

递归

  • 递归模板
  • 核心：递归四部曲，终止条件、执行当前层逻辑、下坠、清理当前层的状态。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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 
     
    }

LeetCode

分治、回溯

分治代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def divide_conquer(problem, param1, param2, ...): 
  # recursion terminator 
  if problem is None: 
	print_result 
	return 

  # prepare data 
  data = prepare_data(problem) 
  subproblems = split_problem(problem, data) 

  # conquer subproblems 
  subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  …

  # process and generate the final result 
  result = process_result(subresult1, subresult2, subresult3, …)
	
  # revert the current level states

LeetCode

BFS、DFS

  • BSF模板

  • 核心：维护一个queue队列，建立一个访问记录visited集合，有时候还需要在节点处记录当前的层数level。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def BFS(graph, start, end):
        visited = set()
    	queue = [] 
    	queue.append([start]) 

    	while queue: 
    		node = queue.pop() 
    		visited.add(node)

    		process(node) 
    		nodes = generate_related_nodes(node) 
    		queue.push(nodes)

    	# other processing work 
    	...

  • DFS模板

  • 核心：DFS在非递归写法时，是维护一个stack栈

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    //递归写法
    visited = set() 

    def dfs(node, visited):
        if node in visited: # terminator
        	# already visited 
        	return 

    	visited.add(node) 

    	# process current node here. 
    	...
    	for next_node in node.children(): 
    		if next_node not in visited: 
    			dfs(next_node, visited)
    			
    //非递归写法
    def DFS(self, tree): 

    	if tree.root is None: 
    		return [] 

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

    	while stack: 
    		node = stack.pop() 
    		visited.add(node)

    		process (node) 
    		nodes = generate_related_nodes(node) 
    		stack.push(nodes) 

    	# other processing work 
    	...

LeetCode

贪心算法

  • 贪心算法是弱化版的动态规划。很多时候都得先判断是否能用贪心算法解决，再使用贪心算法。如最经典的找零问题，在保证大的币种肯定是小的币种的倍数的情况下，可以利用贪心算法解决问题。

    LeetCode

    柠檬水找零

二分查找

  • 特点：有序、有界、能够通过索引随机访问。
  • 二分查找模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    left, right = 0, len(array) - 1 
    while left <= right: 
    	  mid = (left + right) / 2 
    	  if array[mid] == target: 
    		    # find the target!! 
    		    break or return result 
    	  elif array[mid] < target: 
    		    left = mid + 1 
    	  else: 
    		    right = mid - 1

注意，一般防止越界，第三行代码会改写为mid = right + (left - right) >> 1

LeetCode

动态规划

动态规划在大多数情况下和记忆化递归的时间复杂度相近，如经典的爬楼梯问题，既可以使用斐波那契数列，f(n) = f(n-1) + f(n-2)，加上缓存cache的记忆化递归的方式求解，也可以使用动态规划，利用dp方程，dp[i] = dp[i-1] + dp[i-2]进行求解。

  • 自底向上递推
  • 核心：状态转移方程、最近重复子问题、最优子结构

LeetCode

字典树

  • 字典树，又称前缀树、Trie树。主要应用于搜索时前缀单词提示。
  • 核心：理解和记忆Trie树的代码模板
  • Trie树模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Trie(object):
      
    	def __init__(self): 
    		self.root = {} 
    		self.end_of_word = "#" 
     
    	def insert(self, word): 
    		node = self.root 
    		for char in word: 
    			node = node.setdefault(char, {}) 
    		node[self.end_of_word] = self.end_of_word 
     
    	def search(self, word): 
    		node = self.root 
    		for char in word: 
    			if char not in node: 
    				return False 
    			node = node[char] 
    		return self.end_of_word in node 
     
    	def startsWith(self, prefix): 
    		node = self.root 
    		for char in prefix: 
    			if char not in node: 
    				return False 
    			node = node[char] 
    		return True

LeetCode

并查集

  • 并查集，主要应用于解决站队问题，即朋友圈问题。
  • 核心：熟悉并查集的基本操作，即初始化、查询、合并。
  • 并查集模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    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--;
    	}
    }

LeetCode

位运算

  1. 判断奇偶
含义 常规 位运算
判断偶数 x % 2 == 0 (x & 1) == 0
判断基数 x % 2 == 1 (x & 1) == 1
  1. 除以2
常规 位运算
x / 2 x >> 1
int mid = (left + right)/2 int mid = (left + right) >> 1

  1. 清零最低位的1（即：从第0位开始往前，第1个1置为0）

    1
    x = x & (x - 1)

  2. 获取最低位的1（即：从第0位开始往前，获取第1个1）

    1
    x & (-x)

  3. 取0

    1
    x & (~x)

    LeetCode

布隆过滤器

  1. python：代码示例、实现示例、高性能布隆过滤器
  2. java：代码示例 I、代码示例 II

LRU缓存

  • 核心：散列表+双向链表、get和set都是O(1)的时间复杂度
  • 关键词：最近最少使用
  • 用简单的话理解开发容灾
  • 替换算法总揽
  • LRU Cache python 代码示例
  • 基于JAVA的LinkedHashMap（本质即散列表+链表）实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class LRUCache extends LinkedHashMap<Integer, Integer>{
        private int capacity;
        
        public LRUCache(int capacity) {
            super(capacity, 0.75F, true);
            this.capacity = capacity;
        }

        public int get(int key) {
            return super.getOrDefault(key, -1);
        }

        public void put(int key, int value) {
            super.put(key, value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity; 
        }
    }

LeetCode

排序

  • 核心：熟悉含义，了解代码
  • （平均）时间复杂度：
  1. O(n^2)：冒泡排序、插入排序、选择排序
  2. O(nlogn)：快速排序、归并排序
  3. O(n)：桶排序、基数排序、计数排序

LeetCode