给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。 文本的最后一行应为左对齐，且单词之间不插入额外的空格。 注意: 单词是指由非空格字符组成的字符序列。 每个单词的长度大于 0，小于等于 maxWidth。 输入单词数组 words 至少包含一个单词。

<think>好的，我现在需要解决这个问题：将给定的单词数组按照最大宽度maxWidth进行两端对齐排版。用户要求使用贪心算法，并且满足特定的空格分配规则。最后一行要左对齐，且单词之间不插入额外空格。我需要仔细分析问题，然后一步步构建解决方案。 首先，我得理解题目要求。贪心算法意味着每一行尽可能放更多的单词，直到放不下下一个单词为止。那如何确定每一行能放多少个单词呢？比如，当前行的单词总长度加上至少需要的间隔空格数不能超过maxWidth。例如，如果有k个单词，那么至少需要k-1个空格，所以总长度是sum(单词长度) + (k-1) <= maxWidth。当加上下一个单词时可能超过，所以这一行的单词数目就确定为k个。 接下来，处理每一行的空格分配。对于非最后一行的情况，需要尽可能均匀分配空格。如果空格数无法平均分配，左边的空格要比右边多。例如，总共有s个空格需要分配，分到m个间隔（假设该行有n个单词，间隔数是n-1）。每个间隔的基本空格数是s/(m)，余数是s%m。左边的间隔多放一个空格，直到余数用完。例如，s=5，m=3，那么分配是2,2,1？或者余数是2，前两个间隔各加一个？比如，假设总共有5个空格，三个间隔，那么每个间隔先分1个，剩下5-3=2个，余下的2个分配给前两个间隔，所以变成2,2,1？或者可能我计算的方式需要再仔细考虑。 对于最后一行，所有单词之间只放一个空格，剩余的空格全部补在末尾。 那整个算法的大致步骤可能是这样的： 1. 分割每一行的单词。遍历words数组，确定每一行可以放哪些单词。这需要计算当前行单词的总长度，加上间隔的最小空格数（k-1），不超过maxWidth。当加上下一个单词时超过的话，当前行确定。 2. 对每一行进行构造： a. 如果是最后一行，或者该行只有一个单词：左对齐，单词间一个空格，后面补满空格。 b. 否则，计算总空格数：maxWidth - sum(单词长度)。然后分配这些空格到各个间隔。每个间隔先分配平均后的数目，余下的前几个间隔各加一个。 例如，总空格是totalSpaces，间隔数是numGaps = number of words -1。那么每个间隙的基础空格数是base = totalSpaces / numGaps。余数extra = totalSpaces % numGaps。那么前extra个间隙会有base+1个空格，剩下的间隙base个空格。 举个例子，假设总空格是7，间隔数是3。base=2，余数1。那么前1个间隙是3，剩下的两个间隙是2。总共有3+2+2=7。 这样构造每个行的字符串。 接下来，考虑如何分割每一行的单词。例如，遍历words数组，记录当前行的起始索引，然后不断尝试添加下一个单词，直到无法添加为止。这时候确定该行的单词范围，然后处理空格分配。 具体步骤： 初始化一个结果数组vector<string> res。当前行起始索引start=0。然后循环处理每个可能的行： 在每次循环中，计算当前行可以包含的单词数目。这需要从start开始，累加单词长度，并计算总长度加上空格数目是否超过maxWidth。例如，初始化currentLength为0。然后对于i从start到n-1，逐个单词尝试： currentLength += words[i].length() 如果此时currentLength + (i - start) > maxWidth，说明加上当前i的话，总长度（单词总长度加上间隔空格数i - start）已经超过maxWidth。因此，当前行只能包含从start到i-1的单词。此时，处理这些单词，生成该行的字符串，并添加到结果中。然后start = i，继续处理下一行。 否则，继续检查下一个单词。 当处理完所有单词后，剩下的最后一行需要特殊处理（左对齐）。 例如，假设所有单词已经处理到i = n-1，此时需要生成最后一行的字符串。 现在，如何具体实现这个过程？ 比如，假设words数组的长度为n。初始化start=0。然后循环： while start < n: 计算当前行可以包含的单词数目。初始currentLength = words[start].length() end = start + 1 while end < n: next_word_length = words[end].length() if currentLength + 1 + next_word_length > maxWidth: # 因为加上这个单词需要至少增加一个空格 break currentLength += 1 + next_word_length # 当前总长度加上空格和下一个单词长度 end +=1 # 此时，该行的单词是start到end-1。数目是cnt = end - start # 处理该行的构造 # 判断是否是最后一行（end >=n） if end == n: # 最后一行，左对齐，单词间一个空格，后面补空格 string line = join(words[start:end], " ") line += string(maxWidth - line.length(), ' ') else: # 普通行，需要分配空格 # 计算总空格数：maxWidth - sum(words[start..end-1] lengths) totalSpaces = maxWidth - (currentLength - (end - start -1)) # 因为currentLength包含了单词长度和每个间隔的一个空格。例如，假设有k个单词，currentLength是sum(len) + (k-1)*1。所以总空格数是maxWidth - sum(len) = totalSpaces。而总需要填充的空格数是totalSpaces = maxWidth - sum(len。那sum(len)等于currentLength - (k-1)，其中k = end - start。例如，假设k个单词，sum(len) = currentLength - (k-1) *1？比如，当有k=2个单词时，currentLength是sum(len) +1。所以总空格数是maxWidth - (currentLength - (k-1))。或者是不是应该重新计算sum(len)？比如，可以预先计算sum(words[i].length() for i in start..end-1)。或者在循环中，记录sum_len而不是currentLength。这可能更准确。例如： 当计算currentLength时，初始为words[start].length()，之后每次加上1（空格）和下一个单词的长度。这样，sum_len其实是初始的words[start].length()加上后面每个单词的长度。例如： sum_len = words[start].length() for i in start+1到end-1: sum_len += words[i].length() currentLength = sum_len + (end - start -1)*1 # 每个间隔一个空格。所以总空格数应该是maxWidth - sum_len。 所以，在循环中，可以维护sum_len的值，而不是currentLength。这可能更直接。 所以，或许应该重新设计循环中的变量： 在确定每一行的end时，初始化sum_len为words[start].length()，然后end=start+1。 循环条件： while end <n: new_sum = sum_len + 1 + words[end].length() if new_sum + (end - start -1) > maxWidth？或者这样计算可能有问题？ 或者，总长度是sum_len（单词总长度） + (end - start) -1（间隔数） <= maxWidth？因为每个单词之间至少一个空格。所以，当尝试添加第end个单词时，新的总长度是 sum_len + words[end].length() + (end - start) 的空格数？比如，原来的间隔数是 (end-1 - start) ，添加第end个单词后间隔数是 (end - start) 。总长度是 sum_len + words[end].length() + (end - start) <= maxWidth？ 例如，假设start=0，当前sum_len是words[0]的长度。当考虑添加words[1]，此时总长度是sum_len + 1（空格） + words[1].length()。间隔数是1。此时总长度是sum_len + words[1].length() + 1。如果这个总长度超过了maxWidth，那么不能添加words[1]。否则继续。所以，正确的条件是： 当尝试添加words[end]时，新的总长度是 sum_len + 1（空格） + words[end].length() + (间隔数)？ 或许应该将循环中的条件重新设计为：计算添加下一个单词后的总长度（单词总长度加上间隔所需的最小空格数）是否超过maxWidth。例如： sum_len = sum(words[start..end-1].length()) num_gaps = end-1 - start 当添加words[end]时，sum_len += words[end].length() num_gaps +=1 总长度是 sum_len + num_gaps <= maxWidth ? 是的。所以，在确定是否可以添加下一个单词时，要看sum_len + words[end].length() + (num_gaps +1) <= maxWidth。这里，num_gaps是原来的间隔数，即当前单词数目是 (end - start)，间隔数是 (end - start -1)。当添加第end个单词时，间隔数变为 (end - start)。总长度是 sum_len + words[end].length() + (end - start) <= maxWidth？ 所以，在循环中，初始sum_len是words[start]的长度。然后，end从start+1开始，尝试添加每个单词： 对于每个end，临时计算需要的最小空格数：end - start（间隔数）因为当添加第end个单词时，有end - start个单词，间隔数是 (end - start -1)。总长度是 sum_len（start到end-1的单词总长度） + words[end].length() + (end - start -1) 的空格数。但是这可能已经包括了之前的sum_len的计算方式。 可能我需要重新调整变量的维护方式： 例如，在循环中，每次添加一个单词到当前行，需要计算当前行的总单词长度加上所需的最小空格数（即间隔数）是否超过maxWidth。例如，初始时，sum_len = words[start].length()，此时间隔数是0，总长度是sum_len。可以添加下一个单词吗？即，sum_len + words[end] +1（空格）是否 <= maxWidth？ 比如，假设当前行有k个单词，它们的总长度是S，那么所需的最小空格数是k-1。此时，总长度是 S + (k-1)。当尝试添加第k+1个单词时，总长度是 S + (k-1) + 1（空格） + words[k].length() = (S + words[k].length()) ) +k。这时候，k是新的间隔数吗？是的，因为k+1个单词之间有k个间隔。所以总长度是 (sum_len + new_word_length) + (k) <= maxWidth ? 所以，正确的条件是，在添加第end个单词后，总长度（单词总长度之和加上间隔数）是否不超过maxWidth。即： sum_current_words_length + (number_of_gaps) <= maxWidth 其中，number_of_gaps是当前行的单词数目减一。例如，当有m个单词时，间隔数是m-1。总长度是 sum_length + (m-1) <= maxWidth。 所以，在确定是否可以将words[end]加入当前行时，需要计算： 当前行的单词数目是m = end - start + 1 ? 不，当start到end-1是当前行的候选，当尝试添加end时，新的行的单词数目是end - start +1吗？或者初始时，start的单词是确定的，然后end从start+1开始尝试？ 例如，初始时，start是0，当前sum_len是words[0].length()，然后尝试添加words[1]。此时，新的sum_len是 sum_len + words[1].length()。间隔数是1（两个单词之间一个空格）。总长度是 sum_len_new + 1 <= maxWidth ? 是的。因此，当end从start+1开始，尝试添加每一个可能的单词，直到无法添加为止。 因此，在循环中： sum_len = words[start].length() end = start+1 while end <n: required = sum_len + words[end].length() + (end - start) # 因为此时有 (end - start +1) 个单词，间隔数是 (end - start)，所以总长度是 sum_len + words[end].length() + (end - start) <= maxWidth ? 例如，sum_len是前end - start个单词的总长度？或者sum_len是前(end-1 - start +1) = end - start个单词的总长度？ sum_len目前是start到end-1的总长度。当添加end时，sum_len += words[end].length()。此时，总单词数目是 (end - start +1)，间隔数是 (end - start)。总长度是 sum_len + (end - start) ? 是的。例如： 初始时，sum_len = words[start]的长度。此时单词数目是1，间隔数是0，总长度是 sum_len + 0 = sum_len <= maxWidth ? 添加words[end]后，sum_len += words[end].length()，单词数目是2，间隔数是1，总长度是 sum_len +1 ? 所以，当添加第end个单词时，需要判断 sum_len + (end - start) <= maxWidth ？ 是的。因为 (end - start)是间隔数目（单词数目-1）。 因此，在循环中： sum_len = 0 num_words = 0 for end from start to n-1: if sum_len + words[end].length() + num_words > maxWidth: break sum_len += words[end].length() num_words +=1 但是这可能更简单。或者，另一种方式是： 初始化当前行的总长度sum_len为0，单词数目为0。然后逐个添加单词，直到无法添加为止： sum_len =0 current_words = [] for i from start to n-1: if sum_len + len(words[i]) + max(current_words.size(), 0) <= maxWidth: sum_len += len(words[i]) current_words.add(words[i]) else: break end = i 这里的max(current_words.size(),0)是因为，当current_words为空时，添加第一个单词不需要空格。否则，每个新单词需要加一个空格。所以，总长度是sum_len（单词总长度） + (current_words.size()-1)（空格数） <= maxWidth。 或者，在每次添加一个单词时，计算总长度是否允许： 初始时sum_len为0，current_words为空。当添加第一个单词时，sum_len += len(word)，current_words.size()是1，空格数是0，总长度是sum_len. 添加第二个单词时，sum_len += len(word) +1（空格），因为两个单词之间需要一个空格。总长度是 sum_len + len(word) +1 <= maxWidth ? 所以，正确的条件是： 对于当前行的current_words，当尝试添加第i个单词时，新的总长度是 sum_len + (current_words.size()>0 ? 1 :0 ) + len(word) <= maxWidth ? 这可能更准确。例如： sum_len初始为0，current_words为空。 添加第一个单词：sum_len += len(word)，current_words.size()变成1。此时总长度是 sum_len = len(word) <= maxWidth. 添加第二个单词：需要 sum_len +1 + len(word) <= maxWidth ? sum_len是前一个总和。这样，每次添加时，判断是否总和加上必要的空格和单词长度不超过maxWidth。 所以，代码大致如下： int start =0; while (start < words.size()) { int end = start; int sum_len =0; while (end < words.size()) { int needed = sum_len ==0 ? words[end].length() : sum_len +1 + words[end].length(); if (needed > maxWidth) break; sum_len = needed; end++; } // 此时，当前行包含start到end-1的单词。 // 处理该行 processLine(start, end-1); start = end; } 这样，sum_len的计算是包括空格的，但可能这样在计算总单词长度时会有问题，因为空格被计算在sum_len中。例如，假设sum_len保存的是单词总长度加上空格的总数。这样，在处理该行的时候，sum_len等于该行的单词总长度加上（单词数目-1）的空格数。比如，如果有两个单词，sum_len是 len1 +1 + len2 = len1 + len2 +1。而maxWidth可能比这个sum_len大，所以需要分配额外的空格。 例如，假设maxWidth是16，两个单词的总长度是10，sum_len是10 +1 =11。总空格数是16-10=6，每个间隔需要分配6个空格。比如，间隔数目是1，所以每个间隔6个空格。那么总长度是10 +6=16. 所以，在处理该行的时候，需要知道该行的单词总长度之和，而不是sum_len。因为sum_len包括了原来的空格数（每个间隔一个空格）。 因此，可能需要将sum_len拆分为两个变量：单词总长度之和，以及间隔数。或者，在确定end之后，重新计算该行的单词总长度之和。例如： 当确定当前行的单词是start到end-1时，sum_length = sum( words[i].length() for i in start to end-1 ) 然后，总空格数是 maxWidth - sum_length. 这样可能更直接，避免在sum_len中混淆空格的长度。 因此，在确定end之后，需要计算该行的单词数目是cnt = end - start. 然后，sum_length = sum( words[i].length() for i from start to end-1 ) 总空格数目是 spaces = maxWidth - sum_length. 然后根据是否是最后一行或者cnt是否为1，进行不同的处理。 所以，如何确定end？ 例如，当尝试添加每个单词时，必须确保添加后的单词总长度加上间隔所需的最少空格数（即间隔数）之和不超过maxWidth。 所以，正确的条件应该是： 对于当前尝试添加的单词i，总长度是 sum_length + (current_cnt) <= maxWidth ? 其中，current_cnt是当前行的单词数目（在添加i之后）。 例如，初始时sum_length=0，current_cnt=0. 添加第一个单词i=start: sum_length += words[i].length() → sum_length=len1 current_cnt=1 →间隔数是0 →总长度是 len1 +0 <= maxWidth →肯定成立。 添加第二个单词i=start+1: 新的sum_length += words[i].length() → len1 + len2 current_cnt=2 →间隔数是1 →总长度是 len1 + len2 +1 <= maxWidth ? 如果满足，继续。否则，不能添加。 所以，正确的条件应该是：sum_length_new + (current_cnt_new -1) <= maxWidth. sum_length_new是添加单词后的总单词长度之和，current_cnt_new是当前行的单词数目（即原来的cnt+1）。 因此，在确定end的时候，需要逐个单词尝试，直到无法添加为止。 因此，正确的循环结构应该是： start =0 while start < n: end = start sum_length =0 max_end = start while end <n: current_word_length = words[end].length() required = sum_length + (end > start ? 1 :0 ) + current_word_length if required > maxWidth: break sum_length += (end > start ? 1 :0 ) + current_word_length max_end = end+1 # 因为end是当前可以加入的最后一个单词的索引？ end +=1 # 此时，该行的单词是start到max_end-1？ 或者可能我在这里的逻辑有问题。或者，或许应该用另一种方式： start =0 while start <n: end = start sum_len =0 // 这里sum_len是单词总长度加上已经添加的空格数？ // 或者应该分开计算单词总长度和空格数？ // 或许更简单的方式是，计算当前行的总长度（单词总长度 + 间隔数）是否 <=maxWidth. // 初始时，当前行没有单词。逐个添加，直到不能再添加。 int current_sum =0; int num_words =0; int space_needed =0; while (start + num_words <n) { int new_word_len = words[start + num_words].length(); int new_total = current_sum + new_word_len + (num_words ==0 ?0 :1); // 单词之间的空格数。如果有num_words个单词，空格数是num_words-1。但是当尝试添加第(num_words+1)个单词时，空格数将增加到num_words。所以，当添加该单词时，总长度是 current_sum + new_word_len + (num_words) ? // 因为当前已选num_words个单词，空格数是num_words-1。添加第num_words+1个单词时，空格数为num_words. // 所以 new_total = sum_words + new_word_len + num_words. // 其中 sum_words是前num_words个单词的总长度. // 所以，当添加第num_words+1个单词时，总长度是 sum_words + new_word_len + num_words <= maxWidth ? // 例如，初始num_words=0，添加第一个单词时，sum_words=0，new_word_len=len1，num_words变为1。总长度是 len1 +0 = len1 <=maxWidth. // 添加第二个单词：sum_words=len1， new_word_len=len2，num_words=1 → new_total = len1 + len2 +1 <=maxWidth ? if (current_sum + new_word_len + num_words > maxWidth) { break; } current_sum += new_word_len; num_words +=1; } end = start + num_words; 此时，该行有num_words个单词，从start到end-1。 然后处理该行。 这可能更正确。 例如： maxWidth=16 words = ["This", "is", "an", "example", "of", "text", "justification."] 当处理第一行时，start=0，num_words=0: current_sum=0，new_word_len=4（"This"） → current_sum + new_word_len +0=4 <=16 → yes. num_words=1. 下一个单词new_word_len=2（"is"） → current_sum=4+2=6，num_words=1 → new_total=6 +1=7 <=16 → yes. num_words=2. 第三个单词new_word_len=2（"an"） → current_sum=6+2=8 → new_total=8+2=10 → num_words=3 → total=8 +2 (num_words=3-1=2?) → 我可能需要重新计算。 哦，这里可能我的条件有错误。例如，在判断新单词是否可以被加入时，总长度应该是 sum_words + new_word_len + (num_words) <= maxWidth。因为当有num_words+1个单词时，间隔数是 num_words。 所以，在循环中： num_words初始为0。每次尝试添加第i个单词（i从0开始）： sum_words是前i个单词的总长度（i从0到num_words-1）。 现在，当尝试添加第num_words个单词时： new_word_len = words[start + num_words].length() 总长度是 sum_words + new_word_len + num_words <= maxWidth ? 是的，因为此时将有 num_words+1个单词，间隔数是num_words个，每个间隔一个空格，总空格数是 num_words。所以总长度是 sum_words + new_word_len + num_words. 所以，当sum_words是前num_words个单词的总长度时，添加第num_words+1个单词的条件是： sum_words + new_word_len + num_words <= maxWidth ? 例如： num_words=0，添加第一个单词：sum_words=0 + new_word_len +0 → len1 <=maxWidth. 添加第二个单词：sum_words=len1 → len1 + len2 +1（因为num_words=1 →空格数是1） →总长度 len1+len2+1 <=maxWidth. 所以，循环中的条件是正确的。 这样，当循环结束时，num_words是该行可以容纳的单词数目。例如，假设maxWidth=16： 第一行： num_words=0 →添加第一个单词：4+0=4<=16 →yes. num_words=1. 添加第二个单词：4+2+1=7 <=16 →yes. num_words=2. 第三个单词：4+2+2+2= 4+2+2=8？或者我可能计算错了。 原sum_words=4+2=6（前两个单词总和），num_words=2。此时尝试添加第三个单词： new_word_len=2. sum_words + new_word_len + num_words →6+2+2=10 <=16 → yes. num_words=3. 现在尝试添加第四个单词（"example"长度7）: sum_words=6+2=8 →或者sum_words是前三个单词的总和？ 哦，可能我在循环中的变量维护有错误。在循环中，current_sum是前num_words个单词的总长度。例如，当num_words=3时，current_sum是前3个单词的总长度。 例如，当num_words=0，current_sum=0. 添加第一个单词：new_word_len=4 →current_sum=4, num_words=1. 添加第二个单词：new_word_len=2 →current_sum=4+2=6, num_words=2. 添加第三个单词：new_word_len=2 →current_sum=6+2=8, num_words=3. 此时，总长度是 current_sum + (num_words-1) =8+2=10 <=16. 现在，尝试添加第四个单词（"example"长度7）: new_word_len=7. 总长度是 current_sum（8） +7 +3（num_words是3，因为现在要添加第四个单词，num_words将变成4，此时空格数是3） →8+7+3=18>16，所以不能添加。因此，该行的单词数目是3个："This", "is", "an"，总长度8，空格数目3-1=2，总长度8+2=10。剩下的空格数是16-8=8。所以需要将这8个空格分配到2个间隙中。每个间隙平均4个。因此，构造该行为"This is an"（每个间隙4个空格）。 所以，这样的逻辑是正确的。 因此，循环中的处理逻辑是正确的。这样，在代码中，可以这样实现： 在C++中，使用start和end指针。每次确定该行的单词数目num_words，然后计算该行的字符串。 现在，如何处理每一行的字符串构造？ 对于非最后一行，且单词数目大于1的情况： 总空格数目为maxWidth - sum_length。间隔数目是num_words-1. 例如，sum_length是该行所有单词的总长度之和。 每个间隙的空格数目是： base = total_spaces / (num_words-1) extra = total_spaces % (num_words-1) 前extra个间隙有base+1个空格，剩下的间隙有base个空格。 例如，总空格是8，间隙数目是2。则base=4，extra=0 →每个间隙4个空格。 另一个例子，总空格是7，间隙数目3 → base=2， extra=1 →前1个间隙3，后两个间隙2. 然后，构造该行的字符串： 对于第i个间隙（0 <=i < num_words-1）： 空格数目是 base + (i < extra ? 1 :0 ) 然后，将这些空格添加到单词之间。 对于最后一行，或者该行只有一个单词： 如果是最后一行，则所有单词左对齐，每个间隙一个空格，后面填充空格直到maxWidth. 如果是只有一个单词，则后面填充空格。 因此，在代码中： 处理每行的步骤： 1. 计算该行的单词数目num_words = end - start. 2. sum_length = sum( words[i].length() for i in start..end-1 ) 3. 是否是最后一行？ end ==n ? 4. 如果是最后一行或者该行只有一个单词： 构造左对齐的字符串： 将所有单词用单个空格连接，然后在后面补足空格，使总长度达到maxWidth. 5. 否则： 总空格数：spaces = maxWidth - sum_length. gaps = num_words-1. base = spaces / gaps. extra = spaces % gaps. 构造该行的字符串，前extra个间隙用base+1个空格，剩下的用base个。 现在，如何将这些步骤转化为C++代码？ 例如： vector<string> result; int n = words.size(); int start =0; while (start <n) { int num_words =0; int sum_len =0; // 找到该行的单词数目 while (start + num_words <n) { int current_word_len = words[start + num_words].length(); if (num_words ==0) { // 第一个单词，不需要空格 if (sum_len + current_word_len > maxWidth) { break; } } else { // 需要空格数目等于num_words（即当前单词数目，因为间隙数是num_words） if (sum_len + current_word_len + num_words > maxWidth) { break; } } sum_len += current_word_len; num_words++; } int end = start + num_words; bool is_last_line = (end ==n); string line; if (num_words ==1 || is_last_line) { // 左对齐 line = words[start]; for (int i=start+1; i <end; i++) { line += " " + words[i]; } // 补足空格 line += string( maxWidth - line.length(), ' ' ); } else { // 分配空格 int total_spaces = maxWidth - sum_len; int gaps = num_words -1; int base = total_spaces / gaps; int extra = total_spaces % gaps; line = words[start]; for (int i=1; i <num_words; i++) { int spaces = base + (i <= extra ? 1 :0 ); line += string(spaces, ' ') + words[start+i]; } } result.push_back(line); start = end; } 但这里可能存在一些问题。例如，在计算该行可以容纳的单词数目时，上述代码是否正确？ 例如，在确定num_words时，初始sum_len是0，num_words是0。然后循环： current_word_len = words[start+0]（即第一个单词）的长度。因为num_words==0，所以判断sum_len + current_word_len是否超过maxWidth。如果是的话，break，否则sum_len += current_word_len，num_words=1. 然后下一个循环，此时num_words=1。current_word_len是words[start+1].length()。此时，判断sum_len + current_word_len + num_words（即1）是否超过maxWidth？例如，总长度是sum_len（第一个单词的长度） + 第二个单词长度 +1（空格）是否超过maxWidth？ 是的。这样条件是正确的。 例如，当maxWidth是16，第一个单词长度是4。sum_len=4。num_words=1. 第二个单词长度是2 →4+2 +1=7 <=16 →可以添加。sum_len=6. num_words=2. 第三个单词长度是2 →6+2+2=10 <=16 →可以。sum_len=8. num_words=3. 第四个单词长度是7 →8+7 +3= 18>16 →不能添加。所以该行有三个单词。 总空格数目是16-8=8。间隙数目是2. base=4, extra=0.每个间隙4个空格。所以行是 "This is an". 是的，这与之前的例子一致。 现在，如何处理当单词数目为1的情况？例如，假设该行只能放一个单词，那么必须在该单词后面填充空格。例如，maxWidth是5，单词是"abc"。构造"abc ". 现在，代码是否正确处理这种情况？ 当该行只有一个单词时，进入左对齐的分支。构造该单词，后面补空格到maxWidth. 是的。 对于最后一行，例如，假设有三个单词，构造时每个间隙一个空格，后面补足。例如，假设maxWidth是16，sum_length= ...假设最后一行的总单词长度是13，三个单词，那么总空格数是16-13=3. 但因为是最后一行，每个间隙一个空格，总空格数目是2（三个单词两个间隙，每个一个空格，总长13+2=15，后面补1空格）。 是的，代码中的处理是正确的。 综上，这样的代码结构是正确的。现在需要将其转化为C++代码。 此外，还需要处理一些边界情况，例如，所有单词恰好填满一行，或者单词间空格分配的情况。 现在，编写代码： 需要注意，在确定num_words的循环中，判断条件是否正确。例如，在每次循环中，start + num_words是当前要尝试添加的单词的索引。 在代码中： int num_words =0; int sum_len=0; while (start + num_words <n) { int current_word_len = words[start + num_words].length(); if (num_words ==0) { if (sum_len + current_word_len > maxWidth) { break; } } else { if (sum_len + current_word_len + num_words > maxWidth) { // 因为此时已经有num_words个单词，添加新的单词后，总空格数是num_words（间隙数目是num_words，因为单词数目是num_words+1） // 总长度是 sum_len + current_word_len + num_words → 之前的sum_len是前num_words个单词的总长度，现在加上第num_words+1个单词的长度，加上num_words个空格？ // 例如，num_words=1（当前已有一个单词），现在添加第二个单词，空格数目是1。总长度是 sum_len（第一个单词的长度） + current_word_len（第二个单词） +1. // 所以条件判断是否正确？ // 例如，此时判断 sum_len + current_word_len + num_words > maxWidth ? // sum_len是前num_words个单词的总和。current_word_len是第num_words+1个单词的长度。空格数目是 num_words. // 总长度是 sum_len + current_word_len + num_words → 对吗？ // 是的。例如，前两个单词的总长度是 sum_len = len1 + len2。添加第三个单词时，总长度是 len1 + len2 + len3 + 2（空格数目是2，即三个单词两个间隙） → 总长度是 sum_len + len3 +2. // 但在这个条件判断中，当num_words是2时，已经添加了两个单词，sum_len是它们的总和。此时尝试添加第三个单词： // sum_len + current_word_len + num_words → sum_len是前两个单词的总和，current_word_len是第三个单词的长度，num_words是2 → 总长度是 sum_len + current_word_len +2 → 对吗？ // 是的。因为此时总单词数目是3，空格数目是2。总长度是 (sum_len) + current_word_len（第三个单词） +2（空格）. // sum_len是前两个单词的总和，所以总长度是 sum_len + current_word_len +2 = (len1 + len2) + len3 +2 = sum_len_new（三个单词的总长度） +2 → 此时总长度等于三个单词总长度加上两个空格？ // 但是，总空格数目是2吗？是的，三个单词之间有2个间隙，每个间隙一个空格。所以总长度是正确的。 // 所以，条件判断是正确的。如果sum_len + current_word_len + num_words > maxWidth → 不能添加该单词。 break; } } sum_len += current_word_len; num_words++; } 这样，循环结束后，num_words是该行可以容纳的单词数目。例如，假设start是0，num_words是3，那么该行包括words[0], words[1], words[2]. 然后，构造该行的字符串。 现在，编写完整的C++代码： 需要包含必要的头文件，比如<vector>，<string>等。 代码的大致结构： #include <vector> #include <string> using namespace std; class Solution { public: vector<string> fullJustify(vector<string>& words, int maxWidth) { vector<string> result; int n = words.size(); int start =0; while (start <n) { int num_words =0; int sum_len =0; while (start + num_words <n) { int current_word_len = words[start + num_words].length(); if (num_words ==0) { // 第一个单词，不需要空格 if (sum_len + current_word_len > maxWidth) { break; } } else { if (sum_len + current_word_len + num_words > maxWidth) { // 加上该单词后的总长度超过maxWidth break; } } sum_len += current_word_len; num_words++; } int end = start + num_words; bool is_last_line = (end ==n); string line; if (num_words ==1 || is_last_line) { // 左对齐，单词之间一个空格，末尾补空格 line = words[start]; for (int i= start+1; i < end; ++i) { line += " " + words[i]; } // 补足剩余空格 line += string( maxWidth - line.length(), ' ' ); } else { // 分配空格 int total_spaces = maxWidth - sum_len; int gaps = num_words -1; int base = total_spaces / gaps; int extra = total_spaces % gaps; line = words[start]; for (int i=1; i < num_words; ++i) { int spaces = base + (i-1 < extra ? 1 :0 ); line += string(spaces, ' ') + words[start +i]; } } result.push_back(line); start = end; } return result; } }; 这里需要注意，在分配空格的时候，前extra个间隙要多一个空格。例如，如果extra是2，那么前两个间隙各加一个空格。 在代码中： int extra = total_spaces % gaps; line = words[start]; for (int i=1; i < num_words; ++i) { int spaces = base + (i-1 < extra ? 1 :0 ); line += string(spaces, ' ') + words[start +i]; } 这里，i从1到num_words-1。i表示当前处理的是第几个单词后的间隙。例如，第一个间隙在words[start]和words[start+1]之间。i=1时，对应第1个间隙。判断i-1是否小于extra。例如，当extra=1时，i-1<1 →i=1时，i-1=0 <1 →true，所以该间隙的spaces=base+1. 例如，当有3个单词，gaps=2，extra=1： i从1到2: i=1 → i-1=0 <1 →spaces=base+1. i=2 →i-1=1 <1 →false →spaces=base. 这样，第一个间隙多加一个，第二个间隙不加。这符合要求。 例如，总空格是5，gaps=2 →base=2, extra=1.前1个间隙3空格，后一个间隙2. 是的，这样处理是正确的。 现在，测试这个代码是否正确。 例如，样例输入： words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth =16. 正确的输出是： [ "This is an", "example of text", "justification. " ] 现在，看代码是否能处理第一行： 第一行的start=0。循环确定num_words: current_word_len依次是4，2，2，7. 初始num_words=0： sum_len=0 →+4 <=16 →sum_len=4, num_words=1. num_words=1: 当前current_word_len是2. sum_len +2 +1=4+2+1=7 <=16 → sum_len=6, num_words=2. num_words=2: current_word_len是2 →sum_len+2 +2=6+2+2=10 <=16 →sum_len=8, num_words=3. num_words=3: current_word_len是7 →sum_len+7+3=8+7+3=18>16 →break. 所以，num_words=3，end=3. 构造该行：三个单词，不是最后一行，且num_words>1. total_spaces=16 -8=8. gaps=2. base=4, extra=0. 每个间隙4个空格。结果应该是"This is an" →正确。 第二行：start=3. words[3]是"example"长度7，下一个单词是"of"长度2，再下一个是"text"长度4. 循环确定num_words: num_words=0 →sum_len=7 <=16 →yes. num_words=1. num_words=1 →尝试添加"of"长度2 →sum_len+2+1=7+2+1=10 <=16 →yes. num_words=2. num_words=2 →尝试添加"text"长度4 →sum_len+4+2=10+4+2=16 →刚好等于maxWidth →yes. sum_len=14, num_words=3. 此时，start+num_words=3+3=6 <n=7 →继续循环。 尝试添加下一个单词"justification."长度13: sum_len+13+3=14+13+3=30>16 →break. 所以，num_words=3，end=6. 该行不是最后一行（end=6 <7）→需要分配空格。 sum_length=7+2+4=13. total_spaces=16-13=3. gaps=2. base=3/2=1, extra=1. 所以，第一个间隙1+1=2空格，第二个间隙1空格. 所以，该行是"example of text" →正确。 第三行：start=6，单词是"justification."长度13. num_words=0 →sum_len+13 <=16 →13<=16 →yes. num_words=1. 因为start+num_words=6+1=7 ==n →是最后一行。 构造该行：单词后补两个空格，总长度13+2=15 →补1个空格？或者总长度是13，构造时添加一个空格吗？ 根据代码中的处理，最后一行左对齐，单词之间一个空格，后面补空格到maxWidth. 此时，只有一个单词，所以直接补空格： line = "justification." → length=13 →补3个空格，总长度16 →正确。 所以，结果正确。 另一个测试案例： words = ["What","must","be","acknowledgment","shall","be"], maxWidth =16. 正确的输出： [ "What must be", "acknowledgment ", "shall be " ] 检查代码是否正确处理第二行： 第二行是"acknowledgment" →长度14，补2空格 →正确。 第三行有两个单词"shall"和"be" →总长度5+2=7+1=8。总空格数16-7=9。因为是最后一行，所以补到后面。所以行是"shall be " →共有9个空格？ 5+2+1=8，补8空格？ 16-8=8 →是的。 代码是否能正确处理？ 第三行的start=4（假设前两行处理完毕），此时words[4]是"shall"，words[5]是"be". 循环确定num_words: num_words=0 →sum_len=5 ≤16 →yes. num_words=1. num_words=1 →尝试添加"be" →sum_len+2+1=5+2+1=8 <=16 →yes. sum_len=7, num_words=2. end=4+2=6 ==n →是最后一行. 构造该行："shall be" + 16-7-1=8个空格？因为总长度是5+1+2=8 →后面补16-8=8空格 →是的。所以正确。 综上，代码是正确的。</think>```cpp #include <vector> #include <string> using namespace std; class Solution { public: vector<string> fullJustify(vector<string>& words, int maxWidth) { vector<string> res; int n = words.size(); int start = 0; while (start < n) { int numWords = 0; int sumLen = 0; while (start + numWords < n) { int currentLen = words[start + numWords].length(); if (numWords == 0) { if (sumLen + currentLen > maxWidth) break; } else { if (sumLen + currentLen + numWords > maxWidth) break; } sumLen += currentLen; numWords++; } int end = start + numWords; bool isLastLine = (end == n); string line; if (numWords == 1 || isLastLine) { line = words[start]; for (int i = start + 1; i < end; ++i) { line += " " + words[i]; } line += string(maxWidth - line.length(), ' '); } else { int totalSpaces = maxWidth - sumLen; int gaps = numWords - 1; int base = totalSpaces / gaps; int extra = totalSpaces % gaps; line = words[start]; for (int i = 1; i < numWords; ++i) { int spaces = base + (i - 1 < extra ? 1 : 0); line += string(spaces, ' ') + words[start + i]; } } res.push_back(line); start = end; } return res; } }; ```