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

[FrankKai]

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

[FrankKai]

什么是对撞指针？

初识

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

算法图

对撞过程图

167.两数之II-输入有序数组（easy）的对撞过程图。 蓝色指针：头指针 红色指针：尾指针 终止条件：头尾指针对撞

[FrankKai]

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

[FrankKai]

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/problems/reverse-integer/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/7.Reverse_Integer.js

  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/problems/palindrome-number/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/9.Palindrome_Number.js

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/problems/remove-element/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/27.Remove_Element.js

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/problems/valid-palindrome/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/125.Valid_Palindrome.js

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/problems/two-sum-ii-input-array-is-sorted/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/167.Two_Sum_II-Input_array_is_sorted.js

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/problems/reverse-bits/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/190.Reverse_Bits.js

/**
 * @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/problems/reverse-string/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/344.Reverse_String.js

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/problems/reverse-vowels-of-a-string/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/345.Reverse_Vowels_of_a_String.js

/**
 * @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/problems/container-with-most-water/ 题解：https://github.com/FrankKai/leetcode-js/blob/master/11.Container_With_Most_Water.js

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;
};