Ricky.L的随笔
0%

LeetCode.68.文本左右对齐（困难）

发表于 更新于 分类于 Disqus：

题目

LeetCode.68.文本左右对齐（困难）

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

题解

顺着题目说明思考步骤。

怎么知道一行可以放多少个单词？

依次遍历单词，累加单词长度，跟maxWidth对比，找出一行可以容纳的最多的单词。

如果一行有n个单词，要注意，前n - 1个单词末尾都要至少有一个空格，需要考虑进去。

如何知道每行有多少个空格？

maxWidth - 这一行所有单词长度

如何平均分配空格到每个单词的末尾？

假设一行的空格数有spaceCount，一行可以放置的单词有n个。

  • 只有前n - 1个单词的末尾需要分配空格。
  • 按照平均分配的原则，每个单词末尾的空格数应当为spaceCount / (n - 1)。
  • 如果spaceCount / (n - 1)不能整除，说明一行单词间的空格不能均匀分配，按照题意，左侧放置的空格数要多于右侧的空格数。
    • 多出来的空格数是spaceCount % (n - 1)，从左到右给每个单词末尾加一个空格，均匀掉。

边界情况

  • 对于最后一行，按照题意：文本的最后一行应为左对齐，且单词之间不插入额外的空格。，同时末尾要全部填满空格。
  • 对于一行只有一个单词，空格只能全部填在末尾，让单词左对齐。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    fun fullJustify(words: Array<String>, maxWidth: Int): List<String> {
        val result = mutableListOf<String>()
        val n = words.size
        var i = 0
        while (i < n) {
            // >>> 统计一行能放多少个单词
            
            // 这一行所有单词的长度
            var wordsLength = 0
            var j = i
            // 每个单词末尾一个空格数量的累加为 j - i
            while (j < n && wordsLength + words[j].length + j - i <= maxWidth) {
                wordsLength += words[j].length
                j++
            }
            // <<<

            // >>> 最后一行单独处理，因为处理空格的逻辑跟普通行不一样，所以放在普通行处理空格的前面
            if (j == n) {
                val line = StringBuilder()
                for (k in i until j) {
                    if (line.isNotEmpty()) line.append(" ")
                    line.append(words[k])
                }
                for (i in line.length until maxWidth) {
                    line.append(" ")
                }
                result.add(line.toString())
                break
            }
            // <<< 

            // >>> 平均分配空格到单词末尾
            val line = StringBuilder()
            val wordCount = j - i
            val spaceLength = if (wordCount == 1) 0 else (maxWidth - wordsLength) / (wordCount - 1)
            var extraSpaceLength = if (wordCount == 1) 0 else (maxWidth - wordsLength) % (wordCount - 1)
            for (k in i until j) {
                // 空格分配在每个单词前面
                if (line.isNotEmpty()) {
                    repeat(spaceLength) { line.append(" ") }
                    if (extraSpaceLength > 0) {
                        line.append(" ")
                        extraSpaceLength--
                    }
                }
                line.append(words[k])
            }
            // <<< 

            // 对于一行只有一个单词和最后一行，末尾填充空格
            for (i in line.length until maxWidth) {
                line.append(" ")
            }   

            // 添加一行的结果
            result.add(line.toString())

            i = j
        }

        return result
    }
}