王铮老师《算法》系列文章之37-。
提纲:
贪心算法 greedy algorithm
- 贪心算法并不能总是给出最优解:有权图中找最短路径;
- 分糖果:
- 钱币找零
- 区间覆盖
Huffman Coding:
文本中不同字符个数 + 字符出现频率
编码方式:
字符看作结点并带有频率,所有节点在优先级队列中,每次选择最小的结点组成新的父结点,再放入队列中。
https://static001.geekbang.org/resource/image/7b/7a/7b6a08e7df45eac66820b959c64f877a.jpg
分治算法
divide and conquer:将原问题划分为n个小规模问题,且结构相似。可递归解决这些子问题,然后合并结果。
在归并排序中,合并两个有序的数组过程中,就可以计算两个数组的逆序对个数。如图:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| private int num = 0;
public int count(int[] a, int n){ num = 0; mergeSortCounting(a, 0, n-1); return num; }
private void mergeSortCounting(int[] a, int p, int r){ }
private void merge(int[] a, int p, int q, int r){ }
|
二维平面上有 n 个点,如何快速计算出两个距离最近的点对?
有两个 n*n 的矩阵 A,B,如何快速求解两个矩阵的乘积 C=A*B?
在海量数据处理中
扫描10GB的订单,划分金额区间,存储文件。单独加载小文件到内存中排序。最终合并即可。
MapReduce
MapReduce框架是一个任务调度器,本质为分治思想,底层使用GFS存储数据,使用Borg管理机器。
回溯算法
八皇后问题
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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| package com.youdef.DataStructureAndAlgo;
public class EightQueens { public static void main(String[] args){ call8queens(0); }
static int[] result = new int[8]; static int ccc = 1;
public static void call8queens(int row){ if (row == 8){ printQueens(result); return; } for (int column=0; column<8; ++column){ if (isOk(row, column)){ result[row] = column; call8queens(row+1); } }
}
public static boolean isOk(int row, int column){ int leftup = column-1, rightup = column+1; for (int i=row-1; i>=0; --i){ if (result[i] == column) return false; if (leftup >= 0){ if (result[i] == leftup) return false; } if (rightup < 8){ if (result[i] == rightup) return false; } --leftup; ++rightup; } return true; }
public static void printQueens(int[] result){ System.out.println("第 "+ccc+" 种:"); ccc++;
for (int row=0; row<8; ++row){ for (int column=0; column<8; ++column){ if (result[row]== column) System.out.print("Q "); else System.out.print("* "); } System.out.println(); } System.out.println(); } }
|
0-1背包问题
这里的背包问题中物体是不可分割的,要么装要么不装。这里使用回溯算法解决:
正则表达式
动态规划