dsapr

1. 基础算法

快速排序

public void quickSort(int arr, int L, int R) {
  if (L >= R) return;
  
  int x = arr[L], i = L - 1, j = R + 1;
  while(i < j) {
    while(arr[++i] < x);
    while(arr[j--] > x);
    if (i < j) swap(arr, i, j);
  }
  
  quickSort(arr, L, j);
  quickSort(arr, j + l, R);
}

归并排序

public static void mergeSort(int[] arr, int L, int R) {
  	if (L >= R) return;

  	int M = L + R >> 1;
  	int[] tmp = new int[R - L + 1];
 	 	mergeSort(arr, L, M);
 	 	mergeSort(arr,M + 1, R);

  	int k = 0, i = L, j = M + 1;
  	while(i <= M && j <= R)
    	if (arr[i] < arr[j]) tmp[k++] = arr[i++];
  	else tmp[k++] = arr[j++];
  	while(i <= M) tmp[k++] = arr[i++];
  	while(j <= R) tmp[k++] = arr[j++];

  	for (i = L, j = 0; i <= R; i++, j++) arr[i] = tmp[j];
}

二分法

整数二分

// 区间划分为 [L, M], [M + 1, R]
public int bsearch01(int L, int R) {
  while (L < R) {
    int M = L + R >> 1;
    if (check(mid)) R = M;
    else L = M + 1;
  }
}

// 区间划分为 [L, M - 1], [M, R]
public int bsearch01(int L, int R) {
  while (L < R) {
    int M = L + R + 1 >> 1;
    if (check(mid)) L = M;
    else R = M - 1;
  }
}

浮点数二分

public void bsearch() {
  Scanner sc = new Scanner(System.in);
  double x = sc.nextDouble();
  
  int L = 0, R = x;
  while(R - L > Math.pow(10, -8)) {
    double M = (L + R) / 2;
    if (M * M >= x) R = M;
    else L = M;
  }
  
  System.out.println(L);
}

高精度

高精度加减乘除

前缀和与差分

前缀和

注意：下标从 1 开始，arr[0] 定义为 0。可以减少 arr[j] - arr[i] 的特殊判断。

// 一维数组
public static void main(String args[]) {
  Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  int[] arr = new int[N];
  int[] sum = new int[N];
  for (int i = 1; i < N; i++) arr[i] = (int)(Math.random() * 101);
  for (int i = 1; i < N; i++) sum[i] = sum[i - 1] + arr[i];
  
  ArrayUtils.Print(arr);
  ArrayUtils.Print(sum);
}

// 二维数组
public static void main(args[]) {
  Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  int M = sc.nextInt();
  int[][] arr = new int[N][M];
  int[][] sum = new int[N][M];
  for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++)
      arr[i][j] = (int)(Math.random() * 11);
  
  for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++)
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
  
  ArrayUtils.Print(arr);
  ArrayUtils.Print(sum);
}

差分

前缀和的逆运算（原始数组的相邻元素之间的差值）

A 数组为 B 数组的前缀和，B 就为 A 的差分，A 为 B 的前缀和。

arr2 [ 1 ] = arr [ 1 ] - arr [ 0 ]
arr2 [ 2 ] = arr [ 2 ] - arr [ 1 ]
arr2 [ 3 ] = arr [ 3 ] - arr [ 2 ]
...
arr2 [ n ] = arr [ n ] - arr [  n - 1 ]
// 可推导出
arr [ n ] = arr2[ 0 ] + arr2[ 1 ] + arr2[ 2 ] + ... + arr2[ n ]

// 一维数组
public static void main(String args[]) {
  Scanner sc = new Scanner(System.in);
  int N = sc.nextInt();
  int m = sc.nextInt();
  int[] a = new int[N], b = new int[N];
  
  for (int i = 1; i <= N; i++) a[i] = (int)(Math.random() * 11);
  
  for (int i = 1; i <= N; i++) insert(b, i, i, a[i]);
  
  while (m-- > 0) {
    int l = sc.nextInt(), r = sc.nextInt(), c = sc.nextInt();
    insert(b, l, r, c);
  }
  
  for (int i = 1; i <= N; i++) b[i] += b[i - 1];
}

public static void insert(int[] b, int l, int r, int c) {
  b[l] += c;
  b[r + 1] -= c; 
}

// 二维数组
public static void main(String args[]) {
  int n = 5, m = 6, q = 2;
  int a = [n][m];
  int b = [n][m];
  for (int i = 1; i < n; i++)
    for (int j = 1; j < m; j++)
      a[i][j] = (int)(Math.random() * 11);
  
  for (int i = 1; i < n; i++)
    for (int j = 1; j < m; j++)
      insert(b, i, j, i, j, c)
      
  while (q--) {
    int x1, y1, x2, y2, c;
    insert(b, x1, y1, x2, y2);
  }
  
  for (int i = 1; i < n; i++)
    for (int j = 1; i < m; j++)
      b[i][j] += b[i - 1][j] + b[i][j - 1] + b[i - 1][j - 1];
}

