当前位置：首页 > news >正文

(c语言版)滑动窗口给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度

news 来源：原创 2024/4/28 12:52:03

适用情况：
①题目中出现最短，最长
②出现子串、子数组、子数列

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求：

1、只包含1个字母(a~z, A~Z)，其余必须是数字；

2、字母可以在子串中的任意位置；

如果找不到满足要求的子串，如果全是数字，则返回-1。

//套用模板
#include<stdio.h>
#define MAXN 10000
int isNumber(char c) {return (c>='0'&&c<='9');
}
int main(){char str[MAXN]={0};scanf("%s",str);char *left=str;char *right=str;int bestresult=0;int tag=0;while(*right!='\0'){                                       //只要右指针没有到字符串尾部while(tag==1&&!isNumber(*right)&&left<right){                   //子串不满足要求时（有两个字母）,不满足时才缩小为求最长子串left++;                                             //一直向右移动直到子串满足条件if(!isNumber(*(left-1))){                            //左指针略过最左边字母后子串满足条件，跳出循环break;}}tag= isNumber((*right))?tag:1;if(tag==1){bestresult=bestresult>(right-left+1)?bestresult:(right-left+1);}right++;}printf("%d",bestresult);return 0;
}

滑动窗口的最长子串模板

初始化 left，right，result，bestResult
while("右指针没有到结尾"){窗口扩大，加入right对应元素，更新当前resultwhile("result不满足要求"){窗口缩小，移除left对应元素，left右移}更新最优结果bestResultright++;
}
返回bestResult

滑动窗口的最短子串模板

初始化 left，right，result，bestResult
while("右指针没有到结尾"){窗口扩大，加入right对应元素，更新当前resultwhile("result满足要求"){更新最优结果bestResult窗口缩小，移除left对应元素，left右移}right++;
}
返回bestResult

//学习kmp记录next数组
#include<stdio.h>
#define MAXN 10000
int isNumber(char c) {return (c>='0'&&c<='9');
}
int main(){char str[MAXN]={0};scanf("%s",str);char *left=str;char *right=str;char *next_pos=str;int bestresult=0;int tag=0;while(*right!='\0'){                                       //只要右指针没有到字符串尾部if(!isNumber(*right)){next_pos=right+1;}if(tag==1&&!isNumber(*right)) {                   //子串不满足要求时（有两个字母）,不满足时才缩小为求最长子串left = next_pos;}tag= isNumber((*right))?tag:1;if(tag==1){bestresult=bestresult>(right-left+1)?bestresult:(right-left+1);}right++;}printf("%d",bestresult);return 0;
}

//计算字母左边右边数字之和
#include<stdio.h>
int main(){int max=-1;int left_sum=0;int right_sum=0;int len=0;char str[1000]={0};char *p=str;scanf("%s",str);while(*p>='0'&&*p<='9'){p++;left_sum++;}while(*p!='\0'){p++;right_sum=0;while(*p>'0'&&*p<'9'){p++;right_sum++;}len=left_sum+right_sum+1;max=(len>max)?len:max;left_sum=right_sum;}printf("%d",max);return 0;
}