天下武功, 无坚不破, 唯快不破 ——— 某大佬
本文为我,leetcode easy player,algorithm(算法)小xuo生在刷题过程中对快慢指针的应用的总结
什么是快慢指针
-
快慢说的是移动的速度, 即每次移动的步长的大小 -
指针为记录变量内存地址的变量, 用它能间接访问变量的值
为了更直观的了解快慢指针, 请看如下c++demo
在内存中开辟容量为11个整型元素的数组存储空间
初始化整型快慢指针变量都记录数组第一个元素的内存地址
在循环里, 慢指针每次增1, 快指针每次增2
因为c++中指针占4字节即32位的16进制的内存空间, 所以慢指针记录的内存地址每次移动4个字节, 而块指针记录的内存地址每次移动8个字节(
注意因为是16进制, 所以快指针从0x7ffee3c63258到0x7ffee3c63260也是移动了8个字节)
#include <iostream>
using namespace std;
int main (int argc, char const *argv[]) {
int arr[11] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int *slowPointer = &arr[0];
cout<<"slowPointer init point address: "<<slowPointer<<endl;
int *fastPointer = &arr[0];
cout<<"fastPointer init point address: "<<fastPointer<<endl;
for (int i = 0; i < 5; ++i) {
slowPointer++;
fastPointer += 2;
cout<<"i = "<<i<<endl;
cout<<"slowPointer point address: "<<slowPointer<<endl;
cout<<"slowPointer -> "<<*slowPointer<<endl;
cout<<"fastPointer point address: "<<fastPointer<<endl;
cout<<"fastPointer -> "<<*fastPointer<<endl;
}
return 0;
}
// slowPointer init point address: 0x7ffee3c63250
// fastPointer init point address: 0x7ffee3c63250
// i = 0
// slowPointer point address: 0x7ffee3c63254
// slowPointer -> 1
// fastPointer point address: 0x7ffee3c63258
// fastPointer -> 2
// i = 1
// slowPointer point address: 0x7ffee3c63258
// slowPointer -> 2
// fastPointer point address: 0x7ffee3c63260
// fastPointer -> 4
// i = 2
// slowPointer point address: 0x7ffee3c6325c
// slowPointer -> 3
// fastPointer point address: 0x7ffee3c63268
// fastPointer -> 6
// i = 3
// slowPointer point address: 0x7ffee3c63260
// slowPointer -> 4
// fastPointer point address: 0x7ffee3c63270
// fastPointer -> 8
// i = 4
// slowPointer point address: 0x7ffee3c63264
// slowPointer -> 5
// fastPointer point address: 0x7ffee3c63278
// fastPointer -> 10
说人话, 龟兔赛跑的故事大家都应该听过, 可以把乌龟🐢比作慢指针, 兔子🐇比作快指针
image
快慢指针的应用场景如下
判断链表是否有环
image
- 染色标记, 缺点: 改变了链表的结构, 若链表为只可读的则不可取, 需开辟额外的
O(n)空间记录标记信息
var hasCycle = function(head) {
let res = false
while (head && head.next) {
if (head.flag) {
res = true
break
} else {
head.flag = 1
head = head.next
}
}
return res
};
- 哈希表记录, 缺点: 哈希表需开辟额外的
O(n)空间
var hasCycle = function(head) {
const map = new Map()
while (head) {
if (map.get(head)) {
return true
} else {
map.set(head, head)
head = head.next
}
}
return false
}
- 快慢指针, 兔子与乌龟同时在头节点出发, 兔子每次跑两个节点, 乌龟每次跑一个节点, 如果兔子能够追赶到乌龟, 则链表是有环的
image
image
image
image
因为不管有没有环, 以及进环前和进换后耗时都与数据规模成正比, 所以时间复杂度为O(n), 因为只需额外的常数级存储空间记录两个指针, 所以空间复杂度为O(1)
var hasCycle = function(head) {
let slowPointer = head
let fastPointer = head
while (fastPointer && fastPointer.next) {
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
if (fastPointer === slowPointer) {
return true
}
}
return false
}
寻找链表的入环节点
image
此题也可用标记法和哈希表法解决, 用快慢指针法解决如下
- 假设入环之前的长度为
L, 入环之后快慢指针第一相遇时快指针比慢指针🐢多跑了N圈, 每一圈的长度为C, 此时快指针🐰在环内离入环节点的距离为C' - 此时慢指针🐢走过的距离为:
L + C' - 此时快指针🐰走过的距离为:
L + C' + N * C - 因为快指针🐰的速度是慢指针🐢的两倍, 所以有:
2 * (L + C') = L + C' + N * C - 整理后得到:
(N - 1) * C + (C - C') = L - 由此可知, 若此时有两个慢指针🐢同时分别从链表头结点和快慢指针第一次相遇的节点出发, 两者必然会在入环节点相遇
image
image
image
image
var detectCycle = function(head) {
let slowPointer = head
let fastPointer = head
while (fastPointer && fastPointer.next) {
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
if (slowPointer === fastPointer) {
slowPointer = head
while (slowPointer !== fastPointer) {
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
}
return slowPointer
}
}
return null
};
寻找重复数
image
此题暴力解法为先排序再寻找重复的数字, 注意不同JavaScript引擎对sort的实现原理不一样, V8 引擎 sort 函数对数组长度小于等于 10 的用插入排序(时间复杂度O(n^2), 空间复杂度O(1))，其它的用快速排序(时间复杂度O(nlogn), 递归栈空间复杂度O(logn)), 参考https://github.com/v8/v8/blob/ad82a40509c5b5b4680d4299c8f08d6c6d31af3c/src/js/array.js
这一题可以利用寻找链表的入环节点的思想, 把数组当成对链表的一种描述, 数组里的每一个元素的值表示链表的下一个节点的索引
如示例1中的[1, 3, 4, 2, 2]
- 把数组索引为0的元素当成链表的头节点
- 索引为0的元素的值为1, 表示头节点的下一个节点的索引为1, 即数组中的3
- 再下一个节点的索引为3, 即为第一个2
- 再下一个节点的索引为2, 即为4
- 再下一个节点的索引为4, 即为第二个2
- 再下一个节点的索引为2, 即为4
- 此时形成了一个环
- 而形成环的原因是下一节点的索引一致, 即为重复的数字
image
image
image
image
var findDuplicate = function(nums) {
let slowPointer = 0
let fastPointer = 0
while (true) {
slowPointer = nums[slowPointer]
fastPointer = nums[nums[fastPointer]]
if (slowPointer == fastPointer) {
let _slowPointer = 0
while (nums[_slowPointer] !== nums[slowPointer]) {
slowPointer = nums[slowPointer]
_slowPointer = nums[_slowPointer]
}
return nums[_slowPointer]
}
}
};
删除链表的倒数第N个元素
image
要删除链表的倒数第N个元素, 需要找到其倒数第N + 1个元素, 让这个元素的next指向它的下下一个节点
image
此题可利用两次正向遍历链表, 或者一次正向遍历的同时记录前节点, 然后再反向遍历
题目的进阶要求只使用一趟扫描, 利用快慢指针可实现
创建虚拟头节点, 让快指针🐰向前移动N + 1个节点, 然后两个指针以同样的速度直至快指针🐰移动至尾结点, 此时慢指针🐢移动到的位置即为被删除的指针前面的一个指针
image
image
image
image
image
image
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(null)
dummy.next = head
let slowPointer = dummy
let fastPointer = dummy
while (n-- > -1) {
fastPointer = fastPointer.next
}
while (fastPointer !== null) {
slowPointer = slowPointer.next
fastPointer = fastPointer.next
}
slowPointer.next = slowPointer.next.next
return slowPointer === dummy ? slowPointer.next : head
};
回文链表
image
- 把链表变成双向链表, 并从两端向中间比较
时间复杂度为O(n), 因为要存储prev指针, 所以空间复杂度为O(n)
var isPalindrome = function(head) {
if (head === null) {
return true
} else {
let headPointer = head
let tailPointer = head
while (tailPointer.next) {
tailPointer.next.prev = tailPointer
tailPointer = tailPointer.next
}
while(headPointer !== tailPointer) {
if (headPointer.next !== tailPointer) {
if (headPointer.val === tailPointer.val) {
headPointer = headPointer.next
tailPointer = tailPointer.prev
} else {
return false
}
// 考虑偶数链表
} else {
return headPointer.val === tailPointer.val
}
}
return true
}
};
- 快慢指针
- 慢指针🐢依次访问下一个节点, 并翻转链表
- 快指针🐰依次访问下下一个节点, 直到快指针🐰没有下一个节点(奇数链表)或者下下一个节点(偶数链表), 此时已完成了前半截链表的翻转
- 依次比较前半截链表和后半截链表节点的值
image
image
image
image
image
时间复杂度O(n), 空间复杂度O(1)
var isPalindrome = function(head) {
if (head === null) {
return true
} else if (head.next === null) {
return true
} else {
let slowPointer = head
let fastPointer = head
let _head = null
let temp = null
// 找到中间节点, 并翻转前半截链表,
// 让_head指向翻转后的前半截链表的头部,
// 让slow指向后半截链表的头节点
while (fastPointer && fastPointer.next) {
_head = slowPointer
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
_head.next = temp
temp = _head
}
// 奇数链表跳过最中间的节点
if (fastPointer) {
slowPointer = slowPointer.next
}
while (_head) {
if (_head.val !== slowPointer.val) {
return false
}
_head = _head.next
slowPointer = slowPointer.next
}
return true
}
};
快乐数
image
- 循环并缓存每次获取位的平方和, 如果已缓存过, 就退出循环, 判断退出循环后是否为1, 缺点: 需开辟
O(n)的存储空间
var isHappy = function(n) {
const memory = {}
while (n !== 1) {
function getBitSquareSum (n) {
let sum = 0
while (n !== 0) {
const bit = n % 10
sum += bit * bit
n = parseInt(n / 10)
}
return sum
}
n = getBitSquareSum(n)
if (memory[n] === undefined) {
memory[n] = 1
} else {
break
}
}
return n === 1
};
- 慢指针🐢获取一次每位的平方和, 快指针🐰获取两次每位的平方和, 当两个指针值一样时判断其是否为1
如37这个数, 对其反复的求每位的平方和会进入循环, 而且进入循环时其值不为1
image
image
image
image
image
image
image
image
image
var isHappy = function (n) {
let slowPointer = n
let fastPointer = n
function getBitSquareSum (n) {
let sum = 0
while (n !== 0) {
const bit = n % 10
sum += bit * bit
n = parseInt(n / 10)
}
return sum
}
do {
slowPointer = getBitSquareSum(slowPointer)
fastPointer = getBitSquareSum(getBitSquareSum(fastPointer))
} while (slowPointer !== fastPointer)
return slowPointer === 1
}
总结
利用快慢指针创造的差值, 可节省内存空间, 减少计算次数, 常用于链表数据结构和判断循环
快慢指针, 一对快乐的指针, just be happy!
image
