0418：屏幕可显示句子的数量（★★）

2016-02-22 约 543 字预计阅读 2 分钟次阅读

力扣第 418 题

题目

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

注意：

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

示例 1：

输入：
rows = 2, cols = 8, 句子 sentence = ["hello", "world"]

输出：
1

解释：
hello---
world---

字符 '-' 表示屏幕上的一个空白位置。

示例 2：

输入：
rows = 3, cols = 6, 句子 sentence = ["a", "bcd", "e"]

输出：
2

解释：
a-bcd-
e-a---
bcd-e-

字符 '-' 表示屏幕上的一个空白位置。

示例 3：

输入：
rows = 4, cols = 5, 句子 sentence = ["I", "had", "apple", "pie"]

输出：
1

解释：
I-had
apple
pie-I
had--

字符 '-' 表示屏幕上的一个空白位置。

分析

假如 cols 足够放 q 个完整句子，那么可以提前将每一行的 q 个完整句子挖掉，相应地减少 cols
按顺序放，令 d[x]=i 代表第 i 行行头的单词是句子中第 x 个单词
显然 x 的值有限，因此有限行之后，必然进入循环
计算出一个循环中放了多少个完整句子，即可快速得到 rows 行的结果

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:  
    def cal(x):  
        pos, w = -1, 0  
        while pos + A[x] + 1 <= cols:  
            pos += A[x] + 1  
            w += int(x == n - 1)  
            x = (x + 1) % n  
        return x, w  
  
    A, n = [len(s) for s in sentence], len(sentence)  
    q, cols = divmod(cols, sum(A) + n)  
    d, x, pre = {}, 0, [0]  
    for j in range(rows):  
        if x in d:  
            i = d[x]  
            s = pre[-1] - pre[i]  
            _q, _r = divmod(rows-i, j-i)  
            return q*rows + s*_q + pre[i+_r]  
        d[x] = j  
        x, w = cal(x)  
        pre.append(pre[-1]+w)  
    return q * rows + pre[-1]

32 ms

目录

0418：屏幕可显示句子的数量（★★）

题目

分析

解答