刷题顺序来自：代码随想录

• 反转字符串
  • 344. 反转字符串
  • 541. 反转字符串 II
• 替换空格
  • 剑指 Offer 05. 替换空格
• 翻转单词
  • 151. 翻转字符串里的单词
• 左旋转字符
  • 剑指 Offer 58 - II. 左旋转字符串
• 实现strStr(): 经典KMP算法
  • 28. 实现 strStr()

反转字符串

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"]

public void reverseString(char[] s) {
    if(s.length <= 1) return;

    int left = 0, right = s.length - 1;
    while(left < right) {
        char ch = s[left];
        s[left] = s[right];
        s[right] = ch;

        left++;
        right--;
    }
}

541. 反转字符串 II

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

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

示例 1:

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

示例 2:

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

public String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();

    int left = 0, right = 0;

    while(left < chars.length - 1) {
        while(right < chars.length - 1 && right - left + 1 < 2 * k) {
            right++;
        }

        if(right - left + 1 == 2 * k) {
            resverse(chars, left, (left + right) / 2);
        }
        else {
            // 反转前k个或剩余所有字符
            resverse(chars, left, Math.min(right, left + k - 1));
        }

        left = ++right;
    }
    return new String(chars);
}

// 将chars的索引left到right之间的字符反转
public void resverse(char[] chars, int left, int right) {
    while(left < right) {
        char ch = chars[left];
        chars[left] = chars[right];
        chars[right] = ch;

        left++;
        right--;
    }
}

更好的方法：每次循环走2*k格，循环中判断反转的右索引值。

public String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();

    for(int i = 0; i < chars.length; i += 2 * k) {
        int end = Math.min(i + k - 1, chars.length - 1);
        resverse(chars, i, end);
    }

    return new String(chars);
}

替换空格

剑指 Offer 05. 替换空格

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

示例 1:

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

public String replaceSpace(String s) {
    // 得到字符串中的空格数量
    int count = 0;
    for(int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' ') {
            count++;
        }
    }

    // 扩容字符数组
    char[] chars = new char[s.length() + 2 * count];
    int pos = 0;
    
    // 将原来字符串中的字符复制到扩容后的字符数组
    for(int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' ') {
            chars[pos] = '%';
            chars[++pos] = '2';
            chars[++pos] = '0';
        }
        else {
            chars[pos] = s.charAt(i);
        }
        pos++;
    }

    return new String(chars);
}

翻转单词

151. 翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

示例 1:

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

示例 2:

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。

双指针从右向左走，left和 right中间是一个单词。

public String reverseWords(String s) {
    s = s.trim();  // 去头尾空格
    StringBuilder res = new StringBuilder();

    int left = s.length() - 1, right = s.length() - 1;  // left, right之间是一个单词
    for(int i = s.length() - 1; i >= 0; i--) {
        if(s.charAt(i) == ' ') {
            if(left == right) {  // 遇到了多个空格，left和right同时向左，跳过空格
                left--;
                right--;
            }
            else {  // 遇到了第一个空格，表示找到了一个单词
                res.append(s.substring(left + 1, right + 1) + " ");
                right = --left;
            }
        }
        else {  // 向左找，直到找到一个完整的单词
            left--;
        }
    }
	
    // 将最后一个单词加上
    if(left != right) {
        res.append(s.substring(left + 1, right + 1));
    }

    return res.toString();
}

左旋转字符

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

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

示例 1:

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

示例 2:

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

使用substring，此方法申请了O(n)的额外空间。

public String reverseLeftWords(String s, int n) {
    StringBuilder res = new StringBuilder();

    res.append(s.substring(n, s.length()));
    res.append(s.substring(0, n));

    return res.toString();
}

先反转前n个字符，再反转n后的字符，最后反转整个字符串，这种做法没有额外申请空间。

public String reverseLeftWords(String s, int n) {
    StringBuilder res = new StringBuilder(s);

    reverse(res, 0, n);
    reverse(res, n, s.length());
    reverse(res, 0, s.length());

    return res.toString();
}

// left, right为左闭右开
public void reverse(StringBuilder builder, int left, int right) {
    while(left < right) {
        char ch  = builder.charAt(left);
        builder.setCharAt(left, builder.charAt(right-1));
        builder.setCharAt(right-1, ch);

        left++;
        right--;
    }
}

实现strStr(): 经典KMP算法

28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从0 开始）。如果不存在，则返回 -1 。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。

示例 1:

输入：haystack = "hello", needle = "ll"
输出：2

示例 2:

输入：haystack = "aaaaa", needle = "bba"
输出：-1