public static void insert(int[] b, int x1, int y1, int x2, int y2, int c) {
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;
}

双指针算法

核心思想：将朴素算法优化到 O(n)

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
		O(N^2)
    
for (int i = 0, j = 0; i < N; i++) {
  while (j < i && check(i, j)) j++;
  
  // do somthing
}

位运算

// 打印一个数的 32 位二进制
public static void main(String[] args) {
  int n = 10;
  for (int i = 31; i >= 0; i--) {
    System.out.print(n >> i & 1);
    if (i % 4 == 0) System.out.print("\t");
  }
}
// lowbit
public int lowbit(int n) {
  return ~n+1 & n
}

离散化

区间合并

  1. 按区间左端点排序
  2. 扫描区间进行合并

2. 数据结构

链表与邻接表：树与图的存储

栈与队列：单调队列、单调栈

// 栈
int stk[N], top;
// insert
str[++top] = x;
// pop
str[tt--];
// isEmpty
return top == 0;
// 栈顶
stk[tt];
// 队列===========

// 队尾插入，队头弹出
int q[N], hh, tt = -1;
// 插入
q[++tt] = x;
// 弹出
hh++;
// isEmpty
return hh > tt;
// 取出队头元素
q[hh];

// 单调栈==========
// 找出每个数左边离它最近的比他大/小的数
int tt = 0;
for (int i = 1; i <= n; i++) {
  while (tt > 0 && check(q[tt],i)) tt--;
  stk[+tt] = i;
}
// 单调队列========
// 找出滑动窗口中的最大/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i++) {
  while (hh <= tt && check_out(q[hh])) hh++; // 判断队头是否滑出窗口
  while (hh <= tt && check(q[tt], i)) tt --;
  q[++tt] = i;
}

kmp

Trie

高效地存储和查找字符串集合的数据结构

class TrieNode {
  boolean isWorld;
  TrieNode[] children = new TrieNode[26];
}

public void insert(String str) {
  TrieNode cur = root;
  for (int i = 0; i < str.length; i++) {
    int c = str.charAt(i) - 'a';
    if (cur.children[c] == null) cur.children[c] = new TrieNode();
    cur = cur.children[c];
  }
  cur.isWord = true;
}

public boolean search(String str) {
  TrieNode cur = root;
  for (int i = 0; i < word.lenght(); i++) {
    int c = word.charAt(i) - 'a';
    if (cur.children[c] == null) return false;
    cur = cur.children[c];
  }
  return cur.isWord;
}

public boolean search(String str) {
  TrieNode cur = root;
  for (int i = 0; i < word.lenght(); i++) {
    int c = word.charAt(i) - 'a';
    if (cur.children[c] == null) return false;
    cur = cur.children[c];
  }
  return true;
}

并查集

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中
class UnionFind {
	int[] parent;
  public UnionFind(int N) {
    parent = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
  }
  public int find(int x) {
     if (parent[x] != x) parent[x] = find(parent[x]);
     return parent[x];
  }
  public void union(int x, int y) {
    parent[find(x)] = find(y);
  }
}

class UnionFind {
	int[] parent;
  int[] size;
  public UnionFind(int N) {
    parent = new int[N];
    size = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
    Arrays.fill(size, 1);
  }
  public int find(int x) {
     if (parent[x] != x) parent[x] = find(parent[x]);
     return parent[x];
  }
  public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;
    if (size[rootX] <= size[rootY]) {
      parent[rootX] = rootY;
      size[rootY] += size[rootX];
    } else {
      parent[rootY] = rootX;
      size[rootX] += size[rootY];
    }
  }
}

class UnionFind {
	int[] parent;
  int[] rank;
  public UnionFind(int N) {
    parent = new int[N];
    rank = new int[N];
    for (int i = 0; i < N; i++) parent[i] = i;
    Arrays.fill(rank, 1)
  }
  public int find(int x) {
     if (parent[x] != x) parent[x] = find(parent[x]);
     return parent[x];
  }
  public void union(int x, int y) {
    int rootX = find(x), rootY = find(y);
    if (rootX == rootY) return;
    if (rank[rootX] < rank[rootY]) {
      parent[X] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
      parent[rootY] = rootX;
    } else {
      parent[rootX] = rootY;
      rank[rootY]++;
    }
  }
}

堆

Hash表

STL 使用技巧

3. 搜索与图论

DFS 与 BFS

DFS

stack

BFS

queue

树与图的遍历：拓扑排序

最短路

最小生成树

二分图：染色法、匈牙利算法

5. 动态规划

背包问题

  1. 01背包问题

    经典01背包问题：N 个物品（物品的属性： 体积，价值），V 容量的背包 每件物品只能用一次

    问题：背包能装下的情况下最大利益化挑出物品

  2. 完全背包问题 每件物品有无限个

  3. 多重背包 每个物品数量不一定

  4. 分组背包问题 每组物品中只能选一种物品

题目

动态规划

线性dp

数字三角形、最长上升子序列、