给定一个字符串，在字符串中找到第一个连续出现至少k次的字符。C语言

可以使用哈希表来解决这个问题。首先需要遍历一遍字符串，统计每个字符出现的次数，然后再遍历一遍字符串，找到第一个出现至少k次的字符。

以下是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次的字符的位置。

以下是一个简化的代码示例：

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

给定一个字符串，在字符串中找到第一个连续出现至少k次的字符。 输入格式: 第一行包含一个正整数k，表示至少需要连续出现的次数。1 <= k <= 100。 第二行包含需要查找的字符串。字符串长度在1到100之间，且不包含任何空白符。用C语言作答

在C语言中，要解决这个问题，你可以使用滑动窗口或哈希表的策略。这里是一个简单的滑动窗口方法的思路：

#include <stdio.h>
#include <string.h>

int findKthChar(char str[], int k) {
    int n = strlen(str);
    int window_start = 0, count = 0;
    char prev_char = '\0'; // 初始化为前一个字符

    for (int window_end = 0; window_end < n; window_end++) {
        if (str[window_end] == prev_char) { // 如果字符相同
            count++; // 增加计数
        } else {
            count = 1; // 当字符变化时，重置计数
        }

        if (count >= k) { // 如果计数达到k，找到了目标
            return window_end; // 返回窗口右边界
        }

        prev_char = str[window_end]; // 更新前一个字符
    }

    return -1; // 如果没有找到连续出现至少k次的字符，返回-1
}

int main() {
    int k;
    scanf("%d", &k);

    char str[101];
    fgets(str, sizeof(str), stdin); // 注意处理换行符
    str[strlen(str) - 1] = '\0'; // 去掉换行符

    int result = findKthChar(str, k);
    if (result != -1) {
        printf("第一个连续出现至少 %d 次的字符的索引是: %d\n", k, result);
    } else {
        printf("没有找到连续出现至少 %d 次的字符。\n", k);
    }

    return 0;
}