leetcode面试题之字符串

344. 反转字符串

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

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

链接：https://leetcode.cn/problems/reverse-string/

思路：双指针 剪枝：i<n/2

public void reverseString(char[] s) {
        int n = s.length;
        // 双指针 ； 剪枝：i<n/2
        for (int i = 0, j = n - 1; i < n / 2; i ++, j --) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }

541. 反转字符串 II

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

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

链接：https://leetcode.cn/problems/reverse-string-ii/

思路：i += 2 * k

public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        // 每隔2k个字符的前k个翻转
        for (int i = 0; i < n; i += 2 * k) {
            if (i + k < n) { // 1.剩余字符在[k, 2k),翻转前k个字符
                reverse(ch, i, i + k - 1);
                continue;
            } 
            // 2.剩余字符小于k个，全部翻转
            reverse(ch, i, n - 1);
        }
        return new String(ch);
    }

    public void reverse(char[] s, int start, int end) {
        for (int i = start, j = end; i < j; i ++, j --) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }

剑指 Offer 05. 替换空格

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

链接：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

思路：

1.统计空格数 count
2.创建一个字符数组ch n+2*count
3.遍历s并给ch赋值，空格替换成%20，非空格直接赋值原字符

public String replaceSpace(String s) {
        // 1.统计空格数
        int count = 0, n = s.length();
        for (int i = 0; i < n; i ++) {
            if (s.charAt(i) == ' ') count ++;
        }
        // 2. 新的字符串长度 n+2*count
        // 新建一个数组操作，最后转为字符串，因为String是不可变的
        char[] ch = new char[n + 2 * count]; 
        // 3. 遍历修改，遇到空格替换；不是空格直接赋值
        count = 0;
        for (int i = 0; i < n; i ++) {
            char c = s.charAt(i);
            if (c == ' ') {
                ch[count ++] = '%';
                ch[count ++] = '2';
                ch[count ++] = '0';
            } else {
                ch[count ++] = c;
            }
        }
        return new String(ch);
    }

151. 反转字符串中的单词

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

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

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

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

链接：https://leetcode.cn/problems/reverse-words-in-a-string/

思路：

1.移除多余空格
2.反转整个字符串
3.反转每个单词

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

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

链接：https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/

思路：翻转三次，先局部翻转，再整体翻转

public String reverseLeftWords(String s, int n) {
        char[] ch = s.toCharArray();
        int len = ch.length;
        // 翻转三次，先局部翻转，再整体翻转
        reverse(ch, 0, n - 1);
        reverse(ch, n, len - 1);
        reverse(ch, 0, len - 1);
        return new String(ch);
    }
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start ++;
            end --;
        }
    }

28. 实现 strStr()

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

链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

思路：KMP

1. 求next数组
2. 匹配
   注：KMP通常下标从1开始

public int strStr(String haystack , String needle ) {
        int n = haystack.length(), m = needle.length();
        // 小标从1开始，先在首部加一个空格
        haystack = " " + haystack;
        needle  = " " + needle ;
        char[] s = haystack.toCharArray(), p = needle.toCharArray();
        int[] next = new int[m + 1];
        next[0] = 0;
        next[1] = 0;

        // 求next数组
        for (int i = 2, j = 0; i <= m; i ++) {
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            if (p[i] == p[j + 1]) j ++;
            next[i] = j;
        }
        // 匹配
        for (int i = 1, j = 0; i <= n; i ++) {
            while(j > 0 && s[i] != p[j + 1]) j = next[j]; // 当前字符不匹配，整体后移next[j]
            if (s[i] == p[j + 1]) j ++; // 当前字符匹配，后移一位继续匹配
            if (j == m) return i - m; // 匹配成功， i终点 m长度
        }
        return -1; // 匹配不成功
    }