likes
comments
collection
share

力扣之反转字符串之原地修改输入数组（双指针方式）

作者站长头像
站长
· 阅读数 17

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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解构赋值交换位置，虽然速度慢了一点点，但是内存省下来一些了
  • 这不是重点，重点是双指针的方式