文本左右对齐

题目

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

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

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

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

注意:

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

提示:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth

示例

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
  "This    is    an",
  "example  of text",
  "justification.  "
]

输入:words = ["What", "must", "be", "acknowledgment", "shall", "be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐, 而不是左右两端对齐。
     第二行同样为左对齐, 这是因为这行只包含一个单词。

输入:words = ["Science", "is", "what", "we", "understand", "well", "enough",
            "to", "explain", "to", "a", "computer.", "Art", "is", "everything",
            "else", "we", "do"], maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

题解

首先尽可能将 word 尽可能放到一行:

如果当前行是最后一行, 特殊处理为左对齐;
如果当前行只有一个单词, 特殊处理为左对齐;
其余为一般情况, 要尽可能均匀分配单词间的空格数量. 如果某一行单词间的空格不能均匀分配, 则左侧放置的空格数要多于右侧的空格数. 在无法均分时, 我们使用余数来巧妙的处理这种情况:

比如 line = ["Science", "is", "what", "we"], maxWidth = 20,

此时单词总长度是 15, 因此空格总长度是 5; 平摊的空格长度为 5 / 3 向下取整为 1; 但还余出两个来, 即 carry = 2,

因此在 "Science" 和 "is" 之间, 以及 "is" 和 "what" 之间, 除了要安置一个平摊的空格, 都要额外再增加一个空格, 即最终结果为 "Science is what we"

JavaScript
Rust
皮一下

/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function (words, maxWidth) {
  const result = []

  // 记录每行容纳的单词
  let line = []
  // 记录每行容纳单词的长度
  let lineWordsLength = 0

  for (const word of words) {
    // 如果加上当前 word, 即便每个单词的空隙为 1, 仍然超过 maxWidth, 那当前单词就不能加入该行了
    if (line.length + lineWordsLength + word.length > maxWidth) {
      // 如果该行最多只能容纳 1 个单词, 左对齐
      if (line.length === 1) {
        result.push(line[0] + ' '.repeat(maxWidth - lineWordsLength))

        // 一般情况下一行会容纳多个单词
      } else {
        // 计算需要放置多少个空格
        const totalSpaces = maxWidth - lineWordsLength
        // 计算间隙
        const gap = line.length - 1
        // 计算每个间隙要放置的基础空格
        const baseSpaces = Math.floor(totalSpaces / gap)
        // 每个间隙放置基础空格后, 还剩下多少个多余空格
        let extraSpaces = totalSpaces % gap

        // 从左到右遍历每一个间隙
        for (let i = 0; i < gap; i++) {
          // 除了放置基础空格, 如果还有多余空格, 左右到右每次多放一个
          line[i] += ' '.repeat(baseSpaces + (extraSpaces > 0 ? 1 : 0))
          extraSpaces--
        }
        result.push(line.join(''))
      }

      // 将当前遍历到 word 加入到下一行, 循环运算...
      line = [word]
      lineWordsLength = word.length
    } else {
      // 如果没超过 maxWidth, 加入该单词
      line.push(word)
      lineWordsLength += word.length
    }
  }

  // 说明还有最后一行, 左对齐
  if (lineWordsLength > 0) {
    const text = line.join(' ')
    result.push(text + ' '.repeat(maxWidth - text.length))
  }

  return result
}

pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> {
    let n = words.len();
    let mut res = vec![];
    let mut i = 0;

    while i < n {
        let mut line = vec![];

        let mut curr_line_width = words[i].len();
        line.push(words[i].to_string());
        i += 1;

        while i < n && curr_line_width + 1 + words[i].len() <= max_width as usize {
            curr_line_width += 1 + words[i].len();
            line.push(words[i].to_string());
            i += 1;
        }

        if i == n {
            let mut str = line.join(" ");
            for _ in 0..(max_width as usize - str.len()) {
                str += " ";
            }
            res.push(str);
        } else if i < n && line.len() == 1 {
            let mut str = line[0].to_string();
            for _ in 0..(max_width as usize - str.len()) {
                str += " ";
            }
            res.push(str);
        } else if i < n && line.len() > 1 {
            let total_word_width = curr_line_width - (line.len() - 1);
            let total_space_width = max_width as usize - total_word_width;

            let mut carry = total_space_width % (line.len() - 1);
            let space_item_width = total_space_width / (line.len() - 1);

            let mut space_item = String::new();
            for _ in 0..space_item_width {
                space_item += " ";
            }

            for i in 0..(line.len() - 1) {
                if carry > 0 {
                    line[i] += (space_item.to_string() + " ").as_str();
                    carry -= 1;
                } else {
                    line[i] += space_item.as_str();
                }
            }

            res.push(line.join(""));
        }
    }

    res
}

[
    "pub fn full_justify(words: Vec<String>, max_width: i32) -> Vec<String> { let n =",
    "words.len();  let  mut res = vec![]; let mut i = 0; while i < n { let mut line =",
    "vec![];        let       mut       curr_line_width       =       words[i].len();",
    "line.push(words[i].to_string());  i  +=  1; while i < n && curr_line_width + 1 +",
    "words[i].len()  <=  max_width  as usize { curr_line_width += 1 + words[i].len();",
    'line.push(words[i].to_string()); i += 1; } if i == n { let mut str = line.join("',
    '");  for _ in 0..(max_width as usize - str.len()) { str += " "; } res.push(str);',
    "} else if i < n && line.len() == 1 { let mut str = line[0].to_string(); for _ in",
    '0..(max_width as usize - str.len()) { str += " "; } res.push(str); } else if i <',
    "n && line.len() > 1 { let total_word_width = curr_line_width - (line.len() - 1);",
    "let  total_space_width  = max_width as usize - total_word_width; let mut carry =",
    "total_space_width % (line.len() - 1); let space_item_width = total_space_width /",
    "(line.len()   -   1);   let   mut   space_item   =   String::new();   for  _  in",
    '0..space_item_width  {  space_item  +=  " "; } for i in 0..(line.len() - 1) { if',
    'carry  >  0  { line[i] += (space_item.to_string() + " ").as_str(); carry -= 1; }',
    'else { line[i] += space_item.as_str(); } } res.push(line.join("")); } } res }   ',
  ];

题目​

题解​

题目

题解