代码随想录——串

反转字符串

344. 反转字符串

//前后对应交换
//0<->sSize-1
//1<->sSize-2
//...
//i<->sSize-1-i,i=0,1,...,(sSize-1)/2
void reverseString(char* s, int sSize) {
    for(int i=0;i<sSize/2;i++){
        char t=s[i];
        s[i]=s[sSize-1-i];
        s[sSize-1-i]=t;
    }
}

反转字符串Ⅱ

541. 反转字符串 II

思路：在规定区间内反转字符串

//反转下标从l到r的这段字符串
void reverse(char *s,int l,int r){
    for(int i=l;i<=(l+r)/2;i++){
        char t=s[i];
        s[i]=s[l+r-i];
        s[l+r-i]=t;
    }
}
char* reverseStr(char* s, int k) {
    int i=0;
    int l=strlen(s);
    while(l-i>k){
        reverse(s,i,i+k-1);
        i+=2*k;
    }
    if(i<l)reverse(s,i,l-1);
    return s;
}

路径加密

LCR 122. 路径加密

char* pathEncryption(char* path) {
    int l=strlen(path);
    for(int i=0;i<l;i++){
        if(path[i]=='.')path[i]=' ';
    }
    return path;
}

反转字符串中的单词

151. 反转字符串中的单词

思路：去除多余的空格，首位的空格以及中间多出的空格，再把整个字符串反转，最后把整个单词反转

char* reverseWords(char* s) {
    int n = strlen(s);
    // 去除首尾空格
    int start = 0, end = n - 1;
    while (start <= end && s[start] == ' ') start++;
    while (end >= start && s[end] == ' ') end--;

    // 分配足够的内存，包括终止符
    char *t = (char *)malloc((end - start + 2) * sizeof(char));
    if (t == NULL) {
        return NULL; // 内存分配失败
    }

    // 去除中间多余的空格
    int j = 0;
    for (int i = start; i <= end; i++) {
        if (s[i] != ' ' || (i > start && s[i - 1] != ' ')) {
            t[j++] = s[i];
        }
    }
    t[j] = '\0'; // 添加终止符

    // 反转整个字符串
    for (int i = 0, j = strlen(t) - 1; i < j; i++, j--) {
        char temp = t[i];
        t[i] = t[j];
        t[j] = temp;
    }

    // 反转每个单词
    int word_start = 0;
    for (int i = 0; i <= strlen(t); i++) {
        if (t[i] == ' ' || t[i] == '\0') {
            int word_end = i - 1;
            while (word_start < word_end) {
                char temp = t[word_start];
                t[word_start] = t[word_end];
                t[word_end] = temp;
                word_start++;
                word_end--;
            }
            word_start = i + 1;
        }
    }

    return t;
}

动态口令

LCR 182. 动态口令

开辟相同大小的空间，模拟

//用辅助字符串
char* dynamicPassword(char* password, int target) {
    char * ans=malloc(sizeof(char)*(strlen(password)+1));
    for(int i=0;i<strlen(password)-target;i++){
        ans[i]=password[i+target];
    }
    for(int i=strlen(password)-target;i<strlen(password);i++){
        ans[i]=password[i+target-strlen(password)];
    }
    ans[strlen(password)]='\0';
    return ans;
}

时间复杂度：O(n)

空间复杂度：O(n)

字符串匹配

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

方法一：暴力

//暴力
int strStr(char* haystack, char* needle) {
    int i=0,j=0;
    int la=strlen(haystack);
    int lb=strlen(needle);
   
    while(i<la&&j<lb){
        if(haystack[i]==needle[j]){
            i++,j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
    if(j==lb)return i-j;
    else return -1;
}

方法二：KMP

//构建next数组
void getnext(char *s,int l,int *next){
    int j=0;
    next[0]=j;
    int i=1;
    while(i<l){
        if(s[i]==s[j]){
            j++;
            next[i]=j;
            i++;
        }
        else{
            if(j!=0){
                j=next[j-1];
            }
            else{
                next[i]=0;
                i++;
            }
        }
    }
}

// KMP 算法
int strStr(char* haystack, char* needle) {
    int n = strlen(haystack);
    int m = strlen(needle);

    // 特殊情况处理
    if (m == 0) {
        return 0;
    }

    // 构建部分匹配表
    int next[m];
    getnext(needle, m, next);

    int i = 0; // haystack 的索引
    int j = 0; // needle 的索引

    while (i < n) {
        if (haystack[i] == needle[j]) {
            i++;
            j++;
        }

        if (j == m) {
            return i - j; // 找到匹配项
        }
        else if (i < n && haystack[i] != needle[j]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }

    return -1; // 未找到匹配项
}

重复的子字符串

459. 重复的子字符串

方法一：暴力

列举出子字符串的长度，最长为字符串长度的一半

//暴力
bool repeatedSubstringPattern(char* s) {
    int n=strlen(s);
    for(int i=1;i<=n/2;i++){//i表示字串的长度
        int j=i;
        int k=0;
        while(j<n&&s[k]==s[j]){
            if(k==i-1)k=0;
            else k++;
            j++;
        }
        if(j==n&&k==0)return true;
    }
    return false;
}

方法二：KMP

//KMP
void getnext(char *s,int *next,int n){
    next[0]=-1;
    int i=-1,j=0;
    while(j<n-1){
        if(i==-1||s[i]==s[j]){
            i++,j++;
            next[j]=i;
        }
        else{
            i=next[i];
        }
    }
}
bool repeatedSubstringPattern(char* s) {
    int n=strlen(s);
    if(n<=1)return false;
    int next[n];
    getnext(s,next,n);
    int k=next[n-1];//若存在子串，k后面为最后一个字串
    int len=n-k-1;
    int i=len;
    k=0;
    while(i<n&&s[k]==s[i]){
        if(k==len-1)k=0;
        else{      
            k++;
        }
        i++;
    }
    if(k==0&&i==n)return true;
    else return false;

}