当前位置：首页 > article >正文

算法练习题：文本左右对齐

article 2024/11/15 10:58:49

文本左右对齐

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

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

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

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

要实现这个功能，我们可以按照以下步骤进行：

1、初始化一个空的结果数组 result。
2、遍历单词数组 words，将每个单词添加到当前行中，直到当前行的字符数加上下一个单词的长度超过 maxWidth。
3、如果当前行只有一个单词或者已经到达单词数组的末尾，则直接将当前行添加到结果数组中。
4、否则，计算当前行需要填充的空格数量，并均匀分配到单词之间。如果不能均匀分配，左侧的空格多于右侧。
5、将格式化后的当前行添加到结果数组中，并重置当前行为空。
6、重复步骤2-5，直到处理完所有单词。
7、返回结果数组。
以下是实现这个功能的 JavaScript 代码示例：

function fullJustify(words, maxWidth) {
    let result = [];
    let currentLine = [];
    let currentLength = 0;

    for (let word of words) {
        if (currentLength + word.length + currentLine.length > maxWidth) {
            let spaces = maxWidth - currentLength;
            let extraSpaces = currentLine.length > 1 ? spaces % (currentLine.length - 1) : 0;
            let spaceBetween = spaces / (currentLine.length - 1) || 0;
            let line = '';

            for (let i = 0; i < currentLine.length; i++) {
                line += currentLine[i];
                if (i < currentLine.length - 1) {
                    line += ' '.repeat(spaceBetween);
                    if (extraSpaces > 0) {
                        line += ' ';
                        extraSpaces--;
                    }
                }
            }

            result.push(line);
            currentLine = [word];
            currentLength = word.length;
        } else {
            currentLine.push(word);
            currentLength += word.length;
        }
    }

    let lastLine = currentLine.join(' ').trim();
    lastLine += ' '.repeat(maxWidth - lastLine.length);
    result.push(lastLine);

    return result;
}

// Example usage:
const words = ["This", "is", "an", "example", "of", "text", "justification."];
const maxWidth = 16;
console.log(fullJustify(words, maxWidth));

这段代码首先定义了一个名为 fullJustify 的函数，它接受一个单词数组 words 和一个整数 maxWidth 作为参数。函数的主体部分使用贪心算法来构建每一行的文本，并在最后一行左对齐。最后，函数返回一个包含所有格式化行的数组。

下面是实现这个算法的 Python 代码示例：

def fullJustify(words, maxWidth):
    def justify_line(line, maxWidth):
        if len(line) == 1:
            return line[0] + ' ' * (maxWidth - len(line[0]))
        
        total_spaces = maxWidth - sum(len(word) for word in line)
        space_between = total_spaces // (len(line) - 1)
        extra_spaces = total_spaces % (len(line) - 1)
        
        justified_line = []
        for i in range(len(line) - 1):
            justified_line.append(line[i])
            justified_line.append(' ' * space_between)
            if extra_spaces > 0:
                justified_line.append(' ')
                extra_spaces -= 1
        
        justified_line.append(line[-1])
        return ''.join(justified_line)
    
    result = []
    current_line = []
    current_length = 0
    
    for word in words:
        if current_length + len(word) + len(current_line) > maxWidth:
            result.append(justify_line(current_line, maxWidth))
            current_line = []
            current_length = 0
        
        current_line.append(word)
        current_length += len(word)
    
    last_line = ' '.join(current_line)
    result.append(last_line + ' ' * (maxWidth - len(last_line)))
    
    return result

# Example usage:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
print(fullJustify(words, maxWidth))