关注Java领域相关技术 记录有趣的事情

LeetCode-344. 反转字符串

US-B.Ralph
US-B.Ralph
2020-10-08

问题地址

LeetCode每日一题/2020-10-08

LeetCode344. 反转字符串


问题描述

规则

  • 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
  • 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
  • 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例

  • 示例1
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
  • 示例2
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

解析

解题思路

  • 采用双指针
    • 一个记录 当前元素的下标;
    • 一个记录 当前元素对应的反转元素的下标;
    • 给定数组,故数组的长度已知,所以 inx2(对应反转元素的下标) = len – 1 – inx1(当前元素下标);

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0334_ReverseString {
    public void reverseString(char[] s) {
        if (s.length < 2) return;
        int len = s.length;
        int cycleTimes = len / 2;
        for (int i = 0; i < cycleTimes; i++) {
            char tmp = s[i];
            s[i] = s[len - 1 - i];
            s[len - 1 - i] = tmp;
        }
    }
}

JDK java.lang.AbstractStringBuilder 字符反转的实现方式

    public AbstractStringBuilder reverse() {
        boolean hasSurrogates = false;
        int n = count - 1;
        for (int j = (n-1) >> 1; j >= 0; j--) {
            int k = n - j;
            char cj = value[j];
            char ck = value[k];
            value[j] = ck;
            value[k] = cj;
            if (Character.isSurrogate(cj) ||
                Character.isSurrogate(ck)) {
                hasSurrogates = true;
            }
        }
        if (hasSurrogates) {
            reverseAllValidSurrogatePairs();
        }
        return this;
    }

官方解法

方法一:双指针

思路与算法:

  • 对于长度为 N 的待被反转的字符数组,我们可以观察反转前后下标的变化,假设反转前字符数组为 s[0] s[1] s[2] … s[N – 1],那么反转后字符数组为 s[N – 1] s[N – 2] … s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N – 1 – i] 的字符发生了交换的规律,因此我们可以得出如下双指针的解法:
    • 将 left 指向字符数组首元素,right 指向字符数组尾元素。
    • 当 left = right,反转结束,返回字符数组即可。

复杂度分析:

  1. 时间复杂度:O(N),其中 N 为字符数组的长度。一共执行了 N/2 次的交换。
  2. 空间复杂度:O(1)。只使用了常数空间来存放若干变量。

编码实现

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}

精彩评论

跳转地址1:344. 反转字符串:【双指针法】详解

解题思路

先说一说题外话:
对于这道题目一些同学直接用C++里的一个库函数 reverse,调一下直接完事了, 相信每一门编程语言都有这样的库函数。
如果这么做题的话,这样大家不会清楚反转字符串的实现原理了。
但是也不是说库函数就不能用,是要分场景的。
如果在现场面试中,我们什么时候使用库函数,什么时候不要用库函数呢?
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。
毕竟面试官一定不是考察你对库函数的熟悉程度, 如果使用python和java 的同学更需要注意这一点,因为python、java提供的库函数十分丰富。
如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。
建议大家平时在leetcode上练习算法的时候本着这样的原则去练习,这样才有助于我们对算法的理解。
不要沉迷于使用库函数一行代码解决题目之类的技巧,不是说这些技巧不好,而是说这些技巧可以用来娱乐一下。
真正自己写的时候,要保证理解可以实现是相应的功能。
接下来再来讲一下如何解决反转字符串的问题。
大家应该还记得,我们已经讲过了206.反转链表
在反转链表中,使用了双指针的方法。
那么反转字符串依然是使用双指针的方法,只不过对于字符串的反转,其实要比链表简单一些。
因为字符串也是一种数组,所以元素在内存中是连续分布,这就决定了反转链表和反转字符串方式上还是有所差异的。
如果对数组和链表原理不清楚的同学,可以看这两篇,关于链表,你该了解这些!必须掌握的数组理论知识
对于字符串,我们定义两个指针(也可以说是索引下表),一个从字符串前面,一个从字符串后面,两个指针同时向中间移动,并交换元素。
以字符串hello为例,过程如下:

不难写出如下C++代码:

void reverseString(vector<char>& s) {
    for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
        swap(s[i],s[j]);
    }
}

循环里只要做交换s[i] 和s[j]操作就可以了,那么我这里使用了swap 这个库函数。大家可以使用。
因为相信大家都知道交换函数如何实现,而且这个库函数仅仅是解题中的一部分, 所以这里使用库函数也是可以的。
swap可以有两种实现。
一种就是常见的交换数值:

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

一种就是通过位运算:

s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

这道题目还是比较简单的,但是我正好可以通过这道题目说一说在刷题的时候,使用库函数的原则。
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。
如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。
本着这样的原则,我没有使用reverse库函数,而使用swap库函数。
在字符串相关的题目中,库函数对大家的诱惑力是非常大的,因为会有各种反转,切割取词之类的操作,这也是为什么字符串的库函数这么丰富的原因。
相信大家本着我所讲述的原则来做字符串相关的题目,在选择库函数的角度上会有所原则,也会有所收获。

编码实现

class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
            swap(s[i],s[j]);
        }
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

8 + 20 =