给定一个字符串,在字符串中找到第一个连续出现至少k次的字符。C语言
时间: 2024-01-28 19:07:51 浏览: 62
可以使用哈希表来解决这个问题。首先需要遍历一遍字符串,统计每个字符出现的次数,然后再遍历一遍字符串,找到第一个出现至少k次的字符。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <string.h>
#define MAXN 100005
#define MAXC 26
int cnt[MAXC]; // 记录每个字符出现的次数
int main() {
char s[MAXN];
int k;
scanf("%d %s", &k, s);
int n = strlen(s);
int l = 0, r = 0, ans = -1;
while (r < n) {
cnt[s[r] - 'a']++; // 统计字符出现次数
while (l <= r && cnt[s[r] - 'a'] >= k) { // 找到第一个出现至少k次的字符
if (ans == -1 || ans > l) ans = l; // 更新答案
cnt[s[l] - 'a']--; // 左指针右移,更新字符出现次数
l++;
}
r++;
}
printf("%d\n", ans);
return 0;
}
```
该算法的时间复杂度为$O(n)$,其中$n$为字符串的长度。
相关问题
给定一个字符串,在字符串中找到第一个连续出现至少k次的字符。用C语言作答
在C语言中,要找到一个字符串中第一个连续出现至少k次的字符,你可以使用滑动窗口和哈希表的方法。这里是一个简单的算法步骤:
1. 定义一个哈希表(或使用数组)来存储每个字符及其出现的次数。
2. 遍历字符串,对于每个字符,检查它在哈希表中的出现次数是否大于等于k。
3. 如果找到满足条件的字符,更新窗口开始和结束的位置,直到窗口结束的位置移动,且新窗口内的字符出现次数仍然大于等于k。
4. 当遍历完整个字符串后,返回窗口的开始位置,即为第一个连续出现至少k次的字符的位置。
以下是一个简化的代码示例:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_CHAR 256
// 哈希表,记录字符和出现次数
int char_count[MAX_CHAR] = {0};
char start = -1; // 最初的起始位置
int k;
// 更新字符计数
void update_char(char ch) {
if (ch != '\0') {
char_count[ch]++;
if (char_count[ch] >= k) {
start = (start == -1) ? 0 : start;
}
} else {
// 如果遇到'\0',清空计数,寻找下一个连续子串
for (int i = 0; i < MAX_CHAR; i++) {
if (char_count[i] > 0) {
char_count[i] = 0;
if (start != -1;
}
}
}
}
}
// 主函数
int main() {
const char *str = "abcccdeefgg";
int len = strlen(str);
k = 3; // 设置查找的最小连续出现次数
for (int i = 0; i < len; i++) {
update_char(str[i]);
}
if (start != -1) {
printf("第一个连续出现至少 %d 次的字符 '%c' 的位置是 %d\n", k, str[start], start + 1);
} else {
printf("没有找到连续出现至少 %d 次的字符\n", k);
}
return 0;
}
```
用c语言编写一个程序代码实现给定一个字符串,如果字符串中出现了"996"
,将其替换为"955",并输出替换后的字符串。
可以的,以下是代码示例:
```
#include <stdio.h>
#include <string.h>
int main()
{
char str[100];
printf("请输入一个字符串:");
scanf("%s", str);
char *p = strstr(str, "996");
if (p != NULL)
{
strncpy(p, "955", 3);
}
printf("替换后的字符串为:%s\n", str);
return 0;
}
```
这个程序可以实现给定一个字符串,如果字符串中出现了"996",将其替换为"955",并输出替换后的字符串。