乐趣区

关于leetcode:力扣之反转字符串之原地修改输入数组双指针方式

题目形容

编写一个函数,其作用是将输出的字符串反转过去。输出字符串以字符数组 s 的模式给出。

不要给另外的数组调配额定的空间,你必须 原地 批改输出数组、应用 O(1) 的额定空间解决这一问题。

示例 1:

输出:s = ["h","e","l","l","o"]
输入:["o","l","l","e","h"]

示例 2:

输出:s = ["H","a","n","n","a","h"]
输入:["h","a","n","n","a","H"]

提醒:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

力扣原题目地址:https://leetcode.cn/problems/…

思路解法

剖析

大多数人,看到这个题目当前,心想:呵!间接调用数组的 reverse()办法不就行啦。其实这确实是一种解决方案。只不过题目要求:原地 批改输出数组、应用 O(1)  的额定空间。也就是说,要尽可能应用较小的内存去操作,这也是性能优化的一种尝试。

咱们想一下,其实数组的 reverse()办法的最终成果是,反转一个数组,如:

let arr = [1,2,3,4,5]
console.log(arr); // [1,2,3,4,5]
console.log(arr.reverse()); // [5,4,3,2,1]

咱们发现,反转当前的数组只不过是 首尾对应地位颠倒了 罢了,换句话说,就是 地位替换,地位替换,地位替换

那么,一说到 数组的地位替换,咱们会想到哪几种形式呢?

1. 应用长期变量替换, 如下:

let arr = ['甲', '乙']
let temp;
temp = arr[0]
arr[0] = arr[1]
arr[1] = temp
console.log(arr); // ['乙','甲']

冒泡排序的感觉 …

2. 应用 ES6 的解构赋值进行操作, 如下:

let arr = ['甲', '乙']
arr = ([arr[0], arr[1]] = [arr[1], arr[0]]); // 即:arr = [arr[0], arr[1]] = [arr[1], arr[0]]
console.log(arr); // ['乙', '甲']

通过上述形式,咱们发现,既然是替换对应地位的两个元素,那么只有这两个元素的索引咱们通晓即可。在心中默念,两个元素的索引、两个元素的索引、两个 …

哎,有了,双指针啊!

双指针形式

  • 咱们定义两个变量,left 和 right,别离来示意对应的、须要替换地位的元素的、索引。
  • 而后一开始 left 值是 0,right 的值是 arr.length-1。即为要替换第一个和最初一个地位的值。
  • 通过上文中替换数组地位的形式替换结束当前,阐明第一个和最初一个曾经替换实现了
  • 而后就替换第二个,和倒数第二个
  • 而后持续替换第三个,和倒数第三个
  • 即为 left 递增,right 递加
  • 然而替换总有停下来的时候(完结条件)
  • 当 left 等于 right 时(奇数项数组)或者 left 大于 right 时(偶数项数组)就不再持续替换了
  • 也就是说,只有不满足完结条件,我就持续替换地位操作
  • 换句话说,只有处在条件内,我就继续执行操作
  • 只有合乎 xxx 条件,就继续执行操作(直到不符合条件时停下来不操作了),咱们想到了 while 循环

奇数项数组两头位的那一项不必动,偶数项是全副两两替换一下

代码(长期变量替换)

var reverseString = function (s) {
        let left = 0 // 左侧指针初始值为 0,示意从第一项开始
        let right = s.length - 1 // 右侧指针初始值为 length-1,示意从最初一项开始
        while (left <= right) { // 当左侧的指针小于右侧指针时,阐明还没有替换结束
                // 应用长期变量替换地位
                let temp
                temp = s[left]
                s[left] = s[right]
                s[right] = temp
                // 替换结束当前左侧指针递增,右侧指针递加
                left = left + 1
                right = right - 1
        }
        return s
};

代码(ES6 解构替换)

var reverseString = function (s) {
    let left = 0 // 左侧指针初始值为 0,示意从第一项开始
    let right = s.length - 1 // 右侧指针初始值为 length-1,示意从最初一项开始
    while (left <= right) { // 当左侧的指针小于右侧指针时,阐明还没有替换结束
        // 应用 ES6 解构替换地位
        [s[left], s[right]] = [s[right], s[left]]
        // 替换结束当前左侧指针递增,右侧指针递加
        left = left + 1
        right = right - 1
    }
    return s
};

提交 LeetCode 后果图

  • 应用 temp 长期变量,速度更快,然而内存多消耗了一些
  • 应用 ES6 解构赋值替换地位,尽管速度慢了一点点,然而内存省下来一些了
  • 这不是重点,重点是双指针的形式
退出移动版