反轉字符串

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