讨论/《算法面试题汇总》 - 反转字符串/
《算法面试题汇总》 - 反转字符串
共 6 个回复

1,双指针

使用两个指针,一个从第一个开始,一个从数组的最后一个开始,两两交换,可以看下视频演示

两个数字交换的时候,最常见的就是使用一个临时变量temp,除了这种以外还有其他实现方式,具体可以看下《交换两个数字的值》,下面的4种交换两个数字的实现方式都是可以的

    public void reverseString(char[] s) {
        int length = s.length;
        //两个指针一个从第1个,一个从最后一个开始,
        //两两交换
        int left = 0;
        int right = length - 1;
        while (left < right) {
            swap(s, left++, right--);
        }
    }

    private void swap(char[] array, int i, int j) {
        //第1种交换方式
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        //第2种交换方式
//        array[i] = (char) (array[i] + array[j]);
//        array[j] = (char) (array[i] - array[j]);
//        array[i] = (char) (array[i] - array[j]);

        //第3种交换方式
//        array[i] = (char) (array[i] - array[j]);
//        array[j] = (char) (array[i] + array[j]);
//        array[i] = (char) (array[j] - array[i]);

        //第4种交换方式
//        array[i] ^= array[j];
//        array[j] ^= array[i];
//        array[i] ^= array[j];
    }

来看一下运行结果
image.png


2,递归方式解决

上面的代码,我们还可以把它改为递归方式实现

    public void reverseString(char[] s) {
        if (s == null || s.length == 0)
            return;
        reverseStringHelper(s, 0, s.length - 1);
    }

    public void reverseStringHelper(char[] s, int left, int right) {
        if (left >= right)
            return;
        swap(s, left, right);
        reverseStringHelper(s, ++left, --right);
    }

    private void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


我们还可以换种写法,先递归在交换

    public void reverseString(char[] s) {
        if (s == null || s.length == 0)
            return;
        reverseStringHelper(s, 0, s.length - 1);
    }

    public void reverseStringHelper(char[] s, int left, int right) {
        if (left >= right)
            return;
        //注意,这里的顺序调换了
        reverseStringHelper(s, left + 1, right - 1);
        swap(s, left, right);
    }

    private void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

1

换到中间是反序,全换一遍是正序。

  • 双指针一个从前开始,一个从后开始选中元素
  • 利用 ES6 解构赋值交换双方数据
  • 到达数组中心时停止交换输出
var reverseString = function (arr) {
  var len = arr.length;
  for (let index = 0; index < len; index++) {
    let flag = Math.floor(len / 2);
    let lastParams = len - 1 - index;
    if (index < flag)
      [arr[index], arr[lastParams]] = [arr[lastParams], arr[index]];
    else break;
  }
  return arr;
};

go语言,双指针

func reverseString(s []byte)  {
    left,right:=0,len(s)-1
    for left<right {
        s[left],s[right] = s[right],s[left]
        left++
        right--
    }
}

为什么我在本地IDE运行是反序输出,但在力扣上变成正序输出了,请路过的人指点

class Solution {
    public char[] reverseString(char[] s) {
        char[] result = new char[s.length];
        for( int index = s.length -1 ; index >= 0 ; index--){
            result[s.length -1 - index] = s[index]; 
        }
        return result;
    }
}
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l = len(s)
        for i in range(int(l/2)):
            tmpChar = s[i]
            s[i] = s[-i-1]
            s[-i-1] = tmpChar