我正在从leetcode的特色教程Recursion I中学习递归基础知识
第一个练习是反转字符串Reverse String - LeetCode
编写一个反转字符串的函数。输入字符串以字符数组
char[]
的形式给出。
不要为另一个数组分配额外的空间,您必须通过使用O(1)额外内存就地修改输入数组来实现这一点。
您可以假设所有字符都由printable ascii characters组成。
示例1:
输入:"h","e","l","l","o“输出:"o","l","l","e","h”
示例2:
输入:"H","a","n","n","a","h“输出:"h","a","n","a","H”
公认的解决方案是
class Solution:
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
#base case
if len(s) <= 1:
return s
#recur case
elif len(s) >= 2:
n=len(s)
return self.reverseString(s[n//2:])+self.reverseString(s[:n//2])
解决方案有两个问题:
1,不就地修改
2,递归切分字符串的开销很大。
作为改进的第一步,引入了参数lo
和hi
来存储索引
class Solution:
def reverseString(self, s, lo=0, hi=None):
"""
:type s: str
:rtype: None
"""
if hi == None:
hi = len(s)
#base case
if hi <= 1:
return s
#recur case
elif hi >= 2:
mid = hi // 2
left = self.reverseString(s, lo, mid)
right = self.reverseString(s, mid, hi)
return left + right
It报告错误
RecursionError:在比较中超出了最大递归深度
在0.005s内运行了1个测试
有什么问题吗?
发布于 2019-04-17 08:12:10
要在没有空间的情况下执行此操作,您需要交换空间。不能添加数组切片。而不是在中间拆分索引,这永远不会让您交换相反的对(在基本情况下是这样)。
如果你在视觉上想象一下递归,你可以看到它。您可以从如下列表开始:
1, 2, 3, 4
^ ^ <-- these need to swap in a reverse
但是在您的第一个递归调用之后,您将其拆分为:
---- | ----
1, 2 3, 4
^ ^ <-- these still need to be swapped, bu when?
现在分支1没有办法在分支2中的4处进行交换,除非在递归展开时有一种不明显的方法。
相反,您可以(更容易地)从两端遍历索引,并在执行过程中交换索引。那么你的基本情况就是当它们在中间相遇的时候:
class Solution:
def reverseString(self, s, lo=0, hi=None):
if hi == None:
hi = len(s) - 1
if hi <= lo:
return s
s[lo], s[hi] = s[hi], s[lo]
return self.reverseString(s, lo + 1, hi - 1)
s = Solution()
s.reverseString([1, 2, 3, 4])
# [4, 3, 2, 1]
s.reverseString([1, 2, 3, 4, 5])
#[5, 4, 3, 2, 1]
发布于 2019-04-17 07:45:21
我不确定你为什么要做递归。您可以简单地获取两个指针,一个在字符串的开头,另一个在字符串的结尾,首先交换这些字符,然后将指针相互移动,直到它们交叉,然后断开并返回相反的字符串。
class Solution:
def reverseString(self, s):
if len(s) <= 1: return s
# The two pointers
lo = 0
hi = len(s) - 1
# Iterate till both pointers cross
while lo < hi:
# swap the characters
tmp = s[lo]
s[lo] = s[hi]
s[hi] = tmp
# increment the pointers
lo += 1
hi -= 1
return s
s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
#['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']
此外,同样的递归方法如下所示
class Solution:
def reverseString(self, s, lo=0, hi=None):
#If one character or less in the string, return the string
if len(s) <= 1:
return s
#The last index should be placed at the end of the string
if hi == None:
hi = len(s) - 1
#If the two indexes cross, return the string
if hi < lo:
return s
#swap the low and high characters
tmp = s[lo]
s[lo] = s[hi]
s[hi] = tmp
#Recursively call the function
return self.reverseString(s, lo + 1, hi - 1)
s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']
发布于 2019-05-28 13:58:43
下面是这个问题的解决方案:
class Solution(object):
def reverseString(self, s, left=0, right=0):
if right == 0:
right = len(s) - 1
if left >= right:
return
temp = s[right]
s[right] = s[left]
s[left] = temp
self.reverseString(s, left+1, right -1)
https://stackoverflow.com/questions/55717930
复制相似问题