# 文本左右对齐

<div class="notranslate">
  <p>给定一个单词数组和一个长度&nbsp;<em>maxWidth</em>，重新排版单词，使其成为每行恰好有&nbsp;<em>maxWidth</em>&nbsp;个字符，且左右两端对齐的文本。</p>

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

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

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

  <p><strong>说明:</strong></p>

  <ul>
    <li>单词是指由非空格字符组成的字符序列。</li>
    <li>每个单词的长度大于 0，小于等于&nbsp;<em>maxWidth</em>。</li>
    <li>输入单词数组 <code>words</code>&nbsp;至少包含一个单词。</li>
  </ul>

  <p><strong>示例:</strong></p>

  <pre><strong>输入:</strong>
    words = ["This", "is", "an", "example", "of", "text", "justification."]
    maxWidth = 16
<strong>输出:</strong>
    [
    &nbsp; &nbsp;"This &nbsp; &nbsp;is &nbsp; &nbsp;an",
    &nbsp; &nbsp;"example &nbsp;of text",
    &nbsp; &nbsp;"justification. &nbsp;"
    ]
    </pre>

  <p><strong>示例&nbsp;2:</strong></p>

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

  <p><strong>示例&nbsp;3:</strong></p>

  <pre><strong>输入:</strong>
    words = ["Science","is","what","we","understand","well","enough","to","explain",
    &nbsp;        "to","a","computer.","Art","is","everything","else","we","do"]
    maxWidth = 20
<strong>输出:</strong>
    [
    &nbsp; "Science &nbsp;is &nbsp;what we",
      "understand &nbsp; &nbsp; &nbsp;well",
    &nbsp; "enough to explain to",
    &nbsp; "a &nbsp;computer. &nbsp;Art is",
    &nbsp; "everything &nbsp;else &nbsp;we",
    &nbsp; "do &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;"
    ]
    </pre>
</div>

