代码随想录——串

反转字符串

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;}