文本左右对齐
学习
一、题目
这个问题是一个典型的文本排版问题。
二、解题思路
- 初始化:创建一个结果列表result来存储每一行的文本,以及一个临时列表current_line来存储当前正在构建的行的单词。
- 贪心算法填充:遍历words数组,使用贪心算法尽可能多地将单词放入current_line,直到无法再添加更多单词而不超出maxWidth。
- 分配空格:当current_line中的单词不能再添加更多单词时,计算需要添加的空格数以使该行的总长度达到maxWidth。如果单词间的空格不能均匀分配,则左侧多于右侧。
- 构建行:根据计算出的空格数,构建当前行的文本,并添加到result中。
- 最后一行特殊处理:对于最后一行,如果是左对齐,且单词之间不插入额外的空格。
- 返回结果:完成所有行的构建后,返回result列表。
python代码
def fullJustify(words, maxWidth): result = [] i = 0 while i < len(words): count = 0 # 记录当前行单词的数量 width = 0 # 当前行的总宽度 for j in range(i, len(words)): if width + len(words[j]) + count <= maxWidth: count += 1 width += len(words[j]) else: break line = [] if count == 1 or i + count == len(words): # 如果只有1个单词或最后一行 line = ' '.join(words[i:i + count]) else: # 多于1个单词且不是最后一行 spaces = maxWidth - width spaceBetween = spaces // (count - 1) # 每个单词间空格数 extraSpaces = spaces % (count - 1) # 多出的空格数 for j in range(count): line.append(words[i + j]) if j < count - 1: line.extend([' '] * (spaceBetween + (1 if extraSpaces > 0 else 0))) if extraSpaces > 0: extraSpaces -= 1 result.append(''.join(line)) i += count # 移动到下一行的开始 return result # 示例用法 if __name__ == "__main__": words1 = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth1 = 16 for line in fullJustify(words1, maxWidth1): print(line) words2 = ["What", "must", "be", "acknowledgment", "shall", "be"] maxWidth2 = 16 for line in fullJustify(words2, maxWidth2): print(line) words3 = ["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer", ".", "Art", "is", "everything", "else", "we", "do"] maxWidth3 = 20 for line in fullJustify(words3, maxWidth3): print(line) # 示例用法 words1 = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth1 = 16 print("\n".join(fullJustify(words1, maxWidth1))) words2 = ["What", "must", "be", "acknowledgment", "shall", "be"] maxWidth2 = 16 print("\n".join(fullJustify(words2, maxWidth2))) words3 = ["Science", "is", "what", "we", "understand", "well", "enough", "to", "explain", "to", "a", "computer.", "Art", "is", "everything", "else", "we", "do"] maxWidth3 = 20 print("\n".join(fullJustify(words3, maxWidth3)))
C++代码
给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右