当前位置： 面试刷题>> 文本左右对齐(经典算法150题)
### 题目描述
题目：**文本左右对齐**
给定一个字符串（代表一行文本）和一个整数`maxWidth`（表示每行允许的最大字符数，包括空格），要求将该字符串按照以下规则重新排列，使其左右对齐，并返回处理后的多行字符串数组。
- 字符串中的单词由空格分隔。
- 超出`maxWidth`的单词需要被移到新的一行。
- 每行末尾的空格数应该尽可能均匀分布（如果可能），但左对齐是首要条件。
- 如果一行的单词数量只有一个或者没有足够的空格均匀分布，则该行单词左对齐，并在右侧填充空格以达到`maxWidth`。
### 示例
**输入**:
```
str = "The quick brown fox jumps over the lazy dog"
maxWidth = 16
```
**输出**:
```
["The quick brown",
"fox jumps over",
"the lazy dog"]
```
### PHP 代码示例
```php
function fullJustify($words, $maxWidth) {
$result = [];
$line = [];
$lineLength = 0;
foreach ($words as $word) {
$wordLength = strlen($word) + 1; // 加1是因为单词间的空格
if ($lineLength + $wordLength > $maxWidth) {
$result[] = justifyLine($line, $maxWidth, count($line) > 1);
$line = [$word];
$lineLength = strlen($word);
} else {
$line[] = $word;
$lineLength += $wordLength;
}
}
// 处理最后一行
if (!empty($line)) {
$spaces = $maxWidth - $lineLength;
$n = count($line) - 1;
$result[] = implode(str_repeat(' ', ceil($spaces / $n)), array_slice($line, 0, -1)) . ' ' . end($line);
for ($i = 0; $i < $maxWidth - strlen(end($result)); $i++) {
end($result) .= ' ';
}
}
return $result;
}
function justifyLine($line, $maxWidth, $fullJustify) {
$n = count($line) - 1;
$lineStr = implode(' ', $line);
$spaces = $maxWidth - strlen($lineStr);
if ($fullJustify && $n > 0) {
$extraSpaces = $spaces % $n;
$avgSpaces = intdiv($spaces, $n);
$justifiedLine = '';
for ($i = 0; $i < $n; $i++) {
$justifiedLine .= $line[$i] . str_repeat(' ', $avgSpaces + ($i < $extraSpaces ? 1 : 0)) . ' ';
}
$justifiedLine .= $line[$n];
} else {
$justifiedLine = $lineStr . str_repeat(' ', $spaces);
}
return rtrim($justifiedLine);
}
// 示例用法
$words = explode(' ', "The quick brown fox jumps over the lazy dog");
$maxWidth = 16;
$result = fullJustify($words, $maxWidth);
print_r($result);
```
### Python 代码示例
```python
def fullJustify(words, maxWidth):
result = []
line = []
line_length = 0
for word in words:
word_length = len(word) + 1 # 加1考虑空格
if line_length + word_length > maxWidth:
result.append(justify_line(line, maxWidth, len(line) > 1))
line = [word]
line_length = len(word)
else:
line.append(word)
line_length += word_length
# 处理最后一行
if line:
spaces = maxWidth - line_length + len(line) - 1
result.append(' '.join(line) + ' ' * spaces)
result[-1] = result[-1].rstrip()
return result
def justify_line(line, maxWidth, full_justify):
n = len(line) - 1
line_str = ' '.join(line)
spaces = maxWidth - len(line_str)
if full_justify and n > 0:
extra_spaces = spaces % n
avg_spaces = spaces // n
justified_line = ''
for i in range(n):
justified_line += line[i] + ' ' * (avg_spaces + (1 if i < extra_spaces else 0))
justified_line += line[-1]
else:
justified_line = line_str + ' ' * spaces
return justified_line.rstrip()
# 示例用法
words = "The quick brown fox jumps over the lazy dog".split()
maxWidth = 16
result = fullJustify(words, maxWidth)
print(result)
```
### JavaScript 代码示例
```javascript
function fullJustify(words, maxWidth) {
const result = [];
let line = [];
let lineLength = 0;
for (let word of words) {
const wordLength = word.length + 1; // 加1考虑空格
if (lineLength + wordLength > maxWidth) {
result.push(justifyLine(line, maxWidth, line.length > 1));
line = [word];
lineLength = word.length;
} else {
line.push(word);
lineLength += wordLength;
}
}
// 处理最后一行
if (line.length) {
const spaces = maxWidth - (line.reduce((sum, word) => sum + word.length, 0) - line.length + 1);
result.push(line.join(' ') + ' '.repeat(spaces).slice(0, spaces));
}
return result;
}
function justifyLine(line, maxWidth, fullJustify) {
const n = line.length - 1;
const lineStr = line.join(' ');
let spaces = maxWidth - lineStr.length;
if (fullJustify && n > 0) {
const extraSpaces = spaces % n;
const avgSpaces = Math.floor(spaces / n);
let justifiedLine = '';
for (let i = 0; i < n; i++) {
justifiedLine += line[i] + ' '.repeat(avgSpaces + (i < extraSpaces ? 1 : 0)) + ' ';
}
justifiedLine += line[n];
} else {
justifiedLine = lineStr + ' '.repeat(spaces);
}
return justifiedLine.trim();
}
// 示例用法
const words = "The quick brown fox jumps over the lazy dog".split(' ');
const maxWidth = 16;
const result = fullJustify(words, maxWidth);
console.log(result);
```
以上代码均实现了文本左右对齐的功能，并处理了各种边界情况。