LeetCode 418 C语言如何实现单词屏幕排版？

这是一个经典的模拟题，关键在于理解其数学规律，从而避免超时。 描述

给定一个 rows x cols 的屏幕和一个句子（列表形式的字符串），你需要将句子逐行地显示在屏幕上,句子中的单词必须按顺序显示。

• 同一行中,单词与单词之间至少需要一个空格。
• 如果一行放不下一个完整的单词，就换行。
• 如果一行放不下一个完整的句子，就换行并开始一个新的句子。
• 当屏幕被单词填满后，不再显示任何单词。

你的任务是计算屏幕上可以显示多少个完整的句子。

示例:

rows = 3, cols = 6
sentence = ["a", "bcd", "e"]

解释:

a bcd e
a bcd e
a bcd e

答案是 3。

解题思路

暴力模拟（会超时）

最直观的想法是逐行、逐个单词地进行模拟：

1. 初始化一个指针 word_index,表示当前应该显示句子中的第几个单词。
2. 遍历每一行 i 从 0 到 rows-1： a. 从 word_index 开始，尝试将单词填入当前行。 b. 如果当前行剩余空间 cols 小于下一个单词的长度，说明放不下，换行。word_index 保持不变，进入下一行的循环。 c. 如果放得下，就从 cols 中减去单词的长度和 1 个空格（如果是行首单词，则不加空格）。 d. word_index 移动到下一个单词。 e. word_index 超出句子长度，说明一个句子显示完了，计数器 sentence_count 加一，并将 word_index 重置为 0。
3. 最后返回 sentence_count。

为什么这个方法会超时？ 因为当 rows 和 cols 非常大时（rows = 2 * 10^4, cols = 2 * 10^7），这个逐行模拟的效率太低,会超出时间限制。

优化思路：寻找循环

我们需要找到一种方法，能够一次性计算出多行可以显示多少个句子,而不是一行一行地模拟。

观察这个过程，word_index 在 [0, sentence.length) 之间循环，当 word_index 回到某个已经出现过的值时，就意味着进入了一个循环,我们可以利用这个循环来加速计算。

核心思想：

1. 预处理：创建一个数组 next_word_start，next_word_start[i] 表示，如果一行从句子中的第 i 个单词开始，那么这一行结束后，下一行应该从第 j 个单词开始，这个 j 可以通过一次模拟快速计算出来。
2. 循环检测与计算：在遍历行数的过程中，我们记录下 word_index 每次出现的位置，如果发现某个 word_index 重复出现，就找到了一个循环。 a. 计算出循环的长度（多少行构成一个循环）。 b. 计算出循环内可以显示多少个句子。 c. 用总行数减去已经遍历的非循环行数，然后除以循环长度，得到可以跳过多少个完整的循环。 d. 快速加上这些循环贡献的句子数。 e. 再处理剩余的、不足以构成一个循环的行数。

C 语言代码实现

下面是结合了上述优化思路的 C 语言代码。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 辅助函数：计算如果一行从第 start_idx 个单词开始，这一行结束后，下一行应该从哪个单词开始
// 返回这一行中包含的句子数量
int getNextWordStart(char** sentence, int sentenceSize, int cols, int start_idx, int* sentences_in_row) {
    int current_col = 0;
    *sentences_in_row = 0;
    int i = start_idx;
    // 模拟填充一行
    while (current_col < cols) {
        int word_len = strlen(sentence[i % sentenceSize]);
        // 如果当前行放不下这个单词（即使是第一个单词），则跳出循环
        if (current_col + word_len > cols) {
            break;
        }
        // 更新列数：加上单词长度和后面的空格（如果不是行首）
        current_col += word_len;
        i++;
        // 如果一个句子显示完了
        if (i % sentenceSize == 0) {
            (*sentences_in_row)++;
        }
        // 如果不是行尾，加上一个空格
        if (current_col < cols) {
            current_col++;
        }
    }
    // 返回下一行开始的单词索引（对 sentenceSize 取模）
    return i % sentenceSize;
}
int wordsTyping(char** sentence, int sentenceSize, int rows, int cols) {
    // 创建一个数组，记录从每个单词开始一行后，下一行开始的单词索引
    int* next_word_start = (int*)malloc(sentenceSize * sizeof(int));
    // 创建一个数组，记录从每个单词开始一行后，这一行中包含的句子数量
    int* sentences_in_row = (int*)malloc(sentenceSize * sizeof(int));
    // 预处理：计算从每个单词开始一行的结果
    for (int i = 0; i < sentenceSize; i++) {
        next_word_start[i] = getNextWordStart(sentence, sentenceSize, cols, i, &sentences_in_row[i]);
    }
    int total_sentences = 0;
    int current_word_start = 0; // 从第 0 个单词开始
    // 遍历每一行
    for (int i = 0; i < rows; i++) {
        // current_word_start 已经被计算过，说明我们遇到了一个循环
        if (sentences_in_row[current_word_start] > 0) {
            // 找到循环开始的位置
            int loop_start_word = current_word_start;
            int loop_rows = 0;
            int loop_sentences = 0;
            // 从循环开始位置出发，直到再次回到 loop_start_word，找到循环的长度
            do {
                loop_sentences += sentences_in_row[current_word_start];
                current_word_start = next_word_start[current_word_start];
                loop_rows++;
            } while (current_word_start != loop_start_word);
            // 计算剩余的行数
            int remaining_rows = rows - i;
            // 计算可以跳过多少个完整的循环
            total_sentences += (remaining_rows / loop_rows) * loop_sentences;
            // 更新当前行数，跳过这些循环
            i += (remaining_rows / loop_rows) * loop_rows - 1; // -1 因为 for 循环最后会 i++
            // 如果循环结束后行数已用完，则跳出
            if (i >= rows - 1) {
                break;
            }
        }
        // 如果不是循环部分，或者循环处理完后，正常处理当前行
        total_sentences += sentences_in_row[current_word_start];
        current_word_start = next_word_start[current_word_start];
    }
    free(next_word_start);
    free(sentences_in_row);
    return total_sentences;
}
// --- 测试代码 ---
int main() {
    // 示例 1
    char* sentence1[] = {"a", "bcd", "e"};
    int rows1 = 3, cols1 = 6;
    printf("示例 1: %d\n", wordsTyping(sentence1, 3, rows1, cols1)); // 预期输出: 3
    // 示例 2
    char* sentence2[] = {"hello", "world"};
    int rows2 = 2, cols2 = 8;
    printf("示例 2: %d\n", wordsTyping(sentence2, 2, rows2, cols2)); // 预期输出: 1
    // 示例 3
    char* sentence3[] = {"I", "had", "apple", "pie"};
    int rows3 = 4, cols3 = 5;
    printf("示例 3: %d\n", wordsTyping(sentence3, 4, rows3, cols3)); // 预期输出: 1
    // 示例 4 (LeetCode官方样例)
    char* sentence4[] = {"f","p","a"};
    int rows4 = 8, cols4 = 7;
    printf("示例 4: %d\n", wordsTyping(sentence4, 3, rows4, cols4)); // 预期输出: 10
    return 0;
}

