**************

55. 右旋字符串

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

459. 重复的子字符串

（原地覆盖法，常用于原地删除某些内容）

**************

思路&方法

思路

先去除多余空格，再整体翻转字符串，最后翻转字符串里的每个单词

方法

1、除去空格，用原地覆盖法（快慢指针，slow指向新字符串位置，fast寻找旧字符串中符合要求字符串）

2、反转字符串，双指针，一开头一结尾，边更新位置边交换字符

代码一

void removeblack(char* s) {
    int slow, fast;
    for (slow = 0, fast = 0; fast <= strlen(s); fast++) {
        if (s[fast] != ' ') {
            if (slow != 0 && s[fast - 1] == ' ' && s[fast] != '\0')
                s[slow++] = ' ';
            s[slow++] = s[fast];
        }
    }
    return;
}
void reverse(char* s, int start, int end) {
    int left = start, right = end;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
    return;
}
char* reverseWords(char* s) {
    removeblack(s);
    reverse(s, 0, strlen(s) - 1);
    int start = 0;
    for (int i = 0; i <= strlen(s); i++) {
        if (s[i] == ' ' || s[i] == '\0') {
            reverse(s, start, i - 1);
            start = i + 1;
        }
    }
    return s;
}

代码二

上面那个提交后耗时太久，所以改了一下reverse，但是结果大差不差

void removeblack(char* s) {
    int start = 0, end = strlen(s) - 1;
    while (s[start] == ' ') {
        start++;
    }
    while (s[end] == ' ') {
        end--;
    }
    int slow = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] == ' ' && s[i + 1] == ' ') {
            continue;
        }
        s[slow++] = s[i];
    }
    s[slow] = '\0';
    return;
}
void reverse(char* s, int start, int end) {
    int left = start, right = end;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
    return;
}
char* reverseWords(char* s) {
    removeblack(s);
    reverse(s, 0, strlen(s) - 1);
    int start = 0;
    for (int i = 0; i <= strlen(s); i++) {
        if (s[i] == ' ' || s[i] == '\0') {
            reverse(s, start, i - 1);
            start = i + 1;
        }
    }
    return s;
}

55. 右旋字符串

思路&方法

思路

这题不难，但是原地翻转的话，不太好想。

先整体翻转，让后面k个字符转到前面来，再分别翻转前k个字符和剩下的字符，更正顺序

方法 和上面那一题是一样的reverse方法

#include <stdio.h>
#include <string.h>
#define Max 10000
void reverse(char* s, int start, int end) {
    char temp;
    while (start < end) {
        temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
    return;
}
int main(void) {
    int k;
    char s[Max];
    scanf("%d", &k);
    scanf("%s", &s);
    reverse(s, 0, strlen(s) - 1);
    reverse(s, 0, k - 1);
    reverse(s, k, strlen(s) - 1);
    printf("%s\n", s);
    return 0;
}

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

思路&方法 KMP

基本的暴力思想是枚举遍历，在此基础上稍微改进的方法就是KMP（我认为），KMP的难点在于写出来正确的next数组，理解前缀（必须包含第一个字符且不包含最后一个字符的所有子字符串都是前缀）和后缀（所有包含后缀字符且不包含首字符的子字符串就是后缀）能更好写出next数组。

我用的是不加不减不右移的前缀表

理解next数组代码实现 目前next数组为什么能这么操作得来我也不是特别清楚，但是大体也能理解。

j是前缀的末尾，i是后缀的末尾，j标志着以首字符为开始以j对应字符为结束的前缀，相当于i的位置标志着以首字符为开始以i所对应字符为结束的子字符串，i既是后缀的开始也是后缀的结束，在i和j更新的同时，这个子字符串前缀和后缀也在更新。

最难理解的应该是以i为结尾的后缀的开头在哪里，我认为应该是在j回到0且又一次与i匹配的时候，还有一种情况是j与i在过程中不匹配了，但是j没有回到0，这是在更新后缀的首字符位置，首字符与尾字符距离就是j，所以每次i与j重新匹配都是在更新后缀的开头位置，也可以理解为更新后缀长度，也就是我们要找的最大前后缀长度吧。

（理解有待加深）

代码

void getNext(int* next, char* a) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < strlen(a); i++) {
        while (j > 0 && a[j] != a[i]) {
            j = next[j - 1];
        }
        if (a[j] == a[i]) {
            j++;
        }
        next[i] = j;
    }
}
int strStr(char* haystack, char* needle) {
    int len1 = strlen(haysFtack), len2 = strlen(needle);
    int* next = (int*)malloc(sizeof(int) * len2);
    getNext(next, needle);
    int j = 0,
        i = 0; // j是前缀的末尾，i是后缀的末尾，既i是当前字符串的最后一个字符

    while (i < len1) {
        // 当查找字符串的第i个和模式串的第j个相同，同时更新i和j
        while (i < len1 && j < len2 && haystack[i] == needle[j]) {
            i++;
            j++;
        }
        if (j == len2) {
            free(next);
            return i - j;
        }
        if (j > 0)
            j = next[j - 1];
        else
            i++;
    }
    free(next);
    return -1;
}

459. 重复的子字符串

思路&方法

（卡哥讲了三个方法，暴力、移动匹配、KMP，没看懂移动匹配，只写了KMP）

卡哥说，制造出题目字符串的next数组，将数组长度如果len%(len-next[len-1])==0，那么就是重复的（当然还有其他的小细节，具体原理我无法条理的表达出来）

void getNext(int* next, char* s) {
    int j = 0, i = 1;
    next[0] = 0;
    while (i < strlen(s)) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j])
            j++;
        next[i] = j;
        i++;
    }
    return;
}
bool repeatedSubstringPattern(char* s) {
    int len = strlen(s);
    int* next = (int*)malloc(sizeof(int) * len);
    getNext(next, s);
    int p = len - next[len - 1];
    free(next);
    if (p != 0 && p != len && len % p == 0)
        return true;
    return false;
}

字符串小结

常用方法

一、双指针法 删除元素，删除空格，原地修改

二、翻转 整体翻转，局部翻转，先整体再局部

三、KMP 字符串与子字符串匹配问题，字符串重复元素组成问题

双指针用法小结

一、数组

删除数组中元素，一个i指向新数组位置，j在原数组中查找合适元素。

二、字符串

1、删除空格，方法与删除数组中元素相同

2、翻转字符串，两指针一头一尾交换元素

三、链表

1、翻转链表，两指针紧挨着，更改每个节点的next指向前一个节点

2、判断链表是否有环，快慢指针，若有环则最终会相遇

3、判断链表环的入口，额是个数学推导题，忘记了就看 环形链表Ⅱ

四、N数之和

类似于三数之和和四处之和，要求去重，用哈希很麻烦，用for循环固定前n-2个数字，再用while更改两指针（一个在最后一个数的下一个位置，一个指向数组最后一个数，根据n数之和不断更新两指针位置，注意去重操作）