算法：双指针之对撞指针

对撞指针.png

  • 什么是对撞指针？

    • 初识

    • 算法图

    • 对撞过程图

  • JavaScript中的Array与对撞指针

    • 在js中，如何定义对撞指针？

    • 实现一个最简对撞指针

  • leetcode 对撞指针 解法题目

    • 7.整数反转（easy）

    • 9.回文数（easy）

    • 27.移除元素（easy）

    • 125.验证回文串（easy）

    • 167.两数之II-输入有序数组（easy）

    • 190.颠倒二进制位（easy）

    • 344.反转字符串（easy）

    • 345.反转字符串中的元音字母（easy）

    • 11.盛水最多的容器（medium）

什么是对撞指针？

初识

  • 对撞指针是双指针算法之一。

  • 对撞指针从两端向中间迭代数组。一个指针从始端开始，另一个从末端开始。

  • 对撞指针的终止条件是两个指针相遇。

  • 对撞指针常用于排序数组。

算法图

image

对撞过程图

167.两数之II-输入有序数组（easy）的对撞过程图。

蓝色指针：头指针 红色指针：尾指针 终止条件：头尾指针对撞

JavaScript中的Array与对撞指针

在js中，如何定义对撞指针？

命名

头尾指针的命名可以为：

  • i, j

  • head, tail

  • start, end

初始值

  • 头指针：0

  • 尾指针：数组长度减一

let arr = [1, 7, 5, 2];
let head = 0;
let tail = arr.length -1;

实现一个最简对撞指针

image

var arr = new Array(10).fill(0).map((num,i)=>num+i);
var i =0;
var j = arr.length - 1;
while(i<j){
i++;
j--;
}
var collision = [i - 1, j + 1]
var tip = `Array's head and tail had a collision between ${collision[0]} and ${collision[1]}`;
console.log(tip); // Array's head and tail had a collision between 4 and 5

leetcode 对撞指针 解法题目

  • 7.整数反转（easy）

  • 9.回文数（easy）

  • 27.移除元素（easy）

  • 125.验证回文串（easy）

  • 167.两数之II-输入有序数组（easy）

  • 190.颠倒二进制位（easy）

  • 344.反转字符串（easy）

  • 345.反转字符串中的元音字母（easy）

  • 11.盛水最多的容器（medium）

7.整数反转（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var reverse = function (x) {
/**
* 解法2.指针对撞法
* 性能：96 ms 35.38% 35.9 MB 77.35%
*/
var sign = Math.sign(x);
var arr = x.toString().split("");
//
if (sign === -1) {
arr.shift();
}
// 指针对撞开始
var i = 0;
var j = arr.length - 1;
while (i < j) {
swap(arr, i, j);
i++;
j--;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 指针对撞结束
var rX = parseInt(arr.join(""));
var result = sign * rX;
var min = -Math.pow(2, 31);
var max = Math.pow(2, 31) - 1;
if (rX < min || rX > max) return 0;
return result;
};

9.回文数（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var isPalindrome = function (x) {
/**
* 解法3：对撞指针法
* 性能：244ms 45.5MB
*/
var strArr = `${x}`.split("");
var i = 0;
var j = strArr.length - 1;
while (i < j) {
if (strArr[i] !== strArr[j]) {
return false;
}
i++;
j--;
}
return true;
};

27.移除元素（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var removeElement = function (nums, val) {
/**
* 解法2：对撞指针
* 性能：64ms 33.9MB
*/
var i = 0;
var j = nums.length - 1;
while (i <= j) {
if (nums[i] === val) {
nums.splice(i, 1);
j--;
} else if (nums[j] === val) {
nums.splice(j, 1);
j--;
} else {
i++;
}
}
return nums.length;
};

125.验证回文串（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var isPalindrome = function (s) {
/**
* 解法1：正则 + 对撞指针
* 性能：76ms 89.76% 37.5MB 70.83%
*/
var parlinDrome = s.replace(/[^w]/g, "").replace(/_/g, "").toLowerCase();
var strArr = parlinDrome.split("");
var i = 0;
var j = strArr.length - 1;
while (i < j) {
if (strArr[i] !== strArr[j]) {
return false;
}
i++;
j--;
}
return true;
};

167.两数之II-输入有序数组（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var twoSum = function (numbers, target) {
/**
* 解法2：对撞指针
* 性能：68ms 71.18% 35.2MB 76.60%
* 时间复杂度：O(n^2)
*/
var left = 0;
var right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] === target) {
return [left + 1, right + 1];
} else if (numbers[left] + numbers[right] > target) {
right--;
} else {
left++;
}
}
};

190.颠倒二进制位（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

/**
* @param {number} n - a positive integer
* @return {number} - a positive integer
*/
var reverseBits = function (n) {
/**
* 解法1：转数组后对撞交换位置
* 性能：76ms 35.8MB
* 思路：
* 十进制转二进制：toString(2)
* 32位空位补0：padStart(32,0)
* 反转算法：对撞指针法
* 二进制转十进制：parseInt(,2)
*/
let arr = n.toString(2).padStart(32, 0).split("");
let head = 0;
let tail = arr.length - 1;
while (head < tail) {
swap(arr, head, tail);
head++;
tail--;
}
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
let result = parseInt(arr.join(""), 2);
return result;
};

344.反转字符串（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var reverseString = function (s) {
/**
* 解法2：对撞指针
*/
var headIdx = 0;
var tailIdx = s.length - 1;
while (headIdx < tailIdx) {
swap(s, headIdx, tailIdx);
headIdx++;
tailIdx--;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return s;
};

345.反转字符串中的元音字母（easy）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

/**
* @param {string} s
* @return {string}
*/
var reverseVowels = function (s) {
/**
* 解法1：对撞指针
* 性能：108 ms 31.59% 38.4 MB 66.67%
*/
var univocalic = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"];
var sArr = s.split("");
var head = 0;
var tail = sArr.length - 1;
while (head < tail) {
if (univocalic.includes(sArr[head]) && univocalic.includes(sArr[tail])) {
swap(sArr, head, tail);
head++;
tail--;
} else if (!univocalic.includes(sArr[head])) {
head++;
} else if (!univocalic.includes(sArr[tail])) {
tail--;
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return sArr.join("");
};

11.盛水最多的容器（medium）

题目：https://leetcode-cn.com/probl...

题解：https://github.com/FrankKai/l...

var maxArea = function (height) {
/**
* 解法1：对撞指针法
* 性能：64ms 35.6MB
* */
var head = 0;
var tail = height.length - 1;
var maxCapacity = 0;
while (head < tail) {
maxCapacity = Math.max(Math.min(height[head], height[tail]) * (tail - head), maxCapacity)
if (height[head] < height[tail]) {
head++
} else {
tail--;
}
}
return maxCapacity;
};

以上是 算法：双指针之对撞指针 的全部内容， 来源链接： utcz.com/a/21030.html

回到顶部