以下程序实现了这一功能，请你填补空白处的内容：

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void line_fill(char *line, int len, char **words, int *word_lens, int max_size,
					  int even_spaces, int remain_spaces, int start, int end)
{
	int i, j;
	char *p = line;
	for (i = start; i < end; i++)
	{
		memcpy(p, words[i], word_lens[i]);
		p += word_lens[i];
		if (i < end - 1)
		{
			___________________;
		}
	}
	while (p - line < max_size)
	{
		*p++ = ' ';
	}
	*p++ = '\0';
}
static char **fullJustify(char **words, int wordsSize, int maxWidth, int *returnSize)
{
	int i, j, k, cap = 100, count = 0;
	char **lines = malloc(cap * sizeof(char *));
	char *buf = malloc(cap * (maxWidth + 1));
	for (i = 0; i < cap; i++)
	{
		lines[i] = buf + i * (maxWidth + 1);
	}
	int *word_lens = malloc(wordsSize * sizeof(int));
	for (i = 0; i < wordsSize; i++)
	{
		word_lens[i] = strlen(words[i]);
	}
	int wc = 0;
	int len = 0;
	int start = 0;
	int chars = 0;
	for (i = 0, j = 0; i < wordsSize; i++)
	{
		if (len + word_lens[i] > maxWidth)
		{
			int even_spaces = wc == 1 ? 0 : (maxWidth - chars) / (wc - 1);
			int remain_spaces = wc == 1 ? 0 : (maxWidth - chars) % (wc - 1);
			line_fill(lines[count], len, words, word_lens, maxWidth, even_spaces, remain_spaces, start, i);
			count++;
			wc = 1;
			len = word_lens[i] + 1;
			chars = word_lens[i];
			start = i;
		}
		else if (len + word_lens[i] == maxWidth)
		{
			chars += word_lens[i];
			int even_spaces = wc == 0 ? 0 : (maxWidth - chars) / wc;
			int remain_spaces = wc == 0 ? 0 : (maxWidth - chars) % wc;
			line_fill(lines[count], len, words, word_lens, maxWidth, even_spaces, remain_spaces, start, i + 1);
			count++;
			wc = 0;
			len = 0;
			chars = 0;
			start = i + 1;
		}
		else
		{
			chars += word_lens[i];
			len += word_lens[i] + 1;
			wc++;
		}
	}
	if (wc > 0)
	{
		char *p = lines[count];
		for (i = start; i < start + wc; i++)
		{
			memcpy(p, words[i], word_lens[i]);
			p += word_lens[i];
			if (i < start + wc - 1)
			{
				*p++ = ' ';
			}
		}
		while (p - lines[count] < maxWidth)
		{
			*p++ = ' ';
		}
		*p++ = '\0';
		count++;
	}
	*returnSize = count;
	return lines;
}
int main(int argc, char **argv)
{
	if (argc <= 2)
	{
		fprintf(stderr, "Usage: ./test maxsize words...\n");
		exit(-1);
	}
	int i, count;
	char **lines = fullJustify(argv + 2, argc - 2, atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		printf("%s\n", lines[i]);
	}
	return 0;
}
```

## template

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static void line_fill(char *line, int len, char **words, int *word_lens, int max_size,
					  int even_spaces, int remain_spaces, int start, int end)
{
	int i, j;
	char *p = line;
	for (i = start; i < end; i++)
	{
		memcpy(p, words[i], word_lens[i]);
		p += word_lens[i];
		if (i < end - 1)
		{
			for (j = 0; j < even_spaces; j++)
			{
				*p++ = ' ';
			}
			if (remain_spaces > 0)
			{
				*p++ = ' ';
				remain_spaces--;
			}
		}
	}
	while (p - line < max_size)
	{
		*p++ = ' ';
	}
	*p++ = '\0';
}
static char **fullJustify(char **words, int wordsSize, int maxWidth, int *returnSize)
{
	int i, j, k, cap = 100, count = 0;
	char **lines = malloc(cap * sizeof(char *));
	char *buf = malloc(cap * (maxWidth + 1));
	for (i = 0; i < cap; i++)
	{
		lines[i] = buf + i * (maxWidth + 1);
	}
	int *word_lens = malloc(wordsSize * sizeof(int));
	for (i = 0; i < wordsSize; i++)
	{
		word_lens[i] = strlen(words[i]);
	}
	int wc = 0;
	int len = 0;
	int start = 0;
	int chars = 0;
	for (i = 0, j = 0; i < wordsSize; i++)
	{
		if (len + word_lens[i] > maxWidth)
		{
			int even_spaces = wc == 1 ? 0 : (maxWidth - chars) / (wc - 1);
			int remain_spaces = wc == 1 ? 0 : (maxWidth - chars) % (wc - 1);
			line_fill(lines[count], len, words, word_lens, maxWidth, even_spaces, remain_spaces, start, i);
			count++;
			wc = 1;
			len = word_lens[i] + 1;
			chars = word_lens[i];
			start = i;
		}
		else if (len + word_lens[i] == maxWidth)
		{
			chars += word_lens[i];
			int even_spaces = wc == 0 ? 0 : (maxWidth - chars) / wc;
			int remain_spaces = wc == 0 ? 0 : (maxWidth - chars) % wc;
			line_fill(lines[count], len, words, word_lens, maxWidth, even_spaces, remain_spaces, start, i + 1);
			count++;
			wc = 0;
			len = 0;
			chars = 0;
			start = i + 1;
		}
		else
		{
			chars += word_lens[i];
			len += word_lens[i] + 1;
			wc++;
		}
	}
	if (wc > 0)
	{
		char *p = lines[count];
		for (i = start; i < start + wc; i++)
		{
			memcpy(p, words[i], word_lens[i]);
			p += word_lens[i];
			if (i < start + wc - 1)
			{
				*p++ = ' ';
			}
		}
		while (p - lines[count] < maxWidth)
		{
			*p++ = ' ';
		}
		*p++ = '\0';
		count++;
	}
	*returnSize = count;
	return lines;
}
int main(int argc, char **argv)
{
	if (argc <= 2)
	{
		fprintf(stderr, "Usage: ./test maxsize words...\n");
		exit(-1);
	}
	int i, count;
	char **lines = fullJustify(argv + 2, argc - 2, atoi(argv[1]), &count);
	for (i = 0; i < count; i++)
	{
		printf("%s\n", lines[i]);
	}
	return 0;
}
```

## 答案

```cpp
for (j = 0; j < even_spaces; j++)
{
	*p++ = ' ';
}
if (remain_spaces > 0)
{
	*p++ = ' ';
	remain_spaces--;
}
```

## 选项

### A

```cpp
for (j = 0; j < even_spaces; j++)
{
	*p++ = ' ';
}
if (remain_spaces > 0)
{
	*p++ = ' ';
	remain_spaces++;
}
```

### B

```cpp
for (j = 0; j < even_spaces; j++)
{
	*p++ = ' ';
}
if (remain_spaces < 0)
{
	*p++ = ' ';
	remain_spaces++;
}
```

### C

```cpp
for (j = 0; j < even_spaces; j++)
{
	*p++ = '\0';
}
if (remain_spaces > 0)
{
	*p++ = '\0';
	remain_spaces--;
}
```