算法模拟

通过已知的循环节优化模拟过程

字数统计: 1.6k字   |   阅读时长: 6分
,

摘要: 循环节与计数问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于一些计数问题，通过模拟发现循环节可以算是一种找规律的技巧，只是这里的规律是循环节。参考 计数DP。

拿到问题的时候我们并不知道有没有循环节，通过对规模较小的数据进行分析，比如 $f(1), f(2), \cdots$，可能会发现当规模变大时，结果呈周期性，也就是循环节，于是就可以提出关于最小循环节的猜想，进而解决问题。

题目

给你一个 rows x cols 的屏幕和一个用 非空 的单词列表组成的句子，请你计算出给定句子可以在屏幕上完整显示的次数。

注意：

1
2
3
4
5
6
一个单词不能拆分成两行。
单词在句子中的顺序必须保持不变。
在一行中 的两个连续单词必须用一个空格符分隔。
句子中的单词总量不会超过 100。
每个单词的长度大于 0 且不会超过 10。
1 <= rows, cols <= 20,000.

示例 1：
输入：
rows = 2, cols = 8, 句子 sentence = [“hello”, “world”]
输出：
1
解释：

1
2
hello---
world---

示例 2：
输入：
rows = 3, cols = 6, 句子 sentence = [“a”, “bcd”, “e”]
输出：
2
解释：

1
2
3
a-bcd- 
e-a---
bcd-e-

示例 3：
输入：
rows = 4, cols = 5, 句子 sentence = [“I”, “had”, “apple”, “pie”]
输出：
1
解释：

1
2
3
4
I-had
apple
pie-I
had--

题解

算法1：模拟

最朴素的算法，直接按照要求，逐行逐词地模拟。

$i$ 表示行，$j$ 表示列。在推进 $i, j$ 时，维护一个 $iter$ 表示当前在 sentence 中的第 $iter$ 个单词。

对于当前位置 $(i, j)$，首先求当前行剩余的位置数 $remain = cols - j$（剩余范围 $[j, cols - 1]$）。下一个单词长度为 $nxtlen$。

对于 $remain < nxtlen$ 的情况，如果 $j = 0$，那么当前词根本不可能插入。返回 0。如果 $j > 0$ 则当前行无法插入当前单词，在新的行插入，然后继续。

对于 $remain \geq nxtlen$ 的情况，当前词肯定可以插入到当前行。做相应的更新，然后继续推进 $(i, j)$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 最朴素的模拟： 逐行，逐词
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int ans = 0;
        int i = 0;
        int iter = 0; // 当前在 sentence 中的位置
        int N = sentence.size();
        while(i < rows)
        {
            int j = 0;
            while(j < cols)
            {
                int remain = cols - j;
                int nxt_len = sentence[iter].size();
                if(j == 0 && remain < nxt_len)
                    return 0;
                if(nxt_len > remain)
                    break;
                j += nxt_len;
                ++j; // 词跟词之间的空格
                ++iter;
                if(iter == N)
                {
                    ++ans;
                    iter = 0;
                }
            }
            ++i;
        }
        return ans;
    }
};

算法：在同一行中找循环节

朴素模拟基础上，在 $(i, j)$ 遇到句子重新开始时，直接求一次x = (当前行剩余空格数 + 1) / (句子单词总长 + 单词个数)，表示第 $i$ 行，从 $j$ 开始可以塞多少个完整 sentence。

例如剩余 17 空位，2 个词，一个长 2 ，一个长 4，则计算式为 x = (15 + 1) / (2 + 4 + 2) = 2。

1
xx_yyyy_xx_yyyy__ (共占 15 个位)

则在第 $i$ 行，下一个位置为 j + (句子单词总长 + 单词个数) * x - 1。还是看上面的例子，下一个位置为 j + (2 + 4 + 2) * 2 = j + 16。

这样的话在每一行，最多只需要遍历 sentence 中的单词 1 次即可。如果列数很多，通过前面的公式可以直接将 $j$ 推进到靠后的位置。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int ans = 0;
        int i = 0;
        int iter = 0; // 当前在 sentence 中的位置
        int N = sentence.size();
        int len_s = 0; // 句子单词总长 + 单词个数(每个词末尾一个空格)
        for(const string &w: sentence)
        {
            if((int)w.size() > cols)
                return 0;
            len_s += (w.size()) + 1;
        }
        while(i < rows)
        {
            int j = 0;
            while(j < cols)
            {
                int remain = cols - j;
                if(iter == 0)
                {
                    int x = (remain + 1) / (len_s);
                    if(x > 0)
                    {
                        j += len_s * x;
                        remain = cols - j;
                        ans += x;
                    }
                }
                int nxt_len = sentence[iter].size();
                if(nxt_len > remain)
                    break;
                j += nxt_len;
                ++j; // 词跟词之间的空格
                ++iter;
                if(iter == N)
                {
                    ++ans;
                    iter = 0;
                }
            }
            ++i;
        }
        return ans;
    }
};

算法3：循环节

如果 $rows$ 行 $cols$ 列组织成 $rows \times cols$ 的宽度，直接用宽度除以句子加上空格的长度之和，可以快速的得到能装下的个数。

难点在于每行可能会有一些剩下的空格不足以放下一个单词，所以并不是每个位子都是可用的，我们需要记录有效空位的个数。

首先将 sentence 从单词数组转换为一个字符串 all 的形式。例如 sentence 为 word1, word2，那么转换为的字符串为 all = word1 + 空格 + word2 + 空格，all 的长度记为 $len$。

枚举每一行，然后计算每一行对有效空格数的贡献。大致思路是首先将一行所有的空格加入到有效空格中，然后再删除。

假设当前在第 $i$ 行，$i - 1$ 行的有效宽度已经得到，为 $valid$，此时将当前行所有空格都视为有效宽度，即 valid += cols。在当前的 valid 宽度上塞满 sentence，然后从 $valid[-1]$ 开始检查是否有效。

如果 all[valid % len] == ' '，那么 valid 的宽度内刚好填满了词，如果到这里就结尾了，后面就不用再加空格了，但是如果还没到结尾，好需要继续后面的行去算有效空位个数，此时还是要加上一个空格的。也就是 valid++。

否则，valid 宽度的末尾有无效空格，一位一位地判断，删除即可，删除无效空格即 valid--。示意图如下：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string all = "";
        for (string word : sentence) 
            all += (word + " ");
        int len = all.size();
        int valid = 0;
        for (int i = 0; i < rows; ++i) 
        {
            valid += cols;
            if (all[valid % len] == ' ')
            {
                // 当 all[valid % len] == ' ' 的时候，此时 valid 应该自增1
                // 因为虽然 valid 的宽度内填满了词，后面不用再加空格了，但是我们再算有效空位个数的时候还是要加上这个空格的。
                ++valid;
            }
            else
            {
                // 移除不合法的空位
                while (valid > 0 && all[(valid - 1) % len] != ' ')
                {
                    --valid;
                }
            }
        }
        return valid / len;
    }
};
Share