字符串算法（1）

344. 反转字符串

344. 反转字符串

简单

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

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

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
提示：

1 <= s.length <= 105

s[i] 都是 ASCII 码表中的可打印字符

用 left 和 right 双指针， for left < right {} 循环直接反转字符串即可。不要习惯性地 for i:=0; i<len; i++ {}。

func reverseString(s []byte)  {
    left := 0
    right := len(s) - 1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

541.反转字符串 II

541. 反转字符串 II

简单

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

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

示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
提示：

1 <= s.length <= 104

s 仅由小写英文组成

1 <= k <= 104

思路

每隔 2k 个字符的前 k 个字符进行反转
剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符

PS：反转函数和344.反转字符串一样，直接使用库函数也可以。许多库函数的区间都是左闭右开的。

这道题用Go写可以对 s 进行切片，直接对底层数组进行反转操作。

func reverseStr(s string, k int) string {
    ss := []byte(s)
    len := len(ss)
    for i := 0; i < len; i += 2*k {
        if i + k <= len { // 1,2,3 k==2
            // 反转 i ~ i+k （前k个），凑足k个反转
            reverse(ss[i:i+k]) // 左闭右开
        } else {
            // 剩余的不足k个，剩下的都反转
            reverse(ss[i:len])
        }
    }
    return string(ss)
}

func reverse(s []byte) []byte{
    left := 0
    right := len(s)-1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
    return s
}

151. 反转字符串中的单词

151. 反转字符串中的单词

中等

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

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

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

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

示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：

1 <= s.length <= 104

s 包含英文大小写字母、数字和空格 ' '

s 中 至少存在一个 单词

**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的原地解法。

本题增加难度，在原地进行操作。在 go 语言中将字符串转换为 []byte 来操作。

1. 双指针法（快慢指针）来去除多余的空格。

当快指针 i 读到字母（非空格字符时），开始处理需要写入的内容。

在每个单词前加一个空格（首个单词除外）

// 单词间加上空格
if slow != 0 {
  ss[slow] = ' '
  slow++
}

把需要复制的字符，复制到慢指针，随后快慢指针向后移动（即原地覆盖字符串），截断字符串到有效部分。

2. 翻转字符串

先翻转整个字符串，再翻转每个单词，就实现了题目的要求。

翻转单词的思路就是记录单词的开头位置，同时找到下一个空格或字符串末尾+1的索引 i，reverse(s[start, i])，实现对底层数组的修改。

for 循环的判断条件是 i <= len(s)，因为到 i<len 是遍历到字符串末尾，切片操作是左闭右开，想要包含最后一个字符，就要把 i 向后多移一位。

接着 start = i + 1 （因为第 i 位是空格，下一位才是新的字母）

func reverseWords(s string) string {
    // 1. 双指针去除多余空格
    ss := []byte(s)
    slow := 0
    // 如果 slow == 0，开始复制字符串直到 i 遇到空格，下一次循环
    // 这时 slow != 0，先加个空格，再继续复制字符串
    // 这样就实现了去除多余空格
    for i := 0; i < len(ss); i++ {
        if ss[i] != ' ' {
            // 单词间加上空格
            if slow != 0 {
                ss[slow] = ' '
                slow++
            }
            // 复制逻辑
            for i < len(ss) && ss[i] != ' ' {
                ss[slow] = ss[i]
                slow++
                i++
            }
        }
    }
    // 截断字符串到实际位置
    ss = ss[0:slow]

    // 2. 反转整个字符串
    reverse(ss)
    // // 3. 反转每个单词
    start := 0
    for i := 0; i <= len(ss); i++ {
        if i == len(ss) || ss[i] == ' ' {
            reverse(ss[start:i])
            // start 是单词的开头，而此时i指向空格或字符串末尾，i+1 才是下一个单词的开头
            start = i + 1
        }
    }
    return string(ss)
}

func reverse(s []byte){
    left := 0
    right := len(s) - 1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

# 字符串算法（1）

344. 反转字符串

541.反转字符串 II

思路

151. 反转字符串中的单词

1. 双指针法（快慢指针）来去除多余的空格。

2. 翻转字符串

# 哈希表算法（3）

# 字符串算法（2）「初探KMP算法」