leetcode
leetcode 351 ~ 400
屏幕可显示句子的数量

屏幕可显示句子的数量

难度:

标签:

题目描述

代码结果

运行时间: 95 ms, 内存: 16.0 MB


/*
 * 题目思路:
 * 使用Java Stream计算屏幕可显示句子的数量。
 * 将句子连接成一个字符串,在屏幕上尽量显示这个字符串的内容,计算完整显示的句子数量。
 */
import java.util.stream.IntStream;
 
public class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int len = s.length();
        int[] start = {0};
        IntStream.range(0, rows).forEach(i -> {
            start[0] += cols;
            if (s.charAt(start[0] % len) == ' ') {
                start[0]++;
            } else {
                while (start[0] > 0 && s.charAt((start[0] - 1) % len) != ' ') {
                    start[0]--;
                }
            }
        });
        return start[0] / len;
    }
}

解释

方法:

这个题解的思路是先把句子数组拼接成一个长字符串,每个单词之间用空格隔开。然后模拟在屏幕上填充这个长字符串,同时记录填充的有效空格数。最后用有效空格数除以长字符串的长度,就可以得到句子在屏幕上重复的次数。在模拟填充的过程中,如果当前行放不下下一个单词,就需要把当前行剩余的空格略过,把下一个单词放到下一行。

时间复杂度:

O(max(mw, rows * cols))

空间复杂度:

O(mw)

代码细节讲解

🦆
在算法中,如果一个单词长度超过屏幕列数,直接返回0的逻辑是基于什么考虑?
这个逻辑是基于屏幕无法显示整个单词的现实限制。如果句子中的任何一个单词长度超过了屏幕的列数,那么该单词无法在屏幕上完整显示,也就不可能在任何行中完整地显示这个单词。因此,整个句子也无法在屏幕上循环显示,所以直接返回0是为了避免进一步无效的计算。
🦆
为什么在拼接句子时每个单词后要添加一个空格,这对算法的逻辑有什么影响?
在拼接句子时每个单词后添加一个空格是为了模拟句子在屏幕上的实际显示方式,其中单词之间通常需要有空格分隔。这样做可以确保在计算每行可以容纳的单词数时能够准确地处理单词间的间隔。这对算法的逻辑有关键影响,因为它使得整个句子可以作为一个连续的循环字符串来处理,而且在模拟填充过程中可以更简单地判断何时一个单词结束并转向下一个单词。
🦆
在计算重复次数时,为什么使用有效空格数除以整个字符串长度,这种方法的准确性如何保证?
使用有效空格数除以整个字符串长度来计算重复次数是基于整个字符串(包括单词和它们之间的空格)被视为一个循环单位的原理。每次整个字符串长度的有效空格被填满,意味着句子重复了一次。这种方法的准确性由算法设计保证,确保每轮循环结束时,都恰好完成了一个或多个完整的字符串的循环,精确地计算了句子在给定行和列限制下可以重复的次数。
🦆
在循环模拟填充过程中,减小有效空格数直到找到空格字符是为了解决什么问题?
这个操作是为了解决当当前行剩余的空间不足以容纳下一个单词时的问题。如果在当前行填充时达到或超过行的界限,而在那一点上的字符不是空格(意味着它是单词的一部分),则需要回退到最后一个空格字符。这样做可以确保不会将一个单词拆分到两行显示,避免了单词的断裂显示。通过这种方式,算法确保每行都只显示完整的单词,维持了显示的整洁和正确性。

相关问题