核心套路
学习算法和刷题的框架思维
学习解决问题的思路、套路、框架,养成“框架思维”,不应该纠结于问题的细节,把握问题的共性和本质,做到举一反三。
数据结构的存储方式
数据结构的底层存储方式只有两种:数组(顺序存储)和链表(链式存储)
。
其他的数据结构,比如哈希表、栈、队列、堆、树、图等都是属于具体的上层建筑,都是在数组或者链表上的特殊操作,只是API
特性不同而已。
数组
数组由于是紧凑连续存储,因此可以随机访问,通过索引快速找到对应的元素,而且相对节约存储空间。但正因为连续存储,内存空间必须一次性分配足,所以数组如果要扩容,需要先重新分配一块更大的空间,再把数据全部复制进去,时间复杂度为O(N)
;而且如果想在数组中间和开始位置进行插入和删除操作,每次必须移动后面的所有数据以保持连续,时间复杂度为O(N)
。
数组在开始、中间、最后位置的增删改查分析如下:
- 开始位置:增加和删除都需要挪动元素,所以效率不高,但是查询和修改就比较高效。
- 中间位置:增加和删除都需要挪动元素,所以效率不高,但是查询和修改就比较高效。
- 最后位置:增加和删除位置不需要挪动元素,效率比较高,同时查询和修改效率也比较高。
链表
链表因为元素不连续,靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后继,操作指针即可删除该元素或者插入新元素,时间复杂度为O(1)
。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,因此会消耗相对更多的存储空间。
链表在开始、中间、最后位置的增删改查分析如下:
- 开始位置:增加和删除元素只需要操作指针,效率较高,查询和修改元素就在头节点不需要进行遍历,所以效率也比较高。
- 中间位置:增加和删除元素只需要操作指针,效率较高,查询和修改元素需要从头节点开始进行遍历,时间复杂度为
O(N)
,所以效率不高。 - 最后位置:增加和删除元素只需要操作指针,效率较高,查询和修改元素需要从头节点开始进行遍历,时间复杂度为
O(N)
,所以效率不高。
综上所述:
- 如果想要查询和修改比较高效,那就使用数组的底层结构。
- 如果想要插入和删除比较高效,那就使用链表的底层结构。
数据结构的基本操作
任何的数据结构其基本操作就是遍历+访问,在详细一点就是:各种数据结构在不同的应用场景下尽可能高效地进行增删改查。
各种数据结构的遍历+访问无非就是两种形式:线性(for/while迭代)和非线性(递归)
。
数组遍历框架,是典型的线形结构:
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
//迭代访问arr[i]
}
}
链表遍历框架,兼具迭代和递归结构:
class ListNode {
int val;
ListNode next;
}
void traverse1(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
//迭代遍历p.val
}
}
void traverse2(ListNode head) {
//前序遍历head.val
traverse2(head.next);
//后序遍历head.val
}
二叉树具有前序遍历、中序遍历、后序遍历,其实链表也有前序遍历和后序遍历。如果在前序遍历的位置打印head.val
,那么就是正序打印链表;如果在后序遍历的位置打印head.val
,那么就是倒序打印链表。
二叉树遍历框架,是典型的非线性递归遍历结构:
class TreeNode {
int val;
TreeNode left, right;
}
void traverse(TreeNode root) {
//前序遍历
traverse(root.left);
//中序遍历
traverse(root.right);
//后序遍历
}
通过上面的代码可以看到二叉树的遍历与链表的遍历方式非常相似,所以可以将遍历方式扩展到N
叉树。
N
叉树的遍历框架如下所示:
class TreeNode {
int val;
TreeNode[] childrens;
}
void traverse(TreeNode root) {
for (TreeNode children : root.childrens) {
traverse(children);
}
}
N
叉树的遍历又可以扩展到图的遍历,因为图就是好几个N
叉树的结合体。但是图有可能出现环,这其实很好解决,使用布尔数组visited
做标记就可以了。所谓的框架思维就是记住这些遍历框架,根据具体问题在框架上添加代码即可。
算法刷题指南
数据结构和算法
数据结构是工具,算法是通过合适的工具解决特定问题的方法。
- 先刷二叉树,因为二叉树是最容易培养框架思维的,而且大部分的常考算法本质上都是树的遍历问题。
- 试着从框架看问题,而不要纠结于细节。
动态规划解题套路框架
回溯算法解题套路框架
全排列问题
N皇后问题
最后总结
BFS算法套路框架
BFS(广度优先搜索-Broad First Search)
和DFS(深度优先搜索-Depth First Search)
是两种特别常用的算法,其中DFS
可被认为就是前面的回溯算法。BFS
核心思想:把一些问题抽象成图,从一个点开始,向四周扩散,一般来说,BFS
都是用队列这种数据结构,每次都是将一个节点周围的所有节点加入队列。BFS
和DFS
的区别:BFS
找到的路径一定是最短的,但代价是空间复杂度要比DFS
大很多。
算法框架
BFS
出现的场景:问题的本质就是让你在一幅图中找到从起点到终点的最近距离。所谓的BFS
本质就是解决该问题的,但是实际中很多题目的描述都是这个本质场景的各种变体,要把现实问题的场景抽象成一幅图,使用BFS
的思想进行求解。
框架如下:
int BFS(Node start, Node target) {
//核心数据结构,节点类型的队列
Queue<Node> q;
//记录已经走过的节点,避免走回头路
Set<Node> visited;
//将起点加入队列中
q.offer(start);
visited.add(start);
//记录扩散的步数
int step = 0;
//队列非空执行
while (q not empty){
//获取队列长度
int sz = q.size();
//将当前队列中的所有节点向四周扩散
for (int i = 0; i < sz; i++) {
//取出队列头元素
Node cur = q.poll();
//划重点:这里判断是否达到终点
if (cur is target){
return step;
}
//将cur的相邻节点加入队列
for (Node x : cur.adj()) {
//判断当前节点是否被访问过
if (x not in visited){
//加入相邻节点到队列中
q.offer(x);
visited.add(x);
}
}
}
//划重点:队列中的数据已经更新为新的数据,在这里更新步数
step++;
}
return step;
}
变量解释
q
就是核心的队列
数据结构;cur
就是当前节点,即队列的头元素;cur.adj()
泛指与cur
相邻的所有节点,比如在二维数组中,cur
上下左右四面的位置就是相邻节点;visited
的主要作用是防止走回头路,大部分时候都是必需的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要visited
;
二叉树的最小高度
需求:计算一棵二叉树的最小高度,输入一棵二叉树,计算它的最小高度,也就是根节点到叶子节点的最短距离。
分析:起点是什么?
root!
终点是什么?cur.left == null and cur.right == null!
代码如下:
/***
* @Description: 二叉树节点
* @Author: Mr.Tong
*/
class TreeNode {
int val;
TreeNode left, right;
}
/***
* @Description: 二叉树的最小高度
* @Author: Mr.Tong
*/
int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 1;//root本身就是一层
while (!q.isEmpty()) {
int size = q.size();
//队列中所有节点向四周扩散
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
//判断当前节点是不是终点
if (cur.left == null && cur.right == null) {
return depth;
}
//将当前节点相邻的所有节点放入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
//更新步数
depth++;
}
return depth;
}
理解
整个算法过程通过画图可以很容易的理解,后面的几个LeetCode
题目也建议通过画图的方式加深对BFS
思想的理解。
- 两个问题
为什么BFS可以找到最短距离,DFS不行吗?
BFS
的逻辑是depth
每增加一次,队列中所有节点都向前迈了一步,这个逻辑保证了一旦找到一个终点,走的步数是最少的,BFS
的时间复杂度最坏情况是O(N)
。DFS
也是可以找到最短路径的,时间复杂度也是O(N)
,但是实际上比BFS
低效很多。这是因为DFS是靠递归的堆栈记录走过的路径的,如果要找到最短路径,肯定要把二叉树中的所有树杈都走完,然后才能对比得到最短路径,但是BFS
借助队列可以做到一步一步“齐头并进”,是可以在还没遍历完整的一棵树的时候就可以找到最短距离。- 总结一下:
DFS
是线,BFS
是面,DFS
是单打独斗,BFS
是集体行动。
既然BFS那么好,那么为什么还需要DFS?
BFS
是可以找到最短路径,但是其空间复杂度高,而DFS
的空间复杂度较低。- 假设有一棵树是满二叉树,节点数为
N
,对于DFS
算法来说,空间复杂度无非就是递归堆栈,在最坏情况下顶多就是树的高度,也就是O(logN)
。但是对于BFS
算法来说。队列中每次都会存储二叉树一层的节点,这样在最坏情况下空间复杂度应该是树的最下层节点的数量,也就是N/2
,即O(N)
。 BFS
还是有代价的,一般来说在找最短路径的时候用的是BFS
,其他情况用的还是DFS
多一些(递归代码好写)。
LeetCode
相关题目
小总结
BFS
是广度优先搜索,其抽象是以图的概念进行说明,但是在二叉树等数据结构中却频繁用到该算法,这是因为二叉树、二维数组等就是图的具体化。
图中某个节点向四周扩散具体到二叉树、二维数组等数据结构分别是:二叉树某个节点扩散到其左右子节点、二维数组某个节点扩散到其上下左右四个子节点。但是树结构一般不用visited
来防止走回头路,因为根本就没有子节点到父节点的指针存在,所以不用担心会走回头路。
解开密码锁的最少次数
题目链接:打开转盘锁
不管所有的限制条件,不管
deadends
和target
的限制,就思考⼀个问题:如果让你设计⼀个算法,穷举所有可能的密码组合,你怎么做?穷举:总共有 4 个位置, 每个位置可以向上转,也可以向下转,也就是有 8 种可能,然后,再以这 8 种密码作为基础,对每个密码再转⼀下,穷举出所有可能。
仔细想想,这就可以抽象成⼀幅图,每个节点有 8 个相邻的节点,⼜让求最短距离,这就是典型的
BFS
。
穷举所有可能的密码组合
// 将 s[j] 向上拨动⼀次
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// 将 s[j] 向下拨动⼀次
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
// BFS 框架,打印出所有可能的密码
void BFS(String target) {
// 核心数据结构-队列
Queue<String> q = new LinkedList<>();
// 添加根节点
q.offer("0000");
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for (int i = 0; i < sz; i++) {
String cur = q.poll();
/* 判断是否到达终点 */
System.out.println(cur);
/* 将⼀个节点的相邻节点加⼊队列 */
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
String down = minusOne(cur, j);
q.offer(up);
q.offer(down);
}
}
// 队列中的数据已经更新完
/* 在这⾥增加步数 */
}
return;
}
// 1000 9000 0100 0900 0010 0090 0001 0009 -> 第一次更新数据
// ... -> 以上面的八个数为基础进行第二次数据的更新,以此类推
上面的代码可以穷举所有的密码组合,但是还存在如下问题:
- 会走回头路。比如从
0000
转到1000
之后,在转1000
的时候还会转到0000
,这样就产生了死循环。 - 没有终止条件。按照题目要求找到
target
就应该返回步数。 - 没有对
deadends
进行处理。这些死亡密码是不能出现的,所以在碰到这些密码的时候应该跳过。
通过对上述代码进行修改:
class Solution {
// 将 s[j] 向上拨动⼀次
String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '9')
ch[j] = '0';
else
ch[j] += 1;
return new String(ch);
}
// 将 s[j] 向下拨动⼀次
String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] == '0')
ch[j] = '9';
else
ch[j] -= 1;
return new String(ch);
}
public int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// 记录已经穷举过的密码,防⽌⾛回头路
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
// 从起点开始启动⼴度优先搜索
int step = 0;
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
int sz = q.size();
/* 将当前队列中的所有节点向周围扩散 */
for (int i = 0; i < sz; i++) {
String cur = q.poll();
/* 判断是否到达终点 */
if (deads.contains(cur))
// 出现死亡密码,直接跳过,开始下一个密码
continue;
if (cur.equals(target))
// 返回步数
return step;
/* 将⼀个节点的未遍历相邻节点加⼊队列 */
for (int j = 0; j < 4; j++) {
// 向上转动
String up = plusOne(cur, j);
if (!visited.contains(up)) {
q.offer(up);
visited.add(up);
}
// 向下转动
String down = minusOne(cur, j);
if (!visited.contains(down)) {
q.offer(down);
visited.add(down);
}
}
}
/* 在这⾥增加步数 */
step++;
}
// 如果穷举完都没找到⽬标密码,那就是找不到了
return -1;
}
}
优化
deads
集合和visited
集合都是记录不合法访问的集合,可以不需要 visited
这个哈希集合,直接将遍历过的元素加到deads
集合中,效果是⼀样的,可能更加优雅⼀些。
BFS
算法还有一种稍微高级的优化思路:双向BFS
,使用双向BFS
可以进一步提高算法的效率。
传统的BFS和双向BFS的区别
传统的BFS框架
就是从起点开始向四周扩散,遇到终点时停⽌;⽽双向BFS
则是从起点和终点同时开始扩散,当两边有交集的时候停⽌。
从 Big O
表⽰法分析算法复杂度的话,它俩的最坏复杂度都是 O(N)
,但是实际上双向BFS
确实会快⼀些。
按照传统BFS
算法的策略,会把整棵树的节点都搜索⼀遍,最后找到target
;⽽双向BFS
其实只遍历了半棵树就出现了交集,也就是找到了最短距离,明显实现了效率上的提升。
双向BFS的局限性
双向BFS
也有局限,因为必须要知道终点在哪⾥。- ⽐如刚才讨论的⼆叉树最⼩⾼度的问题,⼀开始根本就不知道终点在哪⾥,也就⽆法使⽤
双向BFS
;但是第⼆个密码锁的问题,是可以使⽤双向BFS
算法来提⾼效率。
使用双向BFS
进行优化:
public int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// ⽤集合不⽤队列,可以快速判断元素是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int step = 0;
q1.add("0000");
q2.add(target);
while (!q1.isEmpty() && !q2.isEmpty()) {
// 哈希集合在遍历的过程中不能修改,⽤ temp 存储扩散结果
Set<String> temp = new HashSet<>();
/* 将 q1 中的所有节点向周围扩散 */
for (String cur : q1) {
// 不能出现死亡密码
if (deads.contains(cur))
continue;
/* 判断是否到达终点 */
if (q2.contains(cur))
return step;
visited.add(cur);
/* 将⼀个节点的未遍历相邻节点加⼊集合 */
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up))
temp.add(up);
String down = minusOne(cur, j);
if (!visited.contains(down))
temp.add(down);
}
}
/* 在这⾥增加步数 */
step++;
// temp 相当于 q1
// 这⾥交换 q1 q2,下⼀轮 while 就是扩散 q2
q1 = q2;
q2 = temp;
}
return -1;
}
- 不再使⽤队列,⽽是使⽤
HashSet
⽅便快速判断两个集合是否有交集。 - 另外的⼀个技巧点就是
while
循环的最后交换q1
和q2
的内容,所以只要默认扩散q1
就相当于轮流扩散q1
和q2
。
双向BFS
还有⼀个优化,就是每次将少的那个集合进行扩散,避免轮流扩散q1
和q2
。
public int openLock(String[] deadends, String target) {
// 记录需要跳过的死亡密码
Set<String> deads = new HashSet<>();
for (String s : deadends) deads.add(s);
// ⽤集合不⽤队列,可以快速判断元素是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int step = 0;
q1.add("0000");
q2.add(target);
while (!q1.isEmpty() && !q2.isEmpty()) {
// 哈希集合在遍历的过程中不能修改,⽤ temp 存储扩散结果
Set<String> temp = new HashSet<>();
/* 将 q1 中的所有节点向周围扩散 */
for (String cur : q1) {
// 不能出现死亡密码
if (deads.contains(cur))
continue;
/* 判断是否到达终点 */
if (q2.contains(cur))
return step;
visited.add(cur);
/* 将⼀个节点的未遍历相邻节点加⼊集合 */
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up))
temp.add(up);
String down = minusOne(cur, j);
if (!visited.contains(down))
temp.add(down);
}
}
/* 在这⾥增加步数 */
step++;
// 下一轮进行扩散的时候,扩散较少的那个集合
// 对于temp和q2来说,将最小的那个给q1
if (temp.size() <= q2.size()) {
q1 = temp;
} else {
q1 = q2;
q2 = temp;
}
}
return -1;
}
因为按照 BFS
的逻辑,队列(集合)中的元素越多,扩散之后新的队列 (集合)中的元素就越多;在双向BFS
算法中,如果我们每次都选择⼀个较⼩的集合进⾏扩散,那么占⽤的空间增⻓速度就会慢⼀些,效率就会⾼⼀ 些。
时间复杂度
⽆论传统BFS
还是双向BFS
,⽆论做不做优化,从Big O
衡量标准来看,时间复杂度都是⼀样的。因为双向BFS
的代码只是更换了返回结果的方式(哈希集合是否有交集),每次进行扩散的方式不是并行扩散的,而是轮流进行扩散。
LeetCode
相关题目
双指针技巧套路框架
双指针技巧可以分为如下的两类:
- 一类是“快慢指针”,主要解决链表中的问题,比如典型的判定链表中是否包含环。
- 一类事“左右指针”,主要解决数组(或者字符串)中的问题,比如二分搜索。
快慢指针的常用算法
快慢指针一般会初始化指向链表的头节点head
,前进时快指针fast
在前,慢指针slow
在后。
判定链表中是否含有环
链表的特点是每个节点只知道下一个节点,所以一个指针是无法判断链表中是否含有环的。
- 如果链表中不含环,那么这个指针最终会遇到空指针
null
,表示链表到头了,可以判断当前链表是不含有环的。
boolean hasCycle(ListNode head) {
while (head != null) {
head = head.next;
}
return false;
}
- 如果链表中含有环,上述代码就会陷入死循环,因为环形链表中没有空指针
null
,无法判断当前链表含有环。
判断单链表中是否有环,经典的算法就是使用双指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到null
,说明链表不含环;如果含有环,快指针最终会和慢指针相遇,说明链表含有环。
boolean hasCycle(ListNode head) {
//定义快慢指针
ListNode fast, slow;
//初始化快慢指针都指向头节点
fast = slow = head;
while (fast != null && fast.next != null) {
//快指针每次走两步
fast = fast.next.next;
//慢指针每次走一步
slow = slow.next;
//如果存在环,快慢指针必然会相遇
if (fast == slow) {
return true;
}
}
//循环可以停止,说明单链表中不存在环
return false;
}
已知链表中含有环,返回这个环的起始位置
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
//快慢指针初始化
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
break;
}
}
//上面的代码类似于hasCycle函数
//现在fast=slow,两者相遇,说明链表存在环,并且相遇点肯定是在环内部(包括环起点)的内部的某个节点
//相遇点不可能在环外部,因为fast虽然跑得快,但是跑不出环
//先把一个指针重新指向head
slow = head;
//现在slow在fast后面,两者在以相同的速度跑,下一次相遇点就是环的起点
while (slow != fast) {
//两个指针以相同的速度向前跑
fast = fast.next;
slow = slow.next;
}
//slow=fast的时候,跳出循环,两个指针再次相遇
//两个指针再次相遇的那个单链表节点就是环的起点
return slow;
}
结论:当快慢指针相遇时,让其中任何一个指针指向头节点,然后让两个指针以相同的速度前进,再次相遇时所在的节点位置就是环的起点位置。
寻找无环单链表的中点
最直接的思路:先遍历一遍链表,算出链表的长度n
,然后再一次遍历链表,走n/2
步,这样就得到了链表的中点。
漂亮的思路:使用双指针,让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头的时候,慢指针就处于链表的中间位置。
ListNode getMidNodeFromList(ListNode head) {
ListNode fast, slow;
//初始化快慢指针
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
注意
当链表长度为奇数的时候,slow
恰巧停留在中间位置;当链表长度为偶数的时候,slow
最终的位置是中间偏右。
寻找链表中点作用
寻找链表中点的一个重要作用是对链表进行归并排序,可以尝试参考数组的归并排序写出链表的归并排序。
寻找单链表的倒数第K个元素
使用快慢指针,让快指针先走k
步,然后快慢指针开始以相同速率前进,这样当快指针到链表末尾的时候,慢指针所在的位置就是链表倒数第k
个节点(为了简化,假设k
不会超过链表长度)。
ListNode findKNodeFromListEnd(ListNode head, int k) {
ListNode fast, slow;
fast = slow = head;
//快指针先走k步
while (k != 0) {
fast = fast.next;
k--;
}
//快慢指针以相同的速率跑
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
//此时slow所在的节点就是倒数第k个节点
return slow;
}
LeetCode相关题目:
左右指针的常用算法
左右指针一般运用在数组问题中,实际就是两个索引值,一般初始化规则如下:
left=0;
right=length(array)-1;
二分搜索
后续会有二分搜索的细节描述,在此给出最简单的二分查找算法,旨在突出其双指针特性。
/***
* @Description: 二分查找算法,默认nums数组升序
* @Author: Mr.Tong
*/
int binarySearch(int[] nums, int target) {
//初始化左右指针
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;//找到就返回其索引
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
//找不到直接返回-1
return -1;
}
两数之和
输入一个已按照升序排列的有序数组nums
和一个目标值target
,在nums
中找到两个数使得它们相加之和等于target
,请返回这两个数的索引(可以假设这两个数一定存在,索引从1开始)。
只要数组有序,就应该想到使用双指针技巧,通过sum
的大小来调节left
和right
的移动。
/***
* @Description: 两数之和
* @Author: Mr.Tong
*/
int[] twoSum(int[] nums, int target) {
//左右指针初始化
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum > target) {
//让sum小一点
right--;
} else if (sum < target) {
//让sum大一点
left++;
}
}
//找不到
return new int[]{-1, -1};
}
反转数组
虽然很多编程语言提供了原地反转数组的API,但是仍然要懂得其原理。
/***
* @Description: 原地反转数据
* @Author: Mr.Tong
*/
void reverse(int[] nums) {
//初始化左右指针
int left = 0;
int right = nums.length - 1;
while (left < right) {
//交换左右两个指针指向的数据
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
//指针移动
left++;
right--;
}
}
滑动窗口算法
滑动窗口算法是双指针技巧的最高境界,严格讲,它是快慢指针在数组(字符串)上的应用。若掌握该算法,可以解决一大类字符串匹配问题。该部分比前面稍微复杂,可以查看后续的滑动窗口算法框架。
二分搜索算法
一个笑话
有一天阿东到图书馆借了N
本书,出图书馆的时候,警报响了,于是保安把阿东拦下, 要检查哪本书没有登记出借。阿东正准备把每一本书放在报警器下过一下,以找出引发警报的书,但是保安露出不屑的眼神:你连二分搜索都不会吗?
于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成 两堆。最终,检测了logN
次之后,保安成功地找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是阿东背着剩下的书走了。
从此,图书馆丢了N-1
本书。
二分搜索并不简单,Knuth
“大佬”(发明KMP
算法的那位)是这么评价二分搜索的:
Although the basic idea of binary search is comparatively straightforward, the details canbe surprisingly tricky.
说人话就是:思路很简单,细节是魔鬼。
其细节在于到底要给mid
加1还是减1,while
里面到底是<=
还是<
。
二分搜索框架
基础框架如下所示,后面的二分搜索的变形都是基于该框架。
/***
* @Description: 二分搜索框架
* @Author: Mr.Tong
*/
int binarySearch(int[] nums, int target) {
int left = 0;
int right =...;
while (...){
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left =...;
} else if (nums[mid] > target) {
right =...;
}
}
return ...;
}
注意:
- 不要出现
else
,而是使用else-if
考虑到所有的情况,可以清楚展现细节。 ...
标记的地方都是出现细节问题的地方。int mid = left + (right - left) / 2
是为了防止溢出。
寻找一个数(基本的二分搜索)
需求:在一个有序数组中查找一个数,如果找到就返回其索引,如果找不到就返回-1。
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;//注意
while (left <= right) {//注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;//注意
} else if (nums[mid] > target) {
right = mid - 1;//注意
}
}
//循环跳出,找不到就返回-1
return -1;
}
问题一:为什么
while
循环的条件中是<=
,而不是<
?问题二:为什么left = mid + 1和right = mid - 1?有的代码是right = mid或者left = mid,没有这些加加减减,到底是怎么回事?怎么判断?
问题三:该算法有什么缺陷?