学校网站模板wordpress,重庆网站设计找重庆最佳科技,搬家公司网站建设价格,中国沈阳网站在哪里下载题目
字符串 题目又叫字符串#xff0c;但是这道题是真正的关于字符串的题 思路
这道题可行的我能想出来的思路有两个#xff0c;一个是二分#xff0c;先猜测一个答案#xff0c;然后验证这个答案#xff0c;但是由于这种方法时间复杂度不如另一种方法#xff1a;双指…题目
字符串 题目又叫字符串但是这道题是真正的关于字符串的题 思路
这道题可行的我能想出来的思路有两个一个是二分先猜测一个答案然后验证这个答案但是由于这种方法时间复杂度不如另一种方法双指针滑动窗口所以这里不做记录只记录双指针的方法 设置两个指针一个指针 j j j 标记符合题意的最短字符串的开始另一个指针 i i i 标记字符串结尾都是能取到的闭区间所以字符串长度就是 i − j 1 i-j1 i−j1初始时两个指针都在字符串开始处 0 0 0然后让指针 i i i 往前走直到找出一个符合题意的字符串此时这个指针标记着字符串的结尾然后指针 j j j 也开始走直到走到第一个不符合题意的位置注意指针所在位置开始的字符串仍然是符合题意的然后更新答案的值。如此重复即可。 怎么表示一个子串是否符合题意呢 使用一个哈希表小写字母常用数组代替哈希表记录每个字符出现的次数即可由指针 i i i 遍历到的字符次数加 1 1 1由指针 j j j 遍历到的字符的次数减 1 1 1前提是减少之后不为 0 0 0 代码
#include stdio.h
#include string.h#define N 1000000 5
#define M 26/*** brief 判断当前子串是不是符合题意的** param st* param len* return int*/
int check(int* st, int len) {for (int i 0; i len; i) {if (!st[i]) return 0;}return 1;
}/*** brief 计算符合题意的子串最小长度** param s* return int*/
int solve(const char* s) {int i 0, j 0, ans N;int st[M] {0};while (s[i]) {st[s[i] - a];if (check(st, M)) {while (j i) {// 注意只有当移动了 j 之后还符合题意才移动if (st[s[j] - a] 1) {break;}st[s[j] - a]--;j;}if (i - j 1 ans) {ans i - j 1;}}i;}return ans;
}int main(void) {char s[N];scanf(%s, s);do {if (strlen(s) M) {printf(-114514\n);break;}printf(%d\n, solve(s));} while (0);return 0;
}
