算法 | 仰望·星空

1 前言
2 数据结构
3 算法
4 高级搜索
5 高级树搜索
- 5.1 平衡二叉树
6 位运算
7 布隆过滤器与LRU
- 7.1 布隆过滤器
- 7.2 LRU缓存算法
8 排序算法
9 高级排序
10 字符串算法

文章目录[隐藏]

前言
数据结构
算法
高级搜索
高级树搜索
位运算
布隆过滤器与LRU
排序算法
高级排序
字符串算法

前言

推荐一本书《异类》（outliers）,这本书告诉你如何精通一个领域，主要分三步走：

切碎知识点（chunk it up）
刻意练习（deliberate practing）
反馈（feedback）

切碎知识点：把整体分成各个小部分，并且它们之间有一定的脉络。脑图就是这样的一种思想。
刻意练习：过遍数，要过五遍，练习缺陷、弱点的地方。
反馈：反馈的类型有：

即时反馈
主动反馈（自己去找）
比如：主动查看查看高手的代码（GitHub、LeetCode、etc）
被动反馈（高手给你指点）
比如：高手通过Code Review，指出你的缺陷，给出处理的方案

刷题技巧

切题四件套

clarification 确保读懂题目。
possible solutions 想出尽可能多的解法。并从中择优，分析时间复杂度和空间复杂度，一般时间复杂度最小为优。
coding 多写。
test cases 测试代码。

五遍刷题法

第一遍：
5分钟读题+思考
直接看解法：注意！多解法。比较解法的优劣。
背诵、默写算法。
第二遍：
马上自己写。-> letcode提交。
多种解法比较、体会。->优化。
第三遍：
过了一天，再重复做题。
不同解法的熟练程度。->专项练习。
第四遍：
过了一周，反复回来练习相同题目。
第五遍：
面试前一周恢复性训练。

一维
	基础
		数组 array(string)
		链表 linked list
	高级
		栈 stack
		队列 queue
		双端队列 deque
		集合 set
		映射 hash or map
二维
	基础
		树 tree
		图 graph
	高级
		二叉搜索树 binary search tree
		堆 heap
		并查集 disjoint set
		字典树 trie
特殊
		位运算 bitwise
		布隆过滤器 bloom filter
		LRU Cache

算法

if-else，switch -> branch （判断）分支
for，while，loop -> iteration 循环
递归 Recursion
- 分治法 Divide & Conquer
- 回溯 Backtrace
搜索 Search
- 深度优先搜索 Depth First Search
- 广度优先搜索 Breadth First Search
- 启发式的搜索 A*
动态规划 Dynamic Programming
二分查找 Binary Search
贪心 Greedy
数学 Math
几何 Geometry

时间复杂度

以下复杂度由低到高，O(1)最好，O(n!)最差；O(n)是最普遍的，代表有：遍历。
O(1) 常数复杂度
O(log n) 对数复杂度
O(n) 线性复杂度
O(n^2) 平方复杂度
O(n^3) 立方复杂度
O(2^n) 指数复杂度
O(n!) 阶乘复杂度

举例：斐波那契（Fibbonaci）数列的通项式：F(n)=F(n-1)+F(n-2)
以下这段代码，是一个错误的示范。这里直接使用递归，时间复杂度为O(2^n)，不要这么写。

//这是一个错误的示范。这里直接使用递归，时间复杂度为O(2^n)，不要这么写

int fib(int n) {

if (n>=2) return n;

return fib(n-1)+fib(n-2);

}

主定理

用来解决所有递归或分治的函数，怎么来计算它的时间复杂度。

算法	递推关系	时间复杂度
二分查找	T(n)=T(n/2)+O(1)	O(log n)
二叉树遍历	T(n)=2T(n/2)+O(1)	O(n)
二维矩阵二分查找	T(n)=2T(n/2)+O(log n)	O(n)
归并排序	T(n)=2T(n/2)+O(n)	O(nlog n)

举例：二叉树遍历：前序、中序、后序，时间复杂度是多少？
答：根据主定理，二叉树遍历的时间复杂度为O(n)。

数据结构

数组

优点：访问速度快，为O(1)，根据内存地址直接访问。
缺点：删除、插入都为O(n)

数组的操作可以参考Java的ArrayList

链表

优点：插入、删除快，O(1)。
缺点：查询慢 O(n) 从头或从尾开始查找。

代码实现的参考：
Linked List 的标准实现代码
 Linked List 示例代码
 Java 源码分析（LinkedList）

跳表

为了弥补链表的缺陷而设计出来的。为链表的查询加速。
优化的思想：升维（由一维变成二维，空间换时间）。

跳表可以增加多个索引。

跳表的查询时间复杂度：
n/2、n/4、n/8、第k级索引结点的个数就是 n/(2^k)。
假设索引有h级，最高级的索引有2个结点。n/(2^h)=2，从而求得h=log2(n)-1。
跳表的空间复杂度：
原始链表大小为n，每2个结点抽1个，每层索引的结点数：
n/2,n/4,n/8,…,8,4,2
原始链表大小为n，每2个结点抽1个，每层索引的结点数：
n/3,n/9,n/27,…,9,3,1
空间复杂度是O(n)。
工程中的应用
LRU Cache – Linked list
LRU缓存算法
 LRU缓存机制
Redis – Skip List
Redis 设计与实现 »跳跃表
 为啥 redis 使用跳表(skiplist)而不是使用 red-black？

实战题目

把leetcode-cn.com中的”-cn”去掉，即leetcode.com，就可以访问国际版的LeetCode，可以查看世界上优秀的解题思路。

Array：
盛最多水的容器
移动零
爬楼梯
三数之和（高频老题）
两数之和

以上几道题得到的解题思路是：
1.暴力解题（遍历）
2.使用哈希表
3.使用双指针（夹逼、快慢指针）

