刷題常用技巧(二)-雙指針方法

前言

雙指針的技巧是我在刷題時覺得”So brilliant!”的方法,可以有效的將時間複雜度降低,而且在刷題上即便不是在考雙指針的用法,也常常可以套用雙指針的邏輯去思考,那就讓我們來看看這個方法吧!

原理

我認為簡單來說可以看成

  1. 同步,兩個指針一開始指向同個地方,但是變動的速度不同,如一個動的快,一個動的慢,也可以稱為快慢指針。(287. Find the Duplicate Number (M))
  2. 不同步,兩個指針指向同一個地方,但因為條件成立的與否,決定某一指針是否需要動。(80. Remove Duplicates from Sorted Array II(M))

應用

1. 反轉字串

反轉字串就是第一種設計邏輯很好的例子,可以先將字串轉成字元陣列,利用一個指標指向陣列頭部,一個指標指向陣列尾部,兩兩進行交換後,再個別往內縮一格即可完成字串反轉!

var reverseString = function(s) {
if (s.length <= 1) return s
//偶數
if ((s.length & 1) === 0 ) {
let l = s.length / 2 - 1
let r = s.length / 2
while( l >= 0 ) {
[s[l], s[r]] = [s[r], s[l]]
l--
r++
}
//奇數
}else {
let l = Math.floor(s.length / 2) - 1
let r = Math.floor(s.length / 2) + 1
while( l >= 0 ) {
[s[l], s[r]] = [s[r], s[l]]
l--
r++
}
}
}

2. 找到重複的值

這題因為題目有range [1, n]的特殊性,所以可以利用快慢指標來解,當初研究快慢指標的時候覺得這方法很酷。利用龜兔賽跑的概念,兔子的速度是烏龜的兩倍,若兩人能相遇代表有圈(有重複的值),而相遇時,兔子走過的距離是烏龜的兩倍,如下圖

var findDuplicate = function(nums) {
// p1走一步 p2走兩步
let p1 = nums[0]
let p2 = nums[nums[0]]
//當p1與p2不相等 繼續走
while (p1 ^ p2) {
p1 = nums[p1]; p2 = nums[nums[p2]]
}
//相遇時 讓p1退回起點 此時相距環的整數倍 直到再次相遇即為起點
p1 = 0
while (p1 ^ p2) {
p1= nums[p1]; p2=nums[p2]
}
return p1
}

3. 去除重複的值

讓兩指標指向同個位子,但是可以利用條件判斷來讓指標決定變動與否,如下面這個例子,利用指標1當作”寫”指標,指標2當作”讀”指標,讓指標2去遍歷整個陣列,只要讀到與指標1前兩個位置(pointer1 - 2)的值不同,則將指標2讀到的值寫入指標1的位置,同時指標1再往下一格移動,如此一來就能確保重複的數只會出現兩次。需要注意的是,這題的陣列要先排序過。

var removeDuplicates = function(nums) {
let pointer1 = 2
for (let pointer2 = 2; pointer2 < nums.length; pointer2++) {
if (nums[pointer1 - 2] !== nums[pointer2]) {
nums[pointer1] = nums[pointer2]
pointer1++
}
}
//題目要求回傳陣列長度,因pointer1指的是位置,指向最後一位時實際上就是所求陣列長度
return pointer1
};

1992, 學習科技|研究投資|環境工程技師|成功大學環境工程學系|台灣大學環境工程研究所|水處理行業工作兩年半|想要用科技打造自己的企業,過自己想過的生活。

1992, 學習科技|研究投資|環境工程技師|成功大學環境工程學系|台灣大學環境工程研究所|水處理行業工作兩年半|想要用科技打造自己的企業,過自己想過的生活。