首页 > 试题广场 >

文本对齐

[编程题]文本对齐

热度指数：9330 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个单词数组和长度L，将该单词数组中文本两端对齐(左边和右边)，使每一行都有L个字符。
你要在每一行中尽可能多地填充单词。在必要时填充额外的空格' '，使每行正好有L个字符。
单词之间的额外空格要尽可能均匀地分布。如果一行的空格数不能在单词之间平均分配，请在左边分配更多的空格
对于最后一行文本，它应该左对齐，并且单词之间不插入额外的空格。

例如,

单词数组为:["This", "is", "an", "instance", "of", "code", "alignment."]

L:16.

[
   "This    is    an",
   "instance of code",
   "alignment.  "
]

注意:

题目保证每个单词的长度不超过L。
特殊样例：

有一些行（不是最后一行）可能只包含一个单词。在这种情况下该怎么办? 在这种测试数据中，这一行应该左对齐。

算法知识视频讲解

Java

城市里的养猫者

def fullJustify(self, words, maxWidth): res, cur, num_of_letters = [], [], 0 for w in words: if num_of_letters + len(w) + len(cur) > maxWidth: for i in range(maxWidth - num_of_letters):
                cur[i%(len(cur)-1 or 1)] += ' ' res.append(''.join(cur))
            cur, num_of_letters = [], 0 cur += [w]
        num_of_letters += len(w) return res + [' '.join(cur).ljust(maxWidth)]

How does it work? Well in the question statement, the sentence "Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right" was just a really long and awkward way to say round robin. The following line implements the round robin logic:

for i in range(maxWidth - num_of_letters):
                cur[i%(len(cur)-1 or 1)] += ' '

What does this line do? Once you determine that there are only k words that can fit on a given line, you know what the total length of those words is num_of_letters. Then the rest are spaces, and there are (maxWidth - num_of_letters) of spaces. The "or 1" part is for dealing with the edge case len(cur) == 1.

The following is my older solution for reference, longer and less clear. The idea is the same, but I did not figure out the nice way to distribute the space at the time.

def fullJustify(self, words, maxWidth): res, cur, num_of_letters = [], [], 0 for w in words: if num_of_letters + len(w) + len(cur) > maxWidth: if len(cur) == 1: res.append( cur[0] + ' '*(maxWidth - num_of_letters) ) else:
                num_spaces = maxWidth - num_of_letters
                space_between_words, num_extra_spaces = divmod( num_spaces, len(cur)-1) for i in range(num_extra_spaces):
                    cur[i] += ' ' res.append( (' '*space_between_words).join(cur) )
            cur, num_of_letters = [], 0 cur += [w]
        num_of_letters += len(w) res.append( ' '.join(cur) + ' '*(maxWidth - num_of_letters - len(cur) + 1) ) return res