Linked List
反转链表
两两交换链表中的节点
环形链表
环形链表 II
K 个一组翻转链表
课后作业：
删除排序数组中的重复项
旋转数组
合并两个有序链表
合并两个有序数组
加一

栈和队列

栈：先进后出。
队列：先进先出。
栈和队列的新增和删除时间复杂度为O(1)，查找为O(n)。
参考的文档：
Java 的 Stack 源码

双端队列（Deque）

简单理解：两端都可以进出的队列。
插入、删除的时间复杂度为O(1)，查找为O(n)。
参考的文档：
Java 的 Queue 源码

优先队列（加权队列）

插入的时间复杂度为O(1)，删除、查找为O(log n) -按照元素的优先级取出。
底层具体实现的数据结构较为多样和复杂，有堆(heap)、二叉搜索树(BST)、树堆(treap)等。
参考的文档：
Java 的 PriorityQueue 文档
使用堆实现的优先队列Python版：
Python 的 heapq
高性能的 container 库

实战题目

有效的括号（最近相关性的问题，一般使用栈来解决）
最小栈
 柱状图中最大的矩形
 滑动窗口最大值
课后作业：
用 add first 或 add last 这套新的 API 改写 Deque 的代码。
分析 Queue 和 Priority Queue 的源码。
设计循环双端队列
 接雨水

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表有一个绕不去的问题，那就是哈希冲突，解决哈希冲突有四种方法。
参考文章：
谈谈哈希表
 哈希冲突
增删改查的时间复杂度都是O(1)。如果哈希函数不好或哈希表太小，产生了许多哈希碰撞，就会退化成链表，时间复杂度变为O(n)。所以，要避免发生哈希碰撞，以防退化成链表。
哈希表可以由二叉树，红黑树等实现。
Map和Set
映射(Map)和集合(Set)，都是由哈希表延伸出来的。
Map：K-V对，key不重复；
Set：不重复元素的集合。
Java Set 文档
 Java Map 文档
 面试：为了进阿里，必须掌握HashMap原理和面试题（图解版一）
实战题目
有效的字母异位词
 字母异位词分组
 两数之和
 Anagram, group-anagrams, two sum

二叉树

普通的二叉树是没有顺序的。
形成闭环的二叉树称为图。链表是特殊化的树；树是特殊化的图。
增删改查的时间复杂度都是O(n)。
二叉树的遍历：
前序：根-左-右
中序：左-根-右
后序：左-右-根
由于二叉树自身的定义，它没法有效的进行循环（使用for循环），一般用递归，但也可以强行循环，如广度优先遍历。递归实现比较简单，而循环实现比较麻烦。

二叉搜索树

二叉搜索树是有序的。是指一颗空树或具有下列性质的二叉树：
1、左子树上所有节点的值均小于它的根结点值；
2、右子树上所有节点的值均大于它的根结点值；
3、以此类推：左、右子树也分别为二叉查找树。（这就是重复性）
增删改查的时间复杂度都为O(log n)。
二叉搜索树的删除：
删除关键结点（非叶子结点），找比这个结点稍大一点的子结点作为垫背（作为老大）。
特殊情况：树可以退化成链表，那么增删改查的时间复杂度为O(n)。
树的解题方法一般是递归：
树的自身定义没所谓的后继（链表）这么一个结构，或者说一个便于循环的结构。它只有左结点，右结点。更好的一种方式是，直接对它的左结点，再调用相同的遍历函数（也就是递归）。
二叉搜索树 Demo
实战题目
二叉树的中序遍历
 二叉树的前序遍历
 N叉树的后序遍历
 N叉树的前序遍历
 N叉树的层序遍历

算法

递归

递归：自己调用自己。递归也是一种循环。
递归代码模板：

递归代码模板

递归的思维要点：
1、不要人肉递归；
2、找到最简单方法，将其拆解成可重复解决的问题（重复子问题）；
3、数学归纳法思维。
扩展阅读：
如何优雅地计算斐波那契数列
如何优雅的计算Fibonacci数列
还有一点的是，递归需要关心一下尾递归。
实战题目
爬楼梯
括号生成
翻转二叉树
验证二叉搜索树
二叉树的最大深度
二叉树的最小深度
二叉树的序列化与反序列化
课后作业
二叉树的最近公共祖先
从前序与中序遍历序列构造二叉树
组合
全排列
全排列 II

分治

把大问题分解成子问题，对子问题求解，再把子问题的结果合并，得到问题的解。
分治的基础是递归，它递归的是子问题，子问题具有重复性。
分治代码模板

分治代码模板

Python版本：

def divide_conquer(problem, param1, param2, ...):

# recursion terminator （1.层级,达到了叶子结点，子问题没了）

if problem is None:

print_result

return

# prepare data （2.处理当前逻辑，把大问题如何分成子问题）

data = prepare_data(problem)

subproblems = split_problem(problem, data)

# conquer subproblems （3.下探到下一层，解决子问题）

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 （4.组装结果）

result = process_result(subresult1, subresult2, subresult3, …)

# revert the current level states （5.清理当前层）

C/C++版本：

int divide_conquer(Problem *problem, int params) {

// recursion terminator

if (problem == nullptr) {

process_result

return return_result;

}

// process current problem

subproblems = split_problem(problem, data)

subresult1 = divide_conquer(subproblem[0], p1)

subresult2 = divide_conquer(subproblem[1], p1)

subresult3 = divide_conquer(subproblem[2], p1)

...

// merge

result = process_result(subresult1, subresult2, subresult3)

// revert the current level status

return 0;

}

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;

}

JavaScript版本：

const divide_conquer = (problem, params) => {

// recursion terminator

if (problem == null) {

process_result

return

}

// process current problem

subproblems = split_problem(problem, data)

subresult1 = divide_conquer(subproblem[0], p1)

subresult2 = divide_conquer(subproblem[1], p1)

subresult3 = divide_conquer(subproblem[2], p1)

...

// merge

result = process_result(subresult1, subresult2, subresult3)

// revert the current level status

}

