发现算法之美-双指针之对撞指针

微信扫一扫,分享到朋友圈

发现算法之美-双指针之对撞指针
  • 什么是对撞指针
    • 初识
    • 算法
    • 对撞过程图
  • JavaScript中的Array与对撞指针
    • 在js中,如何定义对撞指针?
    • 实现一个最简对撞指针
  • leetcode 对撞指针 解法题目
    • 7.整数反转(easy)
    • 9.回文数(easy)
    • 27.移除元素(easy)
    • 125.验证回文串(easy)
    • 167.两数之II-输入有序数组(easy)
    • 190.颠倒二进制位(easy)
    • 344.反转字符串(easy)
    • 345.反转字符串中的元音字母(easy)
    • 11.盛水最多的容器(medium)

什么是对撞指针?

初识

  • 对撞指针是双指针算法之一。
  • 对撞指针从两端向中间迭代数组。一个指针从始端开始,另一个从末端开始。
  • 对撞指针的终止条件是两个指针相遇。
  • 对撞指针常用于排序数组。

算法图

对撞过程图

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;
复制代码

实现一个最简对撞指针

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)

题目: leetcode-cn.com/problems/re… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/pa… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/re… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/va… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/tw… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/re… 题解: github.com/FrankKai/le…

/**
* @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)

题目: leetcode-cn.com/problems/re… 题解: github.com/FrankKai/le…

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)

题目: leetcode-cn.com/problems/re… 题解: github.com/FrankKai/le…

/**
* @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)

题目: leetcode-cn.com/problems/co… 题解: github.com/FrankKai/le…

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;
};
复制代码

期待和大家交流,共同进步,欢迎大家加入我创建的与前端开发密切相关的技术讨论小组:

努力成为优秀前端工程师!

新iPhone发布将延迟 苹果iPhone12配置、准确发布日期介绍

上一篇

💫 CSS 幻术 | 抗锯齿

下一篇

你也可能喜欢

发现算法之美-双指针之对撞指针

长按储存图像,分享给朋友