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

前言

原理

應用

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. 找到重複的值

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. 去除重複的值

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