力扣第38题：外观数列（C语言解法）

力扣第38题：外观数列（C语言解法）

题目描述

报数序列是一个整数序列，按照如下规则生成：

1. countAndSay(1) 为字符串 "1"。
2. countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个字符串。

具体描述方式如下：对上一个字符串，从左到右遍历其中连续的相同字符，并将其数量和字符本身连接形成新的字符串。例如：

• 1 读作 "一1" -> 11
• 11 读作 "二1" -> 21
• 21 读作 "一2一1" -> 1211
• 1211 读作 "一1一2二1" -> 111221

示例：

输入：n = 4
输出："1211"
解释：countAndSay(1) = "1"
         countAndSay(2) = "11"
         countAndSay(3) = "21"
         countAndSay(4) = "1211"

解题思路

题目的关键在于如何生成报数序列。观察示例可以发现，每个报数序列描述的是上一个序列的内容。可以通过迭代生成每一个序列，避免递归带来的栈溢出问题。

思路如下：

1. 初始化第一个字符串为 "1"。
2. 从第 2 个到第 n 个序列，逐个生成每一个报数序列。
3. 遍历当前序列，统计连续相同字符的数量，将计数和字符依次拼接到新字符串。
4. 使用新生成的字符串作为下一次迭代的输入，最终获得第 n 个序列。

C语言代码实现

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

char* countAndSay(int n) {
    // 基本情况，返回第一个报数序列
    char* result = (char*)malloc(2 * sizeof(char));
    result[0] = '1';
    result[1] = '\0';

    // 从2到n，迭代生成每一个报数序列
    for (int i = 2; i <= n; i++) {
        int len = strlen(result);
        char* temp = (char*)malloc(2 * len + 1);  // 临时字符串
        int tempIndex = 0;

        for (int j = 0; j < len;) {
            int count = 1;
            while (j + count < len && result[j] == result[j + count]) {
                count++;  // 计算连续相同字符的数量
            }

            // 将数量和字符添加到临时字符串
            temp[tempIndex++] = '0' + count;
            temp[tempIndex++] = result[j];
            j += count;
        }
        temp[tempIndex] = '\0';

        // 用新的结果替换旧的结果
        free(result);
        result = temp;
    }

    return result;  // 返回最终的结果
}

int main() {
    int n = 4;
    char* result = countAndSay(n);
    printf("第 %d 个报数序列为: %s\n", n, result);
    free(result);  // 释放内存
    return 0;
}

代码解析

1. 初始报数序列

首先将 result 初始化为第一个序列 "1"。

char* result = (char*)malloc(2 * sizeof(char));
result[0] = '1';
result[1] = '\0';

2. 循环生成每个报数序列

从第 2 个到第 n 个序列，依次生成每一个报数序列。每次生成一个新序列时，遍历上一个序列的内容，对相同字符进行计数并将计数和字符依次拼接到新的字符串 temp 中。

for (int i = 2; i <= n; i++) {
    int len = strlen(result);
    char* temp = (char*)malloc(2 * len + 1);  // 临时字符串
    int tempIndex = 0;

3. 遍历当前字符串

在内层循环中，我们遍历当前的字符串 result，通过 count 变量统计连续相同字符的数量。

for (int j = 0; j < len;) {
    int count = 1;
    while (j + count < len && result[j] == result[j + count]) {
        count++;  // 计算连续相同字符的数量
    }

4. 将计数和字符拼接到新字符串

将字符 count（转化为字符）和 result[j] 添加到临时字符串 temp 中，并更新 tempIndex。

temp[tempIndex++] = '0' + count;
temp[tempIndex++] = result[j];
j += count;

5. 替换旧的字符串

生成新序列后，将 result 指向 temp 并释放原先的 result 字符串，以避免内存泄漏。

free(result);
result = temp;

6. 返回结果

循环完成后，result 即为所求的第 n 个报数序列。

注意事项

• temp 字符串分配大小为 2 * len + 1，这样确保有足够的空间容纳计数和字符。
• 每次生成新序列后释放旧的 result，防止内存泄漏。
• 该方法的时间复杂度为 $O(n\times m)$，其中 n 是目标序列的编号，m 是字符串的最大长度。