题目描述
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词
输入输出示例
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
解决方案
方式一：模拟
算法思路：根据题干描述的贪心算法，对于每一行，我们首先确定最多可以放置多少单词，这样可以得到该行的空格个数，从而确定该行单词之间的空格个数。
对于填充空格的情况，主要分为以下三种：
当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格；
当前行不是最后一行，且只有一个单词：该单词左对齐，在行末填充空格；
当前行不是最后一行，且不只一个单词：设当前行单词数为 numWords，空格数为 numSpaces，我们需要将空格均匀分配在单词之间，则单词之间应至少有
个空格，对于多出来的
extraSpaces=numSpacesmod(numWords−1)
个空格，应填在前 extraSpaces 个单词之间。因此，前 extraSpaces 个单词之间填充 avgSpaces+1 个空格，其余单词之间填充 avgSpaces 个空格。
实现代码：
class Solution {public List<String> fullJustify(String[] words, int maxWidth) {List<String> ans=new ArrayList<String>();//定义结果集int right=0,n=words.length;//right指每行的最后一个单词在数组中的位置,n为每行的长度while(true){int left=right;//当前行的第一个元素在words数组中的位置int sumLen=0; //统计一行的单词长度//循环确定当前行能够放多少单词，注意单词之间应该有一个空格while(right<n&&sumLen+words[right].length()+right-left<=maxWidth){//right<n 判断word数组中是否还有单词//sumLen+words[right].length()+right-left ///现在单词的长度+新添加的单词的长度+单词之间的空格数=新的总字符长度sumLen+=words[right++].length();}//当前行是最后一行：单词左对齐，且单词之间只有一个空格，在行末填充剩余空格if(right==n){StringBuffer sb=join(words,left,n," ");//先添加所有的单词以及行末空格sb.append(blank(maxWidth-sb.length()));//添加行末的空格ans.add(sb.toString());return ans;}int numWords=right-left;//剩余单词数int numSpaces=maxWidth-sumLen;//剩余空间//当前行只有一个单词：单词左对齐，在行末填充空格if(numWords==1){StringBuffer sb=new StringBuffer(words[left]);sb.append(blank(numSpaces));ans.add(sb.toString());continue;}//当前行有多个单词，且不是最后一行int avgSpaces=numSpaces/(numWords-1); //平均每个单词之间的空格数int extraSpaces=numSpaces%(numWords-1);//多余的空格StringBuffer sb=new StringBuffer();sb.append(join(words,left,left+extraSpaces+1,blank(avgSpaces+1)));sb.append(blank(avgSpaces));sb.append(join(words,left+extraSpaces+1,right,blank(avgSpaces)));ans.add(sb.toString());}}//返回长度为n的由空格组成的字符串public String blank(int n){StringBuffer sb=new StringBuffer();for(int i=0;i<n;i++){sb.append(" ");}return sb.toString();}//将一个范围内单词之间插入空格，返回字符串。public StringBuffer join(String[] words,int left,int right,String sep){StringBuffer sb=new StringBuffer(words[left]);for(int i=left+1;i<right;++i){sb.append(sep);sb.append(words[i]);}return sb; }
}
