怎么用递归解决《344. 反转字符串》 – Becomin' Charles跳至内容

Mac | Linux | 团队管理 | 架构

03/16 401. 二进制手表 (1148 views)
03/17 怎么推导出《115. 不同的子序列》的动态规划解法 (1089 views)
03/10 1178. 猜字谜 (1073 views)
03/08 Git 文章集锦 (1069 views)
03/04 354. 俄罗斯套娃信封问题 (886 views)
03/27 338.比特位计数 (849 views)
04/20 1006. 笨阶乘 (737 views)
03/15 54. 螺旋矩阵 & 59. 螺旋矩阵 II (705 views)

Charles : Sorry, 我测试了一下，有个语法特性在 PHP 7.0 下不支持，更新到 2.0.7 可以修复。...
大盛 : 你好，我启用后报错，怎么解决啊，我的WP版本是5.6.1，PHP版本是7.0

Parse er...
Wang : 现在大部分大学老师在照本宣科，学生在应付考试，计算机专业在大学毕业前没打开过GitHub大有人在。自...
Charles : 我上面插图里，有我家里门禁室内机的电路板。电路板正面右上角，有一个开关，那个就是开锁按钮，可以看到就...
求教 : 您好，最近在研究类似方案，刚刚好搜到你的文章。虽然没有看到介绍，但是我看文章的情况，貌似您的门禁室内...

1,240,240条垃圾评论已被Akismet阻挡

怎么用递归解决《344. 反转字符串》

这个题目太简单了，我就不贴题目的原文了。意思是这样的，给你一个字符数组（字符串），然后，你要原地把这个数组的元素顺序反转。这道题目是非常平凡的，常规解法是使用双指针，头尾指针向中间夹逼，交换头尾指针指向的字符。

class Solution:

def reverseString(self, s: List[str]) -> None:

l, r = 0, len(s) - 1

while l < r:

s[l], s[r] = s[r], s[l]

class Solution:
    def reverseString(self, s: List[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -=

用 Python 写，会非常短小。时间复杂度是 O(n)，空间复杂度是 O(1)。

假如，让你为这个题目设计一个递归算法，你会怎么写呢？

方案一：假设我们掌握了一个把下标 [i, j] 范围内的字符顺序反转的方法。

那么对于这个题目来说，我们只要交换头尾两个字符，然后，用递归方法去计算中间剩余部分即可。

class Solution:

def reverseString(self, s: List[str]) -> None:

def reverse(i: int, j: int) -> None:

if i < j:

s[i], s[j] = s[j], s[i]

reverse(i + 1, j - 1)

reverse(0, len(s) - 1

class Solution:
    def reverseString(self, s: List[str]) -> None:
        def reverse(i: int, j: int) -> None:
            if i < j:
                s[i], s[j] = s[j], s[i]
                reverse(i + 1, j - 1)
        reverse(0, len(s) - 1

这个方法和上面双指针其实如出一辙。

方案二：深度优先搜索，从当前位置探索最后一个字符，找到后，把最后一个字符放到正确位置，然后回溯。

class Solution:

def reverseString(self, s: List[str]) -> None:

n = len(s)

def dfs(i: int):

if i == n:

return

c = s[i]

dfs(i + 1)

s[n - 1 - i] = c

dfs(0

class Solution:
    def reverseString(self, s: List[str]) -> None:
        n = len(s)
        def dfs(i: int):
            if i == n:
                return
            c = s[i]
            dfs(i + 1)
            s[n - 1 - i] = c
        dfs(0

这里很有意思的一点，就是这个变量 c 可不可以不要？为什么？

你还能想出其他的递归设计方法么？欢迎给我留言。

发布于 2021/04/26作者 Charles分类算　　法标签 algorithm、double pointer、recursion

发表评论取消回复

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

显示名称 *

电子邮箱地址 *

网站网址

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。

上一篇上篇文章： 377. 组合总和 IV

自豪地采用WordPress

怎么用递归解决《344. 反转字符串》

怎么用递归解决《344. 反转字符串》

发表评论取消回复

Recommend

This Week in Rust 344

递归反转链表的一部分

【算法】反转字符串

LeetCode 第 344 号问题：反转字符串

Rocket #344: Viral News - Relay FM

LeetCode-344-反转字符串

FreeCodeSession - Episode 344

344: Spinner Armageddon

递归魔法：反转单链表

golang 递归判断回文字符串

About Joyk

怎么用递归解决《344. 反转字符串》

怎么用递归解决《344. 反转字符串》

发表评论 取消回复

Recommend

About Joyk

发表评论取消回复