对应的题：括号生成

回溯

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
1.找到一个可能存在的正确的答案。
2.在尝试了所有可能的分步方法后宣告该问题没有答案。
在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
参考文章：算法—-五大算法之回溯法
简单来说，就是用递归一层层的去去试错，错了就回退。目的是尽早发现错误，减少执行的次数。
实战题目
Pow(x, n)
子集
【参考文章：
牛顿迭代法原理
 牛顿迭代法代码】
多数元素（简单、但是高频）
电话号码的字母组合
 N 皇后

深度优先搜索、广度优先搜索

树的遍历或搜索需要，需要保证以下几点：
1、每个结点都要访问一次；（确保数据不漏）
2、每个结点仅仅要访问一次；（不要重复访问，否则效率低）
3、对于结点的访问顺序不限
– 深度优先 depth first search
– 广度优先 breadth first search
扩展：还有一种搜索叫：优先级搜索（即A*搜索，启发式搜索，多用于推荐算法）。
DFS 代码模板（递归写法、非递归写法）

DFS 代码模板（递归写法、非递归写法）

递归写法：
Python版：

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)

C/C++版：

map<int, int> visited;

void dfs(Node* root) {

// terminator

if (!root) return ;

if (visited.count(root->val)) {

// already visited

return ;

}

visited[root->val] = 1;

// process current node here.

// ...

for (int i = 0; i < root->children.size(); ++i) {

dfs(root->children[i]);

}

return ;

}

非递归写法：
Python版：（手动维护一个栈）

def DFS(self, root):

if tree.root is None:

return []

visited, stack = [], [root]

while stack:

node = stack.pop()

visited.add(node)

process (node)

# 生成相关的节点

nodes = generate_related_nodes(node)

stack.push(nodes)

# other processing work

...

C/C++版：

void dfs(Node* root) {

map<int, int> visited;

if(!root) return ;

stack<Node*> stackNode;

stackNode.push(root);

while (!stackNode.empty()) {

Node* node = stackNode.top();

stackNode.pop();

if (visited.count(node->val)) continue;

visited[node->val] = 1;

for (int i = node->children.size() - 1; i >= 0; --i) {

stackNode.push(node->children[i]);

}

return ;

}

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){

results.add(new ArrayList<>());

}

results.get(level).add(root.val);

if(root.left!=null){

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

}

if(root.right!=null){

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

}

JavaScript版：

const visited = new Set()

const dfs = node => {

if (visited.has(node)) return

visited.add(node)

dfs(node.left)

dfs(node.right)

}

BFS 代码模板

Python版：（使用栈）

def BFS(root):

visited = set()

queue = []

queue.append([root])

while queue:

node = queue.pop()

visited.add(node)

process(node)

nodes = generate_related_nodes(node)

queue.push(nodes)

# other processing work

Java版：

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

public List<List<Integer>> levelOrder(TreeNode root) {

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

if (root == null) {

return allResults;

}

Queue<TreeNode> nodes = new LinkedList<>();

nodes.add(root);

while (!nodes.isEmpty()) {

int size = nodes.size();

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

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

TreeNode node = nodes.poll();

results.add(node.val);

if (node.left != null) {

nodes.add(node.left);

}

if (node.right != null) {

nodes.add(node.right);

}

allResults.add(results);

}

return allResults;

}

C/C++版：

void bfs(Node* root) {

map<int, int> visited;

if(!root) return ;

queue<Node*> queueNode;

queueNode.push(root);

while (!queueNode.empty()) {

Node* node = queueNode.top();

queueNode.pop();

if (visited.count(node->val)) continue;

visited[node->val] = 1;

for (int i = 0; i < node->children.size(); ++i) {

queueNode.push(node->children[i]);

}

return ;

}

JavaScript版：

const bfs = (root) => {

let result = [], queue = [root]

while (queue.length > 0) {

let level = [], n = queue.length

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

let node = queue.pop()

level.push(node.val)

if (node.left) queue.unshift(node.left)

if (node.right) queue.unshift(node.right)

}

result.push(level)

}

return result

};

实战题目
二叉树的层序遍历
最小基因变化
括号生成
在每个树行中找最大值
课后作业：
单词接龙
单词接龙 II
岛屿数量
扫雷游戏

贪心算法 Greedy

贪心算法是一种在每一步选择中都采取在当前状态最好或最优（最有利）的选择，从而希望导致结果是全局最好或最优的算法。
简单来说，每步选择当下最优，从而达到全局最优。但是每步最优，全局不一定最优。
贪心与动态规划的区别：
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，优回退功能。
贪心：当下做局部最优判断。
回溯：能够回退。
动态规划：最优判断+回退。（即贪心+回溯）
贪心算法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一旦一个问题可以通过贪心法解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或直接解决一些要求结果不特别精确的问题。
例题：
零钱兑换
改编1：
当硬币可选集合固定：coins=[20,10,5,1];
求最少可以几个硬币拼出总数。比如：total=36。
改编2：
非整除关系的硬币，可选集合：coins=[10,9,1];
求拼出总数为18最少需要多少硬币？
动态规划定义
适用贪心算法的场景：
简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解称为最优子结构。

实战题目
柠檬水找零
 买卖股票的最佳时机 II
分发饼干
 模拟行走机器人
 跳跃游戏
 跳跃游戏 II
贪心法可以从前往后贪，也可以从后往前贪。
先排序，也是解题的一个步骤。

二分查找

二分查找的前提：
1、目标函数单调性（单调递增或递减）；
2、存在上下界；
3、能够通过索引访问。
二分查找代码模板

二分查找代码模板

Fast InvSqrt() 扩展阅读
实战题目
x 的平方根
有效的完全平方数
课后作业：
搜索旋转排序数组
搜索二维矩阵
寻找旋转排序数组中的最小值
使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方

动态规划

