美文网首页
算法@LeetCode:Reverse String

算法@LeetCode:Reverse String

作者: 苏尚君 | 来源:发表于2017-08-08 21:38 被阅读77次

    Log

    • 【170808】完成 01 版 Python 提交
    • 【170808】完成 02 版 Python 提交
    • 【170808】完成 03 版 Python 提交
    • 【170808】查看最优解法(Python)并自行实现了一遍

    题目

    Reverse String

    【题目类型备注】

    双指针,字符串

    提交

    01

    【语言】

    Python

    【时间】

    170808

    【思路】

    本次提交前,没有查看 Related Topics,仅仅是通过搜索 String 而找到的。我本次提交的两种代码版本思路是一致的:读取字符串每一位,从头读到尾,每读取一位就保存一位,最后反向输出即可。区别在于:通过的代码通过了一个「栈」+字符串 join 方法来实现,并且是先读取,保存,最后连接而实现,试验若干次,从未超时 TLE;没通过的代码则是每读取一个就反向连接一次,结果尝试了若干次,都超时 TLE。超时代码如下:

    class Solution(object):
        def reverseString(self, s):
            """
            :type s: str
            :rtype: str
            """
            ans = ""
            maxlen = len(s)
            if maxlen <= 1:
                return s
            
            for i in range(maxlen-1, -1, -1):
                ans += s[i]
            
            return ans
    

    【代码】

    class Solution(object):
        def reverseString(self, s):
            """
            :type s: str
            :rtype: str
            """
            stk = []
            for i in s:
                stk.append(i)
     
            ans = []
            while(len(stk) > 0):
                ans.append(stk.pop())
     
            return ''.join(ans)
    

    【结果】

    运行时:85 ms

    报告链接:https://leetcode.com/submissions/detail/113009678/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 5.23 % of python submissions.

    02

    【语言】

    Python

    【时间】

    170808

    【思路】

    看到了双指针,我联想到了快排,然后就想到了递归。于是写了一个递归版本。当然试验显示,递归版本更慢点。

    【代码】

    class Solution(object):
        def reverseString(self, s):
            """
            :type s: str
            :rtype: str
            """
            if len(s) in [0, 1]:
                return s
            if len(s) == 2:
                return s[-1]+s[0]
            if len(s) >= 3:
                mid = len(s)//2
                return self.reverseString(s[(mid+1):]) + s[mid] + self.reverseString(s[:mid])
    

    【结果】

    运行时:105 ms

    报告链接:https://leetcode.com/submissions/detail/113011390/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 3.36 % of python submissions.

    03

    【语言】

    Python

    【时间】

    170808

    【思路】

    想到 Python 里好像有一个函数能把字符串转为字符数组,查了一下果然有:直接 list(str) 即可。然后我又记得列表有一个 .reverse() 方法,于是就改写了这个代码。一改,经过多次测试,发现速度好快……

    【代码】

    class Solution(object):
        def reverseString(self, s):
            """
            :type s: str
            :rtype: str
            """
            if len(s) >= 1:
                rev = list(s)
                rev.reverse()
                return ''.join(rev)
            else:
                return s
    

    【结果】

    运行时:42 ms

    报告链接:https://leetcode.com/submissions/detail/113013390/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 65.99 % of python submissions.

    00

    参考解法:

    • Python
      • 其中 Pythonic 的写法用了 Extended Slices。剩下的两种解法中,递归的自己实现过;而双指针的写法,有想到,但以为这样的复杂度估计也是 O(n) 级别的,剩了常数倍(一半)的时间,感觉可能还有更快的解法,就没写。扫视了 Java 和 C++ 的推荐答案后,都没有发现更优的解法。或许就是用这种方法吧。

    自己实现一遍最优解:

    相关文章

      网友评论

          本文标题:算法@LeetCode:Reverse String

          本文链接:https://www.haomeiwen.com/subject/csjxrxtx.html