代码逻辑分解

1. getNextWordStart 函数:

   • 这是核心的模拟函数，但它只模拟一行。
   • 输入：sentence (单词数组), sentenceSize (单词数量), cols (列数), start_idx (本行开始的单词索引)。
   • 输出：本行结束后，下一行开始的单词索引（对 sentenceSize 取模）。
   • 通过指针参数 sentences_in_row 返回本行中完整显示的句子数。

2. wordsTyping 函数:

   • 预处理:
     • 分配 next_word_start 和 sentences_in_row 数组，大小为句子长度 sentenceSize。
     • 循环 i 从 0 到 sentenceSize-1，调用 getNextWordStart 填充这两个数组，这意味着我们预先计算好了“如果一行从第 i 个单词开始”的所有情况。
   • 主循环 (遍历行):
     • total_sentences 用于累计总句子数。
     • current_word_start 记录当前行是从句子中的哪个单词开始的，初始为 0。
     • for (int i = 0; i < rows; i++) 遍历每一行。
   • 循环检测与处理:
     • if (sentences_in_row[current_word_start] > 0)：这个判断是关键，如果从 current_word_start 开始的一行可以显示至少一个完整的句子（>0），那么它后面必然跟着一个确定的 next_word_start,这为形成循环提供了基础。
     • do-while 循环：用来找到真正的循环，它从 current_word_start 出发，沿着 next_word_start 的路径走，直到再次回到起点，这个过程记录了循环的行数 loop_rows 和循环内显示的句子数 loop_sentences。
     • 快速计算：
       • remaining_rows = rows - i;：还剩下多少行没处理。
       • total_sentences += (remaining_rows / loop_rows) * loop_sentences;：直接跳过所有完整循环，并加上它们贡献的句子数，这是时间复杂度从 O(rows) 降低到 O(sentenceSize) 的关键。
       • i += ... - 1;：手动增加 i，以跳过那些被快速处理的循环行。-1 是因为 for 循环本身会在末尾执行 i++。
   • 正常处理:
     • 如果不是循环部分，或者循环处理后还有剩余的行,就正常处理。
     • total_sentences += sentences_in_row[current_word_start];：加上当前行显示的句子数。
     • current_word_start = next_word_start[current_word_start];：更新为下一行开始的单词索引。
   • 内存释放与返回:
     • free 掉动态分配的数组。
     • 返回 total_sentences。

复杂度分析

• 时间复杂度: O(sentenceSize + rows)
  • 预处理阶段需要遍历所有单词作为起点，调用 getNextWordStart 函数。getNextWordStart 内部虽然是个循环，但由于 cols 是固定的，其时间可以看作是常数，所以预处理是 O(sentenceSize)。
  • 主循环中，虽然外面有个 for (rows) 循环，但由于我们检测到循环后会进行“跳跃”，所以内部 do-while 循环在整个 rows 的遍历过程中最多只会执行 sentenceSize 次，因此主循环部分的总复杂度也是 O(sentenceSize)。
  • 综合来看，总时间复杂度为 O(sentenceSize + rows)，当 rows 远大于 sentenceSize 时，可以近似看作 O(rows)，但这已经比纯粹的 O(rows * cols) 好太多了。
• 空间复杂度: O(sentenceSize)
  • 我们使用了两个大小为 sentenceSize 的数组 next_word_start 和 sentences_in_row 来存储预处理结果。