leetcode-344-Reverse String

chenjx85

发布于 2018-05-21 18:43:27

5010

发布于 2018-05-21 18:43:27

文章被收录于专栏：chenjx85的技术专栏chenjx85的技术专栏

题目描述：

Write a function that takes a string as input and returns the string reversed.

Example: Given s = "hello", return "olleh".

要完成的函数：

string reverseString(string s)

说明：

1、这道题目十分容易，反转字符串。就算不使用c++的内置函数来反转或者来交换字母，我们也可以自己写出来如下代码：

    string reverseString(string s) 
    {
        int i=0,j=s.size()-1;
        char c;
        while(i<j)
        {
            c=s[j];
            s[j]=s[i];
            s[i]=c;
            i++;
            j--;
        }
        return s;
    }

实测10ms，beats 97.83% of cpp submissions。

2、这道题有个坑，就是字符串可能会很长。内存容纳一个很长的字符串没有问题，但是如果定义了一个新的字符串，把读取出来的字母逆序存放在新字符串上面，这样做就会超过memory limit。

也就是这道题有空间复杂度的要求。以后能少用点空间还是少用点吧，直接在原有字符串上处理。

3、分享两种使用c++内置函数的做法，给大家观赏一下。

//方法一，使用reverse函数直接反转
    string reverseString(string s) 
    {
        reverse(s.begin(),s.end());
        return s;
    }

//方法二，使用swap函数交换两个字母
    string reverseString(string s) 
    {
        int i=0;
        int j=s.size()-1;
        while(i<j)
            swap(s[i++],s[j--]);
        return s;
    }

上述两种代码跟1中代码，实测都是10ms，beats 97.83% of cpp submissions。

4、这道题看到有人使用了异或的方法去交换。异或方法如下：

a=a^b

b=a^b

a=a^b

这种做法其实从计算机组成的角度来看，需要读取3次a，读取3次b，异或运算3次，然后写入3次。

而如果使用直接交换的方法，如下：

c=a

a=b

b=c

只需要读取1次a，读取1次b，读取1次c，写入1次c，写入1次a，写入1次b。总共读取3次，写入3次，还不用做运算。比起异或运算，其实会更快。

在leetcode上写了个异或的代码如下：

    string reverseString(string s) 
    {
        int i=0,j=s.size()-1;
        while(i<j)
        {
            s[j]=s[j]^s[i];
            s[i]=s[j]^s[i];
            s[j]=s[j]^s[i];
            i++;
            j--;
        }
        return s;
    }

真的会慢一点……实测12ms，beats 36.69% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-04-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

c++

登录后参与评论

0 条评论

热度