前言

今天是算法训练营的第九天，由于没有看训练营题目安排，在两道KMP算法上死磕了好久，最后好不容易有个一知半解，最后发现这两题难度太大可以跳过……

总体来说，字符串部分的题目还是比较简单的(除了两道KMP)，接下来进行今天题目的回顾和双指针部分的总结。

151.翻转字符串里的单词

题目链接：151. 反转字符串中的单词

题目描述：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

思路

这道题目是在反转字符串的基础上更进一步，如果只是反转字符串，那么每个单词里字母的顺序也都是颠倒的，这时我们只需要以空格为限，对每个单词进行反转即可。

除了以上的方式，由于python的标准库过于强大，我们也可以使用split把每个单词都单独分出来，然后倒过来添加进答案输出即可。

实现写法

 class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1

        return " ".join(words)

卡码网55.右旋转字符串

题目链接：https://kamacoder.com/problempage.php?pid=1065

题目描述：

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

思路

这题使用python处理起来相对简单很多，由于python的切片特性，我们只需要依靠切片，将前k个元素和后k个元素单独取出来，更改位置后拼接起来即可。

实现写法

k = int(input())
s = input()

print(s[-k:] + s[:-k])

28和459后续单独出一篇KMP相关文章

理解难度较大，目前理论基础不足以支撑写出文章

字符串部分总结

字符串部分的题目大多是对字符串内容进行一些简单操作，需要注意的是python中无法对字符串直接进行修改，但我们依然可以借助数组等结构实现目的。

双指针部分总结

到这里双指针的题目已经做过十道，双指针在先前每个篇章都有应用到，在我目前的认知中，双指针的最大效用就是将原本O(n^2)的复杂度降低到O(n)，在使用过程中需要时刻注意两个指针的状态更新。