动态规划定义
关键点：
动态规划和递归或分治没有根本上的区别（关键看有无最优的子结构）。
共性：找到重复子问题。
差异性：最优子结构、中途可以淘汰次优解。
不同路径
 不同路径 II
最长公共子序列
 【MIT课程】动态规划 I – 最短路径算法（已添加字幕）
一、Fibonacci（斐波那契）数列（一维）、路径计算（二维）。
状态转移方程（DP方程）：opt[1,j] = opt[i+1,j] + opt[i,j+1];
完整逻辑：

if a[i,j] = '空地'：

opt[i,j] = opt[i+1,j] + opt[i,j+1]

else:

opt[i,j] = 0

动态规划关键点（路径计算题目）：
1、最优子结构：opt[n] = best_of(opt[n-1],opt[n-2],…);
2、存储中间状态：opt[i];
3、递推公式（美其名曰：状态转移方程或者DP方程）
一维路径Fibonacci：opt[i] = opt[n-1] + opt[n-2]
二维路径：opt[i,j] = opt[i+1][j] + opt[i][j+1]，且判断a[i,j]是否空地。
二、最长公共子序列
最长公共子序列
动态规划小结：
1、打破自己的思维惯性，形成机器思维；
2、理解复杂逻辑的关键；
3、也是职业进阶的要点、要领。
三、三角形最小路径和
实战题目
爬楼梯
 三角形最小路径和
 三角形最小路径和题解
 最大子序和
 乘积最大子数组
 零钱兑换
四、最大子序列和
五、打家劫舍
实战题目
打家劫舍
 打家劫舍 II
买卖股票的最佳时机
 买卖股票的最佳时机 II
买卖股票的最佳时机 III
最佳买卖股票时机含冷冻期
 买卖股票的最佳时机 IV
买卖股票的最佳时机含手续费
 一个方法团灭 6 道股票问题
高级 DP 实战题目
完全平方数
 编辑距离（重点）
跳跃游戏
 跳跃游戏 II
不同路径
 不同路径 II
不同路径 III
零钱兑换
 零钱兑换 II
课后作业
最长有效括号
 最小路径和
 编辑距离
 解码方法
 最大正方形
 矩形区域不超过 K 的最大数值和
 青蛙过河
 分割数组的最大值
 学生出勤记录 II
任务调度器
 回文子串
 最小覆盖子串
 戳气球
DP三步曲
1、子问题；
2、状态定义（重要）
3、DP方程

字典树 Trie

应用场景：前缀感应。即：输入一个字，联想（猜测）后面可能出现的字。生活场景是，输入法的自动联想。
基本结构：
字典树，即Trie树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

基本性质：
1、结点本身不存完整单词；
2、从根结点到某一结点，路径上经过的字符串连接起来，为该结点对应的字符串；
3、每个结点的所有子结点路径代表的字符都不同。
结点存储额外信息（如频次）

结点的内部结构

核心思想：
字典树的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的。
例题：
二叉树的层序遍历
 实现 Trie
Tire 树代码模板

实战题目
实现 Trie (前缀树)
单词搜索 II

并查集 Disjoint Set

凡是求两两是不是在一个集合，直接套模板代码即可。
适用场景：组团、配对问题。
基本操作：
makeSet(s)：建立一个新的并查集，其中包含s个单元素集合。
unionSet(x,y)：把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并。
find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
并查集的实现：
初始化：

并查集它拥有一个parent数组指向自己，它指向自己表示它自己的话就是自己的集合，或者自己是自己的老大，就这个意思。
查询、合并：

接下来所谓的合并和查询的一个操作。如何查询对任何一个元素，看它的parent再看它的parent就一直往上，直到它的parent等于它自己的时候，说明找到了它的领头元素，就是它的集合的代表元素，那么就表示这个集合是谁，如何合并。比如说我们要把这个集合和这个集合进行合并，要做的一件事就是找出集合的领头元素，在这里就是a，和另外一个集合，它的领头元素在这里的话就是e，然后将parent[e]特意指向a，或者将parent[a]指向e，这两个都是一样的操作。那么假设我们把e的parent指向a的话，那么就这么指过去，最后的话就把这两个进行所谓的合并。
路径压缩：

还有一个叫做所谓的路径压缩。这里的话我们看到d的parent是c，c的parent是b，b的parent是a，那么我们可以直接把这条路上的所有的元素，它的parent都指向a，这样的话还是和原来的表是一样，但是它的查询时间会快不少。原来的话a你要查它的集合的领头元素是谁，要往上走一步走两步走三步，在这里就只要一步即可。
并查集代码模板

并查集代码模板

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--;

}

Python版本：

def init(p):

# for i = 0 .. n: p[i] = i;

p = [i for i in range(n)]

def union(self, p, i, j):

p1 = self.parent(p, i)

p2 = self.parent(p, j)

p[p1] = p2

def parent(self, p, i):

root = i

while p[root] != root:

root = p[root]

while p[i] != i: # 路径压缩 ?

x = i; i = p[i]; p[x] = root

return root

C/C++版本：

