代码随想录——串
反转字符串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;
s=s;
s=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;
s=s;
s=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=='.')path=' ';
}
return path;
}
反转字符串中的单词
151. 反转字符串中的单词
思绪：去除多余的空格，首位的空格以及中心多出的空格，再把整个字符串反转，末了把整个单词反转
char* reverseWords(char* s) {
int n = strlen(s);
// 去除首尾空格
int start = 0, end = n - 1;
while (start <= end && s == ' ') start++;
while (end >= start && s == ' ') 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 > start && s != ' ')) {
t = s;
}
}
t = '\0'; // 添加终止符
// 反转整个字符串
for (int i = 0, j = strlen(t) - 1; i < j; i++, j--) {
char temp = t;
t = t;
t = temp;
}
// 反转每个单词
int word_start = 0;
for (int i = 0; i <= strlen(t); i++) {
if (t == ' ' || t == '\0') {
int word_end = i - 1;
while (word_start < word_end) {
char temp = t;
t = t;
t = 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=password;
}
for(int i=strlen(password)-target;i<strlen(password);i++){
ans=password;
}
ans='\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==needle){
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=j;
int i=1;
while(i<l){
if(s==s){
j++;
next=j;
i++;
}
else{
if(j!=0){
j=next;
}
else{
next=0;
i++;
}
}
}
}
// KMP 算法
int strStr(char* haystack, char* needle) {
int n = strlen(haystack);
int m = strlen(needle);
// 特殊情况处理
if (m == 0) {
return 0;
}
// 构建部分匹配表
int next;
getnext(needle, m, next);
int i = 0; // haystack 的索引
int j = 0; // needle 的索引
while (i < n) {
if (haystack == needle) {
i++;
j++;
}
if (j == m) {
return i - j; // 找到匹配项
}
else if (i < n && haystack != needle) {
if (j != 0) {
j = next;
} 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==s){
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=-1;
int i=-1,j=0;
while(j<n-1){
if(i==-1||s==s){
i++,j++;
next=i;
}
else{
i=next;
}
}
}
bool repeatedSubstringPattern(char* s) {
int n=strlen(s);
if(n<=1)return false;
int next;
getnext(s,next,n);
int k=next;//若存在子串，k后面为最后一个字串
int len=n-k-1;
int i=len;
k=0;
while(i<n&&s==s){
if(k==len-1)k=0;
else{
k++;
}
i++;
}
if(k==0&&i==n)return true;
else return false;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]