天下武功, 無堅不破, 唯快不破 ——— 某大佬
本文為我,leetcode easy player,algorithm(算法)小xuo生在刷題過程中對快慢指針的應用的總結
什么是快慢指針
-
快慢說的是移動的速度, 即每次移動的步長的大小 -
指針為記錄變量內存地址的變量, 用它能間接訪問變量的值
為了更直觀的了解快慢指針, 請看如下c++demo
在內存中開辟容量為11個整型元素的數組存儲空間
初始化整型快慢指針變量都記錄數組第一個元素的內存地址
在循環(huán)里, 慢指針每次增1, 快指針每次增2
因為c++中指針占4字節(jié)即32位的16進制的內存空間, 所以慢指針記錄的內存地址每次移動4個字節(jié), 而塊指針記錄的內存地址每次移動8個字節(jié)(
注意因為是16進制, 所以快指針從0x7ffee3c63258到0x7ffee3c63260也是移動了8個字節(jié))
#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
快慢指針的應用場景如下
判斷鏈表是否有環(huán)
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
}
- 快慢指針, 兔子與烏龜同時在頭節(jié)點出發(fā), 兔子每次跑兩個節(jié)點, 烏龜每次跑一個節(jié)點, 如果兔子能夠追趕到烏龜, 則鏈表是有環(huán)的
image
image
image
image
因為不管有沒有環(huán), 以及進環(huán)前和進換后耗時都與數據規(guī)模成正比, 所以時間復雜度為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
}
尋找鏈表的入環(huán)節(jié)點
image
此題也可用標記法和哈希表法解決, 用快慢指針法解決如下
- 假設入環(huán)之前的長度為
L, 入環(huán)之后快慢指針第一相遇時快指針比慢指針??多跑了N圈, 每一圈的長度為C, 此時快指針??在環(huán)內離入環(huán)節(jié)點的距離為C' - 此時慢指針??走過的距離為:
L + C' - 此時快指針??走過的距離為:
L + C' + N * C - 因為快指針??的速度是慢指針??的兩倍, 所以有:
2 * (L + C') = L + C' + N * C - 整理后得到:
(N - 1) * C + (C - C') = L - 由此可知, 若此時有兩個慢指針??同時分別從鏈表頭結點和快慢指針第一次相遇的節(jié)點出發(fā), 兩者必然會在入環(huán)節(jié)點相遇
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
這一題可以利用尋找鏈表的入環(huán)節(jié)點的思想, 把數組當成對鏈表的一種描述, 數組里的每一個元素的值表示鏈表的下一個節(jié)點的索引
如示例1中的[1, 3, 4, 2, 2]
- 把數組索引為0的元素當成鏈表的頭節(jié)點
- 索引為0的元素的值為1, 表示頭節(jié)點的下一個節(jié)點的索引為1, 即數組中的3
- 再下一個節(jié)點的索引為3, 即為第一個2
- 再下一個節(jié)點的索引為2, 即為4
- 再下一個節(jié)點的索引為4, 即為第二個2
- 再下一個節(jié)點的索引為2, 即為4
- 此時形成了一個環(huán)
- 而形成環(huán)的原因是下一節(jié)點的索引一致, 即為重復的數字
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指向它的下下一個節(jié)點
image
此題可利用兩次正向遍歷鏈表, 或者一次正向遍歷的同時記錄前節(jié)點, 然后再反向遍歷
題目的進階要求只使用一趟掃描, 利用快慢指針可實現
創(chuàng)建虛擬頭節(jié)點, 讓快指針??向前移動N + 1個節(jié)點, 然后兩個指針以同樣的速度直至快指針??移動至尾結點, 此時慢指針??移動到的位置即為被刪除的指針前面的一個指針
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
}
};
- 快慢指針
- 慢指針??依次訪問下一個節(jié)點, 并翻轉鏈表
- 快指針??依次訪問下下一個節(jié)點, 直到快指針??沒有下一個節(jié)點(奇數鏈表)或者下下一個節(jié)點(偶數鏈表), 此時已完成了前半截鏈表的翻轉
- 依次比較前半截鏈表和后半截鏈表節(jié)點的值
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
// 找到中間節(jié)點, 并翻轉前半截鏈表,
// 讓_head指向翻轉后的前半截鏈表的頭部,
// 讓slow指向后半截鏈表的頭節(jié)點
while (fastPointer && fastPointer.next) {
_head = slowPointer
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
_head.next = temp
temp = _head
}
// 奇數鏈表跳過最中間的節(jié)點
if (fastPointer) {
slowPointer = slowPointer.next
}
while (_head) {
if (_head.val !== slowPointer.val) {
return false
}
_head = _head.next
slowPointer = slowPointer.next
}
return true
}
};
快樂數
image
- 循環(huán)并緩存每次獲取位的平方和, 如果已緩存過, 就退出循環(huán), 判斷退出循環(huán)后是否為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這個數, 對其反復的求每位的平方和會進入循環(huán), 而且進入循環(huán)時其值不為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
}
總結
利用快慢指針創(chuàng)造的差值, 可節(jié)省內存空間, 減少計算次數, 常用于鏈表數據結構和判斷循環(huán)
快慢指針, 一對快樂的指針, just be happy!
image