class UnionFind {

public:

UnionFind(vector<vector<char>>& grid) {

count = 0;

int m = grid.size();

int n = grid[0].size();

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

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

if (grid[i][j] == '1') {

parent.push_back(i * n + j);

++count;

}

else {

parent.push_back(-1);

}

rank.push_back(0);

}

//递归

int find(int i) {

if (parent[i] != i) {

parent[i] = find(parent[i]);

}

return parent[i];

}

void unite(int x, int y) {

int rootx = find(x);

int rooty = find(y);

if (rootx != rooty) {

if (rank[rootx] < rank[rooty]) {

swap(rootx, rooty);

}

parent[rooty] = rootx;

if (rank[rootx] == rank[rooty]) rank[rootx] += 1;

--count;

}

int getCount() const {

return count;

}

private:

vector<int> parent;

vector<int> rank;

int count;

};

JavaScript版本：

class unionFind {

constructor(n) {

this.count = n;

this.parent = new Array(n);

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

this.parent[i] = i;

}

find(p) {

let root = p;

while (parent[root] !== root) {

root = parent[root];

}

// 压缩路径

while (parent[p] !== p) {

let x = p;

p = this.parent[p];

this.parent[x] = root;

}

return root;

}

union(p, q) {

let rootP = find(p);

let rootQ = find(q);

if (rootP === rootQ) return;

this.parent[rootP] = rootQ;

this.count--;

}

实战题目
朋友圈
岛屿数量
被围绕的区域

高级搜索

1、朴素搜索（暴击搜索）-> 初级搜索；
2、优化方式：不重复（Fibonacci）->初级、剪枝（生成括号问题）->高级；
3、搜索方向：
DFS：深度优先搜索->初级
BFS：广度优先搜索->初级
双向搜索、启发式搜索（也叫A*搜索）->高级

剪枝

整个状态树，这个分支是没有必要的时候，那么我们就把它剪掉。
实战题目
爬楼梯
 括号生成
 N 皇后
 有效的数独
 解数独

双向BFS

分别从头和尾开始搜索，直到中间相遇。

代码模板：
单词接龙的题解
实战题目
单词接龙
 最小基因变化

启发式搜索

A*代码模板

Python版：

def AstarSearch(graph, start, end):

pq = collections.priority_queue() # 优先级 —> 估价函数

pq.append([start])

visited.add(start)

while pq:

node = pq.pop() # can we add more intelligence here ?

visited.add(node)

process(node)

nodes = generate_related_nodes(node)

unvisited = [node for node in nodes if node not in visited]

pq.push(unvisited)

C/C++版：

class Node {

public:

int x;

int y;

bool operator< (const Node &A) {

}

};

void generate_related_nodes(Node &node) {

}

void process(Node &node) {

}

void AstarSearch(vector<vector<int>>& graph, Node& start, Node& end) {

vector<vector<bool> > visited(graph.size(), vector<bool>(graph[0].size(), false));

priority_queue<Node> q;

q.push(start);

while (!q.empty()) {

Node cur = q.top();

q.pop();

visited[cur.x][cur.y] = true;

process(node);

vector<Node> nodes = generate_related_nodes(node)

for (auto node : nodes) {

if (!visited[node.x][node.y]) q.push(node);

}

return ;

}

Java版本：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

public class AStar

{

public final static int BAR = 1; // 障碍值

public final static int PATH = 2; // 路径

public final static int DIRECT_VALUE = 10; // 横竖移动代价

public final static int OBLIQUE_VALUE = 14; // 斜移动代价

Queue<Node> openList = new PriorityQueue<Node>(); // 优先队列(升序)

List<Node> closeList = new ArrayList<Node>();

/**

* 开始算法

public void start(MapInfo mapInfo)

{

if(mapInfo==null) return;

// clean

openList.clear();

closeList.clear();

// 开始搜索

openList.add(mapInfo.start);

moveNodes(mapInfo);

}

/**

* 移动当前结点

private void moveNodes(MapInfo mapInfo)

{

while (!openList.isEmpty())

{

Node current = openList.poll();

closeList.add(current);

addNeighborNodeInOpen(mapInfo,current);

if (isCoordInClose(mapInfo.end.coord))

{

drawPath(mapInfo.maps, mapInfo.end);

break;

}

/**

* 在二维数组中绘制路径

private void drawPath(int[][] maps, Node end)

{

if(end==null||maps==null) return;

System.out.println("总代价：" + end.G);

while (end != null)

{

Coord c = end.coord;

maps[c.y][c.x] = PATH;

end = end.parent;

}

/**

* 添加所有邻结点到open表

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)

{

int x = current.coord.x;

int y = current.coord.y;

// 左

addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);

// 上

addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);

// 右

addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);

// 下

addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);

// 左上

addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);

// 右上

addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);

// 右下

addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);

// 左下

addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);

}

/**

* 添加一个邻结点到open表

private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)

{

if (canAddNodeToOpen(mapInfo,x, y))

{

Node end=mapInfo.end;

Coord coord = new Coord(x, y);

int G = current.G + value; // 计算邻结点的G值

Node child = findNodeInOpen(coord);

if (child == null)

{

int H=calcH(end.coord,coord); // 计算H值

if(isEndNode(end.coord,coord))

{

child=end;

child.parent=current;

child.G=G;

child.H=H;

}

else

{

child = new Node(coord, current, G, H);

}

openList.add(child);

}

else if (child.G > G)

{

child.G = G;

child.parent = current;

openList.add(child);

}

/**

* 从Open列表中查找结点

private Node findNodeInOpen(Coord coord)

{

if (coord == null || openList.isEmpty()) return null;

for (Node node : openList)

{

if (node.coord.equals(coord))

{

return node;

}

return null;

}

/**

* 计算H的估值：“曼哈顿”法，坐标分别取差值相加

private int calcH(Coord end,Coord coord)

{

return Math.abs(end.x - coord.x)

+ Math.abs(end.y - coord.y);

}

/**

* 判断结点是否是最终结点

private boolean isEndNode(Coord end,Coord coord)

{

return coord != null && end.equals(coord);

}

/**

* 判断结点能否放入Open列表

private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)

{

// 是否在地图中

if (x < 0 || x >= mapInfo.width || y < 0 || y >= mapInfo.hight) return false;

// 判断是否是不可通过的结点

if (mapInfo.maps[y][x] == BAR) return false;

// 判断结点是否存在close表

if (isCoordInClose(x, y)) return false;

return true;

}

/**

* 判断坐标是否在close表中

private boolean isCoordInClose(Coord coord)

{

return coord!=null&&isCoordInClose(coord.x, coord.y);

}

/**

* 判断坐标是否在close表中

private boolean isCoordInClose(int x, int y)

{

if (closeList.isEmpty()) return false;

for (Node node : closeList)

{

if (node.coord.x == x && node.coord.y == y)

{

return true;

}

return false;

}

Javascript版本：

function aStarSearch(graph, start, end) {

// graph 使用二维数组来存储数据

let collection = new SortedArray([start], (p1, p2) => distance(p1) - distance(p2));

while (collection.length) {

let [x, y] = collection.take();

if (x === end[0] && y === end[1]) {

return true;

}

insert([x - 1, y]);

insert([x + 1, y]);

insert([x, y - 1]);

insert([x, y + 1]);

}

return false;

function distance([x, y]) {

return (x - end[0]) ** 2 - (y - end[1]) ** 2;

}

function insert([x, y]) {

if (graph[x][y] !== 0) return;

if (x < 0 || y < 0 || x >= graph[0].length || y > graph.length) {

return;

}

graph[x][y] = 2;

collection.insert([x, y]);

}

class SortedArray {

constructor(data, compare) {

this.data = data;

this.compare = compare;

}

// 每次取最小值

take() {

let min = this.data[0];

let minIndex = 0;

for (let i = 1; i < this.data.length; i++) {

if (this.compare(min, this.data[i]) > 0) {

min = this.data[i];

minIndex = i;

}

this.data[minIndex] = this.data[this.data.length - 1];

this.data.push();

return min;

}

insert(value) {

this.data.push(value);

}

get length() {

return this.data.length;

}

估价函数：
启发式函数：h(n)，它用来评价那些结点最有希望的是一个我们要找的结点，h(n)会返回一个非负实数，也可以认为是从结点n的目标结点路径的估计成本。
启发式函数是一种告知搜索方向的方法。它提供了一种明智的方法来猜测哪个邻居结点会导向一个目标。

A* Search 估价函数：
h(current_state) = distance(current_state,target_state)
相似度测量方法
 二进制矩阵中的最短路径的 A* 解法
 8 puzzles 解法比较
实战题目
二进制矩阵中的最短路径
 滑动谜题
 解数独

高级树搜索

平衡二叉树

二叉树在极端情况下会退化成链表，为了避免这种情况，使用平衡二叉树。
1、保证二维维度->左右树结点平衡
2、平衡二叉树有多种
（1）AVL树
1、Balance Factor (平衡因子) ：
是它的左子树的高度减去它的右子树的高度（有时相反）。
balance factor = {-1,0,1}

2、通过旋转操作来进行平衡（四种）
左旋、右旋、左右旋、右左旋。
左旋：

右旋：

左右旋：

右左旋：

参考动画：https://zhuanlan.zhihu.com/p/63272157

为什么会有AVL？怎么定平衡因子：
由来是它查询的时间复杂度是等于树的深度的，所以会记录深度差，得到平衡因子。
平衡因子不平衡怎么办：
通过四种旋转操作达到平衡。

AVL的不足：
结点需要存储额外信息、且调整次数频繁。
（2）近似平衡二叉树
为了弥补平衡二叉树的不足，引申出了近似平衡二叉树，如：红黑树是一种近似平衡二叉树。
红黑树是一种近似平衡的二叉搜索树，它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树；

每个结点要么是红色，要么是黑色；
根结点是黑色；
每个叶结点（NIL结点，空结点）是黑色的；
不能有相邻接的两个红色结点；
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

关键性质：
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
红黑树对比AVL：
1、查询：AVL比红黑树好。AVL是严格的平衡。
2、插入、删除：红黑树比AVL好。AVL旋转操作多。
3、AVL要存更多的额外信息（平衡因子、树高），占用内存多；红黑树只要一个bit来存0、1（表示黑或红）；
4、结合以上几点，查询多的用AVL，其它情况用红黑树。

位运算

为什么需要位运算：
1、机器里的数字表示方式和存储格式就是二进制；
2、十进制、二进制转换。如何从十进制转换为二进制

位运算符

左移	<<	0011 => 0110
右移	>>	0110 => 0011
按位或	\|	0011/1011=> 1011
按位与	&	0011/1011=> 0011
按位取反	~	0011 => 1100
按位异或（相同为0，不同为1）	^	0011/1011=> 1000

XOR-异或

异或：相同为0，不同为1。也可用“不进位加法”来理解。
异或操作的一些特点：
x^0 = x；
x^1s = ~x； // 注意：1s=~0
x^(~x) = 1s；
x^x = 0；
c = a^b=>a^c=b，b^c=a ; // 交换两个数
a^b^c=a^(b^c)=(a^b)^c； // associative

指定位置的位运算

1、将x最右边的n位清零：x&(~0<<n) 2、获取x的第n位置（0或者1）：(x>>n)&1
3、获取x的第n位的幂值：x&(1<<(n-1))
4、仅将第n位，置为1：x|(1<<n)
5、仅将第n位，置为0：x&(~(1<<n))
6、将x最高位至第n位（含）清零：x&((1<<n)-1)
7、将第n位至第0位（含）清零：x&(~(1<<(n+1)-1)) 实战位运算要点： 1、判断奇偶： x%2==1 ->(x&1)==1
x%2==0 ->(x&1)==0
2、x>>1 -> x/2
如：(left+right)/2 -> (left+right)>>1
3、x=x&(x-1) ：清零最低位的1
4、x&-x ：得到最低位的1
5、x&~x -> 0
N 皇后位运算代码示例

N 皇后位运算代码示例

Python版：

def totalNQueens(self, n):

if n < 1: return []

self.count = 0

self.DFS(n, 0, 0, 0, 0)

return self.count

def DFS(self, n, row, cols, pie, na):

# recursion terminator

if row >= n:

self.count += 1

return

bits = (~(cols | pie | na)) & ((1 << n) — 1) # 得到当前所有的空位

while bits:

p = bits & —bits # 取到最低位的1

bits = bits & (bits — 1) # 表示在p位置上放入皇后

self.DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)

# 不需要revert cols, pie, na 的状态

附带非位运算判重（Python）

def solveNQueens(self, n):

def DFS(queens, xy_dif, xy_sum):

p = len(queens)

if p==n:

result.append(queens)

return None

for q in range(n):

if q not in queens and p-q not in xy_dif and \

p+q not in xy_sum:

DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])

result = []

DFS([],[],[])

return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

Java版：

class Solution {

private int size;

private int count;

private void solve(int row, int ld, int rd) {

if (row == size) {

count++;

return;

}

int pos = size & (~(row | ld | rd));

while (pos != 0) {

int p = pos & (-pos);

pos -= p; // pos &= pos - 1;

solve(row | p, (ld | p) << 1, (rd | p) >> 1);

}

public int totalNQueens(int n) {

count = 0;

size = (1 << n) - 1;

solve(0, 0, 0);

return count;

}

C/C++版本：

class Solution {

public:

int totalNQueens(int n) {

dfs(n, 0, 0, 0, 0);

return this->res;

}

void dfs(int n, int row, int col, int ld, int rd) {

if (row >= n) { res++; return; }

// 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历

int bits = ~(col | ld | rd) & ((1 << n) - 1);

while (bits > 0) {

int pick = bits & -bits; // 注: x & -x

dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);

bits &= bits - 1; // 注: x & (x - 1)

}

private:

int res = 0;

};

JavaScript版本：

var totalNQueens = function(n) {

let count = 0;

void (function dfs(row = 0, cols = 0, xy_diff = 0, xy_sum = 0) {

if (row >= n) {

count++;

return;

}

// 皇后可以放的地方

let bits = ~(cols | xy_diff | xy_sum) & ((1 << n) - 1);

while (bits) {

// 保留最低位的 1

let p = bits & -bits;

bits &= bits - 1;

dfs(row + 1, cols | p, (xy_diff | p) << 1, (xy_sum | p) >> 1);

}

})();

return count;

};

实战题目
位1的个数
2的幂
颠倒二进制位
N 皇后
N皇后 II
比特位计数

布隆过滤器与LRU

布隆过滤器

布隆过滤器 VS 哈希表
一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
优点是空间效率和查询时间都远远超过一般的算法。
缺点是有一定的误识别率和删除困难。
布隆过滤器示意图

布隆过滤器只能确定数据不存在，不能保证数据一定存在。
布隆过滤器只作为外部的缓存使用，当数据被断定不存在，就不会查询数据库。
案例：
1、比特币网络；
2、分布式系统（Map-Reduce）- Hadoop、search engine；
3、Redis缓存；
4、垃圾邮箱、评论等过滤。
科普：布隆过滤器(Bloom Filter)的原理和实现,
使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
 布隆过滤器 Python 代码示例
 布隆过滤器 Python 实现示例
 高性能布隆过滤器 Python 实现示例
 布隆过滤器 Java 实现示例 1
布隆过滤器 Java 实现示例 2

LRU缓存算法

1、两个要素：大小、替换策略。
2、哈表（Hash Table）+双链表（Double LinkedList）
3、查询的时间复杂度为O(1)，修改、更新的时间复杂度为O(1)
LRU Cache工作示例：

替换算法总揽
 Understanding the Meltdown exploit
LRU Cache Python 代码示例
（补全代码 12:58）
实战题目
LRU缓存机制

排序算法

1、比较类排序：
通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlog n)，因此也称为非线性时间比较类排序。
2、非比较类排序
不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
3、排序算法的类别

4、效率比较

高级排序

十大经典排序算法

初级排序【时间复杂度为：O(n^2)】

1、选择排序 (Selection Sort)
每次找最小值，然后放到待排序数组的起始位置。

//选择排序，a表示数组，n表示数组大小

public static void selectionSort(int[] a, int n) {

int minIndex, tmp;

for (var i = 0; i < n - 1; i++) {

minIndex = i;

for (var j = i + 1; j < n; j++) {

if (a[j] < a[minIndex]) { // 寻找最小的数

minIndex = j; // 将最小数的索引保存

}

tmp = a[i];

a[i] = a[minIndex];

a[minIndex] = tmp;

}

2、插入排序 (Insertion Sort)
从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

// 插入排序，a表示数组，n表示数组大小

public static void insertionSort(int[] a, int n) {

if (n <= 1) return;

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

int value = a[i];

int j = i - 1;

// 查找插入的位置

for (; j >= 0; --j) {

if (a[j] > value) {

a[j+1] = a[j]; // 数据移动

} else {

break;

}

a[j+1] = value; // 插入数据

}

3、冒泡排序 (Bubble Sort)
嵌套循环，每次查看相邻的元素，如果逆序，则交换。

// 冒泡排序，a表示数组，n表示数组大小

public static void bubbleSort(int[] a, int n) {

if (n <= 1) return;

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

// 提前退出冒泡循环的标志位

boolean flag = false;

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

if (a[j] > a[j + 1]) { // 交换

int tmp = a[j];

a[j] = a[j + 1];

a[j + 1] = tmp;

flag = true; // 表示有数据交换

}

if (!flag) break; // 没有数据交换，提前退出

}

高级排序【时间复杂度为：O(N*logN)】

1、快速排序 (Quick Sort)
数组取标杆(pivot)，将小元素放pivot左边，大元素放右侧，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。
快速排序代码示例

快速排序代码示例

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;

}

Go版本：

func quickSort(array []int, begin, end int) {

if end <= begin {

return

}

pivot := partition(array, begin, end)

quickSort(array, begin, pivot-1)

quickSort(array, pivot+1, end)

}

func partition(array []int, begin, end int) int {

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

pivot, counter := end, begin

for i := begin; i < end; i++ {

if array[i] < array[pivot] {

array[i], array[counter] = array[counter], array[i]

counter++

}

array[pivot], array[counter] = array[counter], array[pivot]

return counter

}

C/C++版本：

int random_partition(vector<int>& nums, int l, intr) {

int random_pivot_index = rand() % (r - l +1) + l; //随机选择pivot

int pivot = nums[random_pivot_index];

swap(nums[random_pivot_index], nums[r]);

int i = l - 1;

for (int j=l; j<r; j++) {

if (nums[j] < pivot) {

i++;

swap(nums[i], nums[j]);

}

int pivot_index = i + 1;

swap(nums[pivot_index], nums[r]);

return pivot_index;

}

void random_quicksort(vector<int>& nums, int l, int r) {

if (l < r) {

int pivot_index = random_partition(nums, l, r);

random_quicksort(nums, l, pivot_index-1);

random_quicksort(nums, pivot_index+1, r);

}

Python版本：

def quick_sort(begin, end, nums):

if begin >= end:

return

pivot_index = partition(begin, end, nums)

quick_sort(begin, pivot_index-1, nums)

quick_sort(pivot_index+1, end, nums)

def partition(begin, end, nums):

pivot = nums[begin]

mark = begin

for i in range(begin+1, end+1):

if nums[i] < pivot:

mark +=1

nums[mark], nums[i] = nums[i], nums[mark]

nums[begin], nums[mark] = nums[mark], nums[begin]

return mark

JavaScript版本：

const quickSort = (nums, left, right) => {

if (nums.length <= 1) return nums

if (left < right) {

index = partition(nums, left, right)

quickSort(nums, left, index-1)

quickSort(nums, index+1, right)

}

const partition = (nums, left, right) => {

let pivot = left, index = left + 1

for (let i = index; i <= right; i++) {

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

[nums[i], nums[index]] = [nums[index], nums[i]]

index++

}

[nums[pivot], nums[index-1]] = [nums[index-1], nums[pivot]]

return index -1

}

2、归并排序【分治】
1、把长度为n的输入序列分成两个长度为n/2的子序列；
2、对这两个子序列分别采用归并排序；
3、将两个排序好的子序列合并成一个最终的排序序列。
归并排序代码示例

归并排序代码示例

归并和快排具有相似性，但步骤顺序相反。
归并：先排序左右子数组，然后合并两个有序子数组。
快排：先调配出左右子数组，然后对于左右子数组进行排序。

3、堆排序【堆插入O(logN)，取最大/小值O(1)】
1、数组元素依次建立小顶堆。
2、依次取堆顶元素，并删除。
堆排序代码示例

堆排序代码示例

特殊排序【时间复杂度为O(n)】

1、计数排序 (Counting Sort)
计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键，存储在额外开辟的数组空间中；然后依次把计数大于1的填充回原数组。
2、桶排序 (Bucket Sort)
桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。
3、基数排序 (Radix Sort)
基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
参考链接
十大经典排序算法
 9 种经典排序算法可视化动画
 6 分钟看完 15 种排序算法动画展示
实战题目
数组的相对排序
 有效的字母异位词
 设计一个排行榜
 合并区间
 翻转对

高级DP方程

复杂度来源：
1、状态拥有更多维度（二维、三维、或者更多，甚至需要压缩）。
2、状态方程更加复杂。
本质：内功、逻辑思维、数学。

编辑距离问题：
解法（补全代码 29:30）

实战题目
爬楼梯
 不同路径
 不同路径 2
打家劫舍
 最小路径和
 股票买卖
 使用最小花费爬楼梯
 编辑距离
课后作业
最长上升子序列
 解码方法
 最长有效括号
 最大矩形
 不同的子序列
 赛车

字符串算法

参考链接：
不可变字符串
 Atoi 代码示例
字符串基础问题：
转换成小写字母
 最后一个单词的长度
 宝石与石头
 字符串中的第一个唯一字符
 字符串转换整数 (atoi)
字符串操作问题：
最长公共前缀
 反转字符串
 反转字符串 II
翻转字符串里的单词
 反转字符串中的单词 III
仅仅反转字母
异位词问题：
有效的字母异位词
 字母异位词分组
 找到字符串中所有字母异位词
回文串问题：
验证回文串
 验证回文字符串 Ⅱ
最长回文子串
最长子串、子序列问题：
最长公共子序列
 编辑距离
 最长回文子串
字符串 +DP 问题：
详细讲解，由浅入深
 详细讲解，由浅入深-详细讲解，由浅入深
 通配符匹配
 不同的子序列
参考链接：
Boyer-Moore 算法
 Sunday 算法
 字符串匹配暴力法代码示例
 Rabin-Karp 代码示例
 KMP 字符串匹配算法视频
 字符串匹配的 KMP 算法
课后作业：
字符串中的第一个唯一字符
 字符串转换整数 (atoi)
反转字符串 II
翻转字符串里的单词
 反转字符串中的单词 III
仅仅反转字母
 找到字符串中所有字母异位词
 最长回文子串
 同构字符串
 验证回文字符串 Ⅱ
通配符匹配
 最长有效括号
 不同的子序列

文章算法转载需要注明出处

前言

刷题技巧

算法

时间复杂度

主定理

数据结构

数组

链表

跳表

栈和队列

双端队列（Deque）

优先队列（加权队列）

实战题目

哈希表

二叉树

二叉搜索树

算法

递归

分治

回溯

深度优先搜索、广度优先搜索

贪心算法 Greedy

二分查找

动态规划

字典树 Trie

并查集 Disjoint Set

高级搜索

剪枝

双向BFS

启发式搜索

高级树搜索

平衡二叉树

位运算

位运算符

XOR-异或

指定位置的位运算

布隆过滤器与LRU

布隆过滤器

LRU缓存算法

排序算法

高级排序

初级排序 【时间复杂度为：O(n^2)】

高级排序 【时间复杂度为：O(N*logN)】

特殊排序【时间复杂度为O(n)】

高级DP方程

字符串算法

您必须 登录 才能发表评论！

初级排序【时间复杂度为：O(n^2)】

高级排序【时间复杂度为：O(N*logN)】

您必须登录才能发表评论！