【完虐算法】「字符串-逆序」全复盘

大家好！

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5dd140c7-f5a3-46e7-af9a-bd84bbfdc69d

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:89ec266b-8026-4093-a7b4-1244fd52fbe6

然后后面两节会是字符串中比较硬核的内容，分别是字符串中的动态规划问题和 KMP 算法。

今天先来说逆序！

说在前面

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:a00c8073-359c-4430-9bc3-db4eaf5d7fca

github：https://github.com/xiaozhutec/share_leetcode
文档地址：https://github.com/xiaozhutec/share_leetcode/tree/master/docs
整体架构：

字符串 – 逆序

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e88463d2-dac7-4d61-9b5c-3179b349f750

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:903af8ad-eb09-4c31-a588-e4eb08ec0ac9

比如：”Hannah” 逆序后为 “hannaH”

一般是要在时间复杂度为 O(N)，空间额外复杂度为 O(1)

字符串「逆序」方面的问题（还拿字符串 “Hannah” 逆序后为 “hannaH” 为例）

一般的思路是：

设两个指针 left 和 right 分别指向字符串最左边和最右边，然后指针指向的字符不断交换，直到 left 不小于 right。

下图为例，left 指向字符串最左边，right 指向字符串最右边，进行不断的交换。

再往后，会发现 left < right 的条件不满足，退出执行。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:ac00abeb-5e20-40b5-ab46-65045abb60e9

时间复杂度方面，由于是线性执行，所以是 O(N)；

额外空间复杂度方面，仅仅是在交换的时候会借助一个字符的空间进行交换。所以额外空间复杂度是 O(1)。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:1c426637-eb0e-4e5c-ac3e-d3aefd9b0da9

案例

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6014b579-956d-4cc4-bfa0-14ffbf35e804

下面会通过两个案例进行举例，分别是 LeetCode 的 344 题 和 LeetCode 的 541 题

344.反转字符串【简单】

541.反转字符串【简单】

344.反转字符串【简单】

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6fdfbfa2-4dc8-4d9e-ac9c-b7a90bd98956

分别设定左指针 left 和 右指针 right 分别指向字符串的最左边和最右边。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:d0d43e50-824d-4db5-9757-d7929198f0df

但是每一步需要满足 left < right。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:dd25b511-44fc-424f-9514-67558a32fa13

① left 指向字符 ‘h’， right 指向字符 ‘o’，满足 left < right 进行交换.

② left 指向字符 ‘e’， right 指向字符 ‘l’，满足 left < right 进行交换.

② left 指向字符 ‘l’， right 指向字符 ‘l’，❗️不满足 left < right ，所以就不进行交换，退出程序。

这个题目只要注意 left < right这个细节点就可以了。

而且实现起来也比较简单

咱们直接用 Python 来解决：

def reverseString(self, s):
    size = len(s)
    left, right = 0, size-1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    return s

这个题目解决了。

咱们看下一个！

541.反转字符串【简单】

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

输入：s = "abcdefg", k = 2
输出："bacdfeg"

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:69748742-e993-4ff9-a657-eb81d82967a7

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:6b371c19-62e4-490b-904d-c0d0c36804b4

所以，在问题解决的时候，是需要根据 k 值判断要逆序的位置。

在遍历字符串时候，每次循环的位置一定是 2k 的倍数，即 4 的倍数，即：0, 4, 8…

需要注意的是，因为要在 2k 的倍数处进判断子串位置。以下图为例：

当最后一组， left 指向位置 6，而 right 需要指向位置 8，但是字符串不够 8。这里需要特殊处理一下：

left = index
right = index+k-1 if index+k < size else size-1

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5bf69779-cce8-4d16-a69e-a9b0fffce19e

def reverseStr(self, s, k):
    list_s = list(s)
    size = len(list_s)
    for index in range(0, size, 2*k):
        left = index
        right = index+k-1 if index+k < size else size-1
        while left < right:
            list_s[left], list_s[right] = list_s[right], list_s[left]
            left += 1
            right -= 1

    return "".join(list_s)

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:4883e131-c5d3-47d2-9385-8ec46ef09769

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bd2ba864-b765-4d7e-a728-eb6c9649d0fc

另外，方便的话也在我的 github👇 加颗星，它是我持续输出最大最大的动力，感谢大家！

github：https://github.com/xiaozhutec/share_leetcode

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:bb459575-57e5-4fc7-a5e2-f76627443a16

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:02492941-3f22-48ad-928e-948b242f71f9

下面不要忘记抽取福利吖，好了~ 咱们下期见！bye~~

Original: https://www.cnblogs.com/yydsxiaozhu/p/15539918.html
Author: 技术gogogo
Title: 【完虐算法】「字符串-逆序」全复盘