一、151翻转字符串里的单词

​​​​​151. 反转字符串中的单词 - 力扣（LeetCode）

题解：这道题的难度还是很综合的，在CPP里面调用库函数的话应该有蛮多种解法，卡哥提到用split函数分开各个单词，然后再反转各个单词最后再join合并在一起，听起来很妙（不过我也不会写，我还没学到这），C语言少了这些库函数的调用的同时，且要保持空间复杂度为O（1）的话，我们可以这样：首先把单词间多的空格（只允许一个）以及两端多的空格去除掉，然后再整体反转，之后根据空格（因为之前去除空格的时候保留了单词间的的一个）以及结束符来找到每个反转后的单词，再给他反转一次即可。当然，去除的函数和反转的函数可以用void写在外面，然后再调用，相当于自己创了个库
CPP如下：

//要翻转字符串中的单词，先要去空格，再翻转单个单词

//翻转单词
void reverse(char* s,int start,int end){
   for(int i=start,j=end;i<j;i++,j--){
    int temp;
    temp=s[i];
    s[i]=s[j];
    s[j]=temp;
   }
}

//去掉空格
void removeExtraSpace(char* s){
    int start=0;
    int end=strlen(s)-1;//旧的尾指针
    while(s[start]==' ')start++;
    while(s[end]==' ')end--;//找到第一个尾部不为0的字符
    int slow=0;//指向新指针
    for(int i=start;i<=end;i++){
        if(s[i]==' '&&s[i+1]==' ')
            continue;//当这个和下一个都是空时跳过空格,若只有一个空格是保留的
        s[slow]=s[i];
        slow++;
    }
    s[slow]='\0';//结束加结束符
}


//交换单词内部的字符：先去除空格然后再交换
char* reverseWords(char* s) {
    removeExtraSpace(s);
    reverse(s,0,strlen(s)-1);
    int head=0;//指向单词开头，要找空字符来断开一个单词
    for(int i=0;i<=strlen(s);i++){
        if(s[i]==' '||s[i]=='\0'){
            reverse(s,head,i-1);
            head=i+1;//指向下一个单词头
        }
    }
    return s;
}

对了，注意交换的时候写的是i<j，不再是i<strlen(s)/2，因为后面要交换的还有各个单词间的，不止是一整个字符串的，会访问字符串外的内存地址，触发了堆缓冲区溢出。因此访问的只是start到end间的，只要i<j就可以

卡哥的CPP写法如下：一起放入，以便学习151.翻转字符串里的单词 | 代码随想录

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

二、卡码网右旋字符串

做了上一题后这题其实还好，话不多说，先上题：55. 右旋字符串（第八期模拟笔试）

题解：这题主要可以用先整体反转，再前后两部分旋转，也可以是先前后两部分旋转再整体旋转。如果题目换成左旋圆也是一样的，这几个都是reverse的范围要注意分清，CPP我的题解如下：

#include<stdio.h>
#include<string.h>

//反转
void reverse(char* s,int left,int right){
    while(left<=right){
        char c;
        c=s[left];
        s[left]=s[right];
        s[right]=c;
        left++;
        right--;
    }
}

//右旋:先反转整体，再反转部分
void  rightRotate(char *s,int k){
    int len=strlen(s);
    k=k%len;
    reverse(s,0,len-1);
    reverse(s,0,k-1);//前
    reverse(s,k,len-1);
}

int main(){
    int k;
    scanf("%d",&k);
    char s[10000];
    scanf("%s",s);
    rightRotate(s,k);
    printf("%s\n",s);
    return 0;
}

这个代码写起来还是比较容易的，但是有一个很致命的错误找了半天，如下：

void reverse(char* s, int left, int right) {
    // 这里的循环让 i 和 j 往中间移动，这是对的
    for(int i=left, j=right; i<j; i++, j--) {
        char c;
        c = s[left];      // <--- 错误！这里应该用 s[i]
        s[left] = s[right]; // <--- 错误！这里应该用 s[right] = s[i] 和 s[left] = s[j]
        s[right] = c;     // <--- 错误！这里应该用 s[j]
    }
}

我在写的时候赋值了但是没有修改变量，搞得一直输出有bug卡住，好在这种小问题对于小AI来说还是好找到的

三、实现strStr(找出字符串中第一个匹配项的下标)

先看题目：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

题解：这题写了好久，先看了B站上卡哥关于KMP的解释以及代码书写，大部分能懂，但是刚写起来也比较费劲，对照着标答慢慢写，边写便琢磨是因为什么，写下的注释也不少，搞懂了不少疑惑，现在看起来还是很顺的。主要就是先找到next数组（注意针对的是模式串），找完后再和文本串进行对比，我的理解是再找到其中的更大next数组，所以方法类似，一步步移动指针，C解法如下，对了动态分配记得free

//KMP算法，先构造next数组，
//构造next数组包括：初始化，前后缀不相同情况，前后缀相同情况，最后更新next
void getNext(int* next,const char* s)//const char* s指的是只读这个字符串,，不改变模式串
{
    //初始化
    int j=0;
    next[0]=0;//前缀表第一位为0，即不移动（如aabaaf中的a的为0即第一位前缀表为0）
    //j为前缀表的尾部，i为后缀表的尾部
    for(int i=1;i<strlen(s);i++){
        //处理不相同
        while(j-1>=0&&s[i]!=s[j])//因为不相等时要回退重新比较具体可看卡哥的next的动态图
            j=next[j-1];
        if(s[i]==s[j])
            j++;
        next[i]=j;//最长相等前后缀子串长度是j的位置
    }
}

int strStr(char* haystack, char* needle) {
    int n=strlen(haystack);
    int m=strlen(needle);
    if(m==0)return 0;//C,CPP,PYTHON的共性定义，在查找空字符串时，都会返回 0
    //手动分配next数组的内存
    int* next=(int*)malloc((sizeof(int)*m));//next数组是为模式串服务的，因此是*m
    //计算next数组
    getNext(next,needle);
    int j=0;
    for(int i=0;i<n;i++){
        while(j>0 && haystack[i]!=needle[j]){
            j=next[j-1];
        }
        if(haystack[i]==needle[j])j++;
        if(j==m){//找到匹配了
            free(next);
            return(i-m+1);//起始位置=结束位置-长度+1
        }
    }
    free(next);
    return -1;//未找到

}

因此，这道题的核心是利用 KMP 算法在不回退主串指针的前提下高效查找子串：首先处理空串等边界情况，接着通过分析模式串（needle）自身的重复特征构建一个 next 数组（前缀表），作为“匹配失败时的跳转指南”；随后遍历主串（haystack），当遇到字符不匹配时，主串指针 i 继续向前，仅利用 next 数组将模式串指针 j 智能回退到合适的位置继续比对，从而实现一次线性扫描即可判断是否匹配，并在完全匹配时通过当前位置反推并返回起始下标 i - m + 1。

好了，今天就到这！！！！！！！！！