算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做 文本左右對齊，我們先來看題面：
https://leetcode-cn.com/problems/minimum-path-sum/
Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
題意給定一個單詞數組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字符，且左右兩端對齊的文本。你應該使用「貪心算法」來放置給定的單詞；也就是說，儘可能多地往每行中放置單詞。必要時可用空格 ' ' 填充，使得每行恰好有 maxWidth 個字符。要求儘可能均勻分配單詞間的空格數量。如果某一行單詞間的空格不能均勻分配，則左側放置的空格數要多於右側的空格數。文本的最後一行應為左對齊，且單詞之間不插入額外的空格。每個單詞的長度大於 0，小於等於 maxWidth。輸入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
輸出:
[
"This is an",
"example of text",
"justification. "
]
public class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> list = new ArrayList<>();
int n = words.length;
if(n == 0) {
return list;
}
//index represents which position in array words we are traversing now
int index = 0;
while(index < n) {
//every String in list contains 1 word or more
int len = words[index].length();
int i = index + 1;
for (; i < words.length; i++) {
if(len + words[i].length() + 1 > maxWidth) {
break;
}
len += words[i].length() + 1;
}
//levelLen represents how many characters that isn't space in erery String
int levelLen = 0;
for (int j = index; j < i; j++) {
levelLen += words[j].length();
}
//numSpace represents how many space between 2 words
int numSpace = i - index - 1;
//string represents every String
String string = "";
if(i != words.length) {
//if we haven't traversed all the words
if(numSpace != 0) {
//if this String has more than one word
int[] spaces = new int[numSpace];
int averageSpace = (maxWidth - levelLen) / numSpace;
int remainSpace = maxWidth - levelLen - numSpace * averageSpace;
for (int j = 0; j < numSpace; j++) {
if(j + 1 <= remainSpace) {
spaces[j] = 1 + averageSpace;
}else {
spaces[j] = averageSpace;
}
}
for (int j = index, k = 0; j < i && k < numSpace;) {
string += words[j];
j++;
for (int num = 0; num < spaces[k]; num++) {
string += " ";
}
k++;
}
}
string += words[i - 1];
if(numSpace == 0) {
//if this String only has one word, fill space in the remain position
while(string.length() < maxWidth) {
string += " ";
}
}
}else {
//if we have traversed all the words, the last String we need to put all words on the left
for (int j = index; j < i - 1; j++) {
string += words[j] + " ";
}
string += words[i - 1];
while(string.length() < maxWidth) {
string += " ";
}
}
list.add(string);
index = i;
}
return list;
}
}