344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

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

示例 2：

1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思路：

使用双指针，定位到起始和结尾

调换起始和结尾的数据

起始+1，结尾-1

代码：

1
2
3
4
5
6
7
8
class Solution(object):
    def reverseString( s):
        left,right=0,len(s)-1
        while left<right:
            s[left],s[right]=s[right],s[left]
            left+=1
            right-=1
        return s

541.反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

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

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

思路：

定义一个翻转函数

for循环遍历步距为2k

对i：i+k元素重新赋值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def reverseStr(s, k):

        def reverse(s):
            left, right = 0, len(s) - 1
            while left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
            return s
        s=list(s)
        for i in range(0,len(s),2*k):
            s[i:i+k]=reverse(s[i:i+k])

        return ''.join(s)

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

思路：

获取字符串中空格的个数

对原数组s进行扩充，长度为空格个数的两倍

采用双指针，末指针指向扩充后的末尾，起始指针指向原数组的末尾

当起始指针不为空时，对末指针赋予该值，当起始指针为空时，对末指针赋予%20

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def replaceSpace( s):
        counter=s.count(' ')
        s=list(s)
        tmps=s[:]
        tmps.extend(['']*counter*2)
        slow,fast=len(s)-1,len(tmps)-1
        while slow>=0:
            if tmps[slow]!=' ':
                tmps[fast]=tmps[slow]
                fast-=1
            else:
                tmps[fast-2:fast+1]='%20'
                fast-=3
            slow-=1
        return ''.join(tmps)

151.反转字符串中的单词

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

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

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

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

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

思路：

对空格进行处理

使用翻转函数对每个单词进行翻转

对整个字符串进行翻转

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
    # 1.去除多余的空格
    def trim_spaces(self, s):
        n = len(s)
        left = 0
        right = n - 1

        while left <= right and s[left] == ' ':  # 去除开头的空格
            left += 1
        while left <= right and s[right] == ' ':  # 去除结尾的空格
            right -= 1
        tmp = []
        while left <= right:  # 去除单词中间多余的空格
            if s[left] != ' ':
                tmp.append(s[left])
            elif tmp[-1] != ' ':  # 当前位置是空格，但是相邻的上一个位置不是空格，则该空格是合理的
                tmp.append(s[left])
            left += 1
        return tmp

    # 2.翻转字符数组
    def reverse_string(self, nums, left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return None

    # 3.翻转每个单词
    def reverse_each_word(self, nums):
        start = 0
        end = 0
        n = len(nums)
        while start < n:
            while end < n and nums[end] != ' ':
                end += 1
            self.reverse_string(nums, start, end - 1)
            start = end + 1
            end += 1
        return None

    # 4.翻转字符串里的单词
    def reverseWords(self, s):  
        # 测试用例："the sky is blue"
        l = self.trim_spaces(s)  
        # 输出：['t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e'
        self.reverse_string(l, 0, len(l) - 1)  
        # 输出：['e', 'u', 'l', 'b', ' ', 's', 'i', ' ', 'y', 'k', 's', ' ', 'e', 'h', 't']
        self.reverse_each_word(l)  
        # 输出：['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']
        return ''.join(l)  # 输出：blue is sky the

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

思路：

扩充原数组，扩充大小为k

使用双指针分别定为到扩充后的结尾和k-1

将k左边的元素赋值给结尾

代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def reverseLeftWords(s, n):
        s=list(s)
        s.extend(['']*n)
        fast=len(s)-1
        slow=n-1
        while slow>=0:
            s[fast]=s[slow]
            slow-=1
            fast-=1
        return ''.join(s[n:])

28.找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

思路：

采用窗口的思想，窗口大小为needle

代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        m,n=len(haystack),len(needle)
        for i in range(m):
            if haystack[i:i+n]==needle:
                return i
        return -1

459.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

1
2
3
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

1
2
输入: s = "aba"
输出: false

示例 3:

1
2
3
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

思路：

如果s不包含重复子串，那么s自己就是一次重复的子串，那么把s + s去头去尾中就一定不包含s自己。

如果s包含重复子串，那么在s + s去头去尾中就一定能找到s自己