文本对齐__牛客网

JacobGo！

import java.util.ArrayList;


/**
 * 68. Text Justification
 * 
 * @author Jacob
 *
 *         理解题意：首先要做的就是确定每一行能放下的单词数，这个不难， 就是比较n个单词的长度和加上n -1个空格的长度跟给定的长度L来比较即可，
 *         找到了一行能放下的单词个数，然后计算出这一行存在的空格的个数， 是用给定的长度L减去这一行所有单词的长度和。得到了空格的个数之后，
 *         就要在每个单词***入这些空格，这里有两种情况， 比如某一行有两个单词"to"和
 *         "a"，给定长度L为6，如果这行不是最后一行，那么应该输出"to a"， 如果是最后一行，则应该输出 "to a"，
 *         所以这里需要分情况讨论，最后一行的处理方法和其他行之间略有不同。
 *         最后一个难点就是，如果一行有三个单词，这时候中间有两个空，如果空格数不是2的倍数，
 *         那么左边的空间里要比右边的空间里多加入一个空格，那么我们只需要用总的空格数除以空间个数，
 *         能除尽最好，说明能平均分配，除不尽的话就多加个空格放在左边的空间里
 *
 */
public class Solution {
    public ArrayList<String> fullJustify(String[] words, int maxWidth) {
        ArrayList<String> res = new ArrayList<String>();

		int n = words.length;
		int i = 0;

		while (i < n) {
			StringBuilder sb = new StringBuilder();
			int last = i + 1;
			int len = words[i].length();
			while (last < n && len + 1 + words[last].length() <= maxWidth) {
				len += 1 + words[last].length();
				last++;
			}
			// 最后一行
			if (last == n) {
				for (int j = i; j < n; j++) {
					sb.append(words[j] + " ");
				}
				sb.deleteCharAt(sb.length() - 1);
				for (int j = sb.length(); j < maxWidth; j++) {
					sb.append(" ");
				}
			} else {
				// 只有一个word
				if (last - i == 1) {
					sb.append(words[i]);
					for (int j = words[i].length(); j < maxWidth; j++)
						sb.append(" ");
				} else {// 有多个单词
					int wordNum = last - i;
					int wordTotal = 0;
					for (int j = i; j < last; j++) {
						wordTotal += words[j].length();
					}
					// eachSpace为每个单词间的空格数；r是余数，表示前r个空格数为eachSpace+1
					int eachSpace = (maxWidth - wordTotal) / (wordNum - 1);
					int r = (maxWidth - wordTotal) % (wordNum - 1);

					for (int j = i; j < last; j++) {
						sb.append(words[j]);
						if (j < last - 1) {
							for (int k = 0; k < eachSpace + ((j - i) < r ? 1 : 0); k++) {
								sb.append(" ");
							}
						}
					}
				}
			}
			res.add(sb.toString());
			i = last;
		}
		return res;
	}
    
}

发表于 2017-07-24 12:36:21 回复(0)

元气の悟空

class Solution {
public:
    vector<string> fullJustify(vector<string> &x, int L) {
        vector<string> res;
        int i,len=0,j,row=0,n=10000;
        if(L==0){
            res.push_back("");return res;
        }
        vector<vector<string> > G(n+5,vector<string>());
        for(i=0;i<x.size();){
            int sum=0;
            for(j=i;j<x.size()&&sum<L;j++)
                sum+=x[j].length()+(j==i?0:1);
            if(sum>L) j--,sum-=x[j].length()+1;
            for(int k=i;k<j;k++) G[row].push_back(x[k]);
            row++,i=j;
            if(i+1==x.size()){
                G[row].push_back(x[i]);break;
            }
        }
        for(i=0;i<n;i++){
            int l=G[i].size(),space,sum=0,cnt,c=0,nextL=G[i+1].size();
            if(nextL==0) break;
            for(j=0;j<G[i].size();j++) sum+=G[i][j].length();
            sum=L-sum,space=(l==1?1:l-1);
            cnt=sum/space,c=sum%space;
            string tmp="";
            for(j=0;j<G[i].size();j++){
                tmp+=G[i][j];
                int k,q;
                if(c>0) k=cnt+1,c--;
                else k=cnt;
                if(G[i].size()==1||j+1!=G[i].size())
                    for(q=0;q<k;q++) tmp+=" ";
            }
            res.push_back(tmp);
        }
        string tmp="";
        for(j=0;j<G[i].size();j++) tmp+=(j==0?"":" ")+G[i][j];
        int curL=tmp.length();
        for(i=0,curL=L-curL;i<curL;i++) tmp+=" ";
        res.push_back(tmp);
        return res;
    }
};

发表于 2017-10-25 09:13:57 回复(0)

C/C++

ltaoj

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> result;
        for (int start = 0, end; start < words.size();start = end) {
            int width = 0;
            for (end = start; end < words.size() && words[end].size() + width + end - start <= L;end++) {
                width += words[end].size();
            }
            int space = 1;
            int extra = 0;
            if (end - start != 1 && end != words.size()) {
                space = (L - width) / (end - start - 1);
                extra = (L - width) % (end - start - 1);
            }
            string line(words[start]);
            for (int m = start + 1; m < end;m++) {
                line += string(space, ' ');
                if (extra-- > 0) {
                    line += " ";
                }
                line += words[m];
            }
            line += string(L - line.size(), ' ');
            result.push_back(line);
        }
        return result;
    }
};

发表于 2019-11-09 19:57:19 回复(1)

C/C++

nbgao

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> result;
        int l = words.size();         for(int i=0,j;i<l;i=j)         {             int width = 0;             for(j=i;j<l && width+words[j].size()+j-i <= L;j++)                 width += words[j].size();             int space = 1, extra = 0;             if(j-i!=1 && j!=l){                 space = (L-width)/(j-i-1);                 extra = (L-width)%(j-i-1);             }             string line(words[i]);             for(int k=i+1;k<j;k++)             {                 line += string(space, ' ');                 if(extra-- > 0)                     line += " ";                 line += words[k];             }             line += string(L-line.size(), ' ');             result.push_back(line);         }          return result;
    }
};

发表于 2017-10-05 01:08:47 回复(0)

后劲好大

import java.util.ArrayList;
public class Solution {
    public ArrayList<String> fullJustify(String[] words, int L) {
        ArrayList<String> res = new ArrayList<>();
		//if(words == null || words.length == 0 || L <= 0)
		//	return res;
		
		int i = 0;
		while(i < words.length){
			int len = words[i].length();
			String line = words[i];
			int j = i + 1;
			// 找到能加到一行的最多的单词
			for(; j < words.length && len + words[j].length() + 1 <= L; j++){
				len += words[j].length() + 1;
			}
			if(j < words.length){
				// 计算有多少个多的空格以及插槽
				int space = L - len;
				int gap = j - i - 1;
				// 没有插槽，那就无脑往单词后面加空格
				if(gap == 0){
					while(line.length() < L){
						line += " ";
					}
				}
				else{
					for(int p = i + 1; p < j; p++){
						line += " ";
						// 除了每个单词后原本的空格，还可以每个单词后面加
						// space/gap个空格
						for(int q = 0; q < space / gap; q++)
							line += " ";
						// 不足以每个插槽都加一个空格，那就加在前面几个插槽
						if(p - i <= space % gap)
							line += " ";
						line += words[p];
					}
				}
			}
			else{	// 	最后一行
				for(int p = i + 1; p < words.length; p++)
					line += " " + words[p];
				while(line.length() < L){
					line += " ";
				}
			}
			res.add(line);
			i = j;
		}
		return res;		
    }
}

发表于 2017-06-06 16:45:09 回复(0)

C/C++

枫火琅琊

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
      vector<string> result;
        for(int i = 0, j; i < words.size(); i = j) {
            int width = 0;
            for(j = i; j < words.size() && width + words[j].size() + j - i <= L; j++) {
                width += words[j].size();
            }
            int space = 1, extra = 0;
            if(j - i != 1 && j != words.size()) {
                space = (L - width) / (j - i - 1);
                extra = (L - width) % (j - i - 1);
            }
            string line(words[i]);
            for(int k = i + 1; k < j; k++) {
                line += string(space, ' ');
                if(extra-- > 0) {
                    line += " ";
                }
                line += words[k];
            }
            
            line += string(L - line.size(), ' ');
            result.push_back(line);
        }
        return result;
    }
};

发表于 2017-07-24 13:53:34 回复(1)

W.sl

public class Solution {
    public ArrayList<String> fullJustify(String[] words, int L) {
        ArrayList<String> list = new ArrayList<String>();
        int n=words.length;
        int i=0;
        while(i<n){
            int len = words[i].length();
            String line = words[i];
            int j=i+1;
            for(;j<n&&len+1+words[j].length()<=L;j++){
                len +=1+words[j].length();
                
            }
            if(j==n){//处理最后一行
                for(int k=i+1;k<n;k++){
                    line+=" "+words[k];
                }
                while(line.length()<L){
                    line+=" ";
                }
            }else{//处理普通的行
                int white = L-len;//多余的空格
                int slot = j-i-1;//单词之间的槽数
                if(slot==0){//处理行中只有一个单词的情况
                    while(line.length()<L){
                    	line+=" ";
                	}
                }else{
                    for(int k=i+1;k<j;k++){
                        line+=" ";
                        for(int m=0;m<white/slot;m++){//计算每个空槽应该有几个空格
                            line+=" ";
                        }
                        if(k-i<=white%slot){//多余的空格加到前几个空槽里
                            line+=" ";
                        }
                        line+=words[k];
                    }
                }
            }
            list.add(line);
            i=j;
        }
        return list;
    }
}

发表于 2016-11-07 15:20:49 回复(0)

C/C++

华科不平凡

基本思路——遍历整个单词数组，并执行以下步骤：

求本行的单词个数以及单词的长度和
求均匀空格数和额外空格数
均匀填充单词
如果未填满，在末尾补空格

代码如下：

//
// Created by jt on 2020/9/25.
//
#include 
#include 
using namespace std;
class Solution {
public:
    vector fullJustify(vector &words, int L) {
        vector res;
        for (int start = 0, end; start < words.size(); start = end) {
            int width = 0, spaces = 1, extra = 0;
            // 定位本行的末尾单词（注意这里的end为末尾单词的后一个下标）
            for (end = start; end < words.size() && width + words[end].size() + (end-start) <= L; ++end) {
                width += words[end].size();
            }
            // 求空格数和额外空格数
            if (end - start != 1 && end != words.size()) {
                spaces = (L - width) / (end - start - 1);
                extra = (L - width) % (end - start - 1);
            }
            // 填充本行字符串
            string line(words[start]);
            for (int i = start + 1; i < end; ++i) {
                line += string(spaces, ' ');
                if (extra-- > 0) line += " ";
                line += words[i];
            }
            // 填充末尾空格
            line += string(L-line.size(), ' ');
            res.push_back(line);
        }
        return res;
    }
};

编辑于 2020-09-26 15:08:47 回复(0)

小凯~

为啥显示格式错误，有大佬提点一下吗？

vector<string> fullJustify(vector<string>& words, int L)

{
vector<string>res; string tmp;
int num = 0; vector<string>tmp1;
for (int i = 0; i < words.size();)
{
if (tmp1.size() > 0)
{
if (tmp1.size() > 1)
{
int len = tmp1.size();
int a = L - num;
int b = a % (len - 1);
int c = a / (len - 1);
tmp = tmp + tmp1[0];
int t1 = b + c;
while (t1 > 0)
{
tmp = tmp + " ";
t1--; num++;
}
for (int j = 1; j < len - 1 ; ++j)
{
tmp = tmp + tmp1[j];
int t = c;
while (t > 0)
{
tmp = tmp + " ";
t--; num++;
}
}
tmp = tmp + tmp1[len - 1];
}
else if (tmp1.size() == 1)
{
tmp = tmp + tmp1[0];
while (num < L)
{
tmp = tmp + " ";
num++;
}
}
res.push_back(tmp);
num = 0; tmp.clear(); tmp1.clear();
}

while (i < words.size() && num + tmp1.size() <= L && num + words[i].size() + tmp1.size() <= L)
{
num = num + words[i].size();
tmp1.push_back(words[i]);
i++;
}
}
if (tmp1.size() > 0)
{
for (auto i : tmp1)
{
tmp = tmp + i;
if (num < L)
{
tmp = tmp + " ";
}
num++;
}
while (num < L)
{
tmp = tmp + " ";
num++;
}
res.push_back(tmp);
num = 0; tmp.clear(); tmp1.clear();
}

return res;
}
};

发表于 2020-05-30 18:24:32 回复(0)

ponmmains

import java.util.*;
/*贪心法*/
public class Solution {
public ArrayList<String> fullJustify(String[] words, int L) {
ArrayList<String> res = new ArrayList<>();
int n = words.length, i = 0;

while (i < n) {
StringBuilder sb = new StringBuilder();
int next = i + 1;
int len = words[i].length();
while (next < n && len + 1 + words[next].length() <= L) {
len += 1 + words[next].length();
next++;
}

if (next == n) {
for (int k = i; k < n; k++)
sb.append(words[k] + " ");
sb.deleteCharAt(sb.length() - 1);
len = sb.length();
for (int j = sb.length(); j < L; j++)
sb.append(' ');
}else {
int wordNum = next - i;
if (wordNum == 1) {
sb.append(words[i]);
for (int j = sb.length(); j < L; j++)
sb.append(' ');
}else {
len = 0;
for (int k = i; k < next; k++)
len += words[k].length();
int num = (L - len) / (wordNum - 1);
int r = (L - len) % (wordNum - 1);
for (int k = i; k < next; k++) {
sb.append(words[k]);
if (k != next - 1) {
int temp = (k - i) < r ? num + 1 : num;
for (int j = 0; j < temp; j++)
sb.append(' ');
}
}
}
}

i = next;
res.add(sb.toString());
}

return res;
}
}

发表于 2020-03-07 12:16:14 回复(0)

Leomh

vector<string> fullJustify(vector<string> &words, int L) {
        vector<string>ans;
        vector<int>node,length;//记录每一行结束点及长度
        node.push_back(0);
        length.push_back(0);
        int totlen = 0;
        int len = words.size();
        for(int i=0;i<len;++i){
            if(!totlen)totlen += words[i].size()+1;
            else if(totlen+words[i].size()<=L)totlen += words[i].size()+1;
            else {
                length.push_back(totlen);
                node.push_back(i);
                totlen = words[i].size()+1;
            }
        }
        for(int i=1;i<node.size();++i){
            int num = node[i]-node[i-1]-1;//空白区域数量
            int blen = L-length[i]+num+1;//空白区域总长
            int wei = num==0?0:blen/num;//空白区域均长
            int offset = num==0?0:blen%num;//左边空白偏置
            string res = "";
            for(int t=node[i-1],k=0;t<node[i];++t,++k){
                res += words[t];
                if(t == node[i]-1)break;
                int truewei = k<offset?wei+1:wei;//补偏置
                string tmp(truewei,' ');
                res += tmp;
            }
            res += string(L-res.size(),' ');
            ans.push_back(res);
        }
    //最后一行
        string res = "";
        for(int i=node.back();i<words.size();++i){
            res += i==node.back()?"":" ";
            res += words[i];
        }
        res += string(L-res.size(),' ');
        ans.push_back(res);
        return ans;
    }

编辑于 2019-08-27 23:46:08 回复(0)

only_唯

//尽可能多地往每行放置单词
//尽可能均匀地分配单词间的空格数量
//并且左侧放置的空格数多于右侧
//文本的最后一行应为左对齐，且单词间不能插入额外的空格
class Solution {
public:
    vector fullJustify(vector& words, int maxWidth) {
        vector res;
        int cnt=words.size();
        //start到end间的单词总长totalLen进行均匀排列
        int start=0,end=0,totalLen=0;
        for(int i=0;i<cnt;i++){
            totalLen+=words[i].size()+1;//+1表示单词之间至少一个空格
            if(totalLen-1>maxWidth){
                end=i-1;
                //numBlank表示剩余需要填充的空格数
                int numBlank=maxWidth-(totalLen-(end-start+2)-words[i].size());
                 //将start~end将的单词均匀放入string中
                fullJustifyCore(words,res,start,end,numBlank,maxWidth);
                totalLen=words[i].size()+1;
                start=i;
            }
        }
        //res中的放入最后一个元素
        string s(maxWidth,' ');
        int pos=0;
        for(int i=start;i<cnt;i++){
            s.replace(pos,words[i].size(),words[i]);
            pos+=words[i].size()+1;
        }
        res.push_back(s);
        return res;
    }
    void fullJustifyCore(vector& words,vector& res,int start,int end,int numBlank,int maxWidth){
        string s(maxWidth,' ');
        int pos=0,cnt=0;
        //单词之间的空隙数
        int numSpace=end-start;
        //每个单词之间至少间隔num1
        int num1=numSpace!=0?numBlank/numSpace:0;
        //前num2个单词之间间隔num1+1
        int num2=numSpace!=0?numBlank%numSpace:0;
        for(int i=start;i<=end;i++){
            s.replace(pos,words[i].size(),words[i]);
            pos+=words[i].size()+num1;
            cnt++;
            if(cnt<=num2)
                pos++;
        }
        res.push_back(s);
    }
};

发表于 2019-06-02 13:29:10 回复(0)

darkmaycry

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> result;
        int start = 0;
        int n = words.size();
        int tmp_len = 0;
        for (int i=0; i<n; i++)
        {
            if (tmp_len + words[i].length() + i-start > L)
            {

                int spaces = L - tmp_len;
                if (i - start > 1)
                {
                    int k = spaces / (i - start -1);
                    int extra = spaces % (i - start -1);
                    string s = words[start];
                    for (int j=start+1; j<i; j++)
                    {
                        s = s + string(" ", k);
                        if (extra > 0)
                        {
                            s = s + " ";
                            extra--;
                        }
                        s = s + words[j];
                    }
                    result.push_back(s);
                }
                else
                    result.push_back(words[start] + string(" ", spaces));
                start = i;
                tmp_len = words[i].length();
            }
            else
            {
                tmp_len += words[i].length();
            }
        }

        if (start < n)
        {
            string s = words[start];
            tmp_len = s.length();
            for (int i=start+1; i<n; i++)
            {
                s = s + " " + words[i];
                tmp_len += words[i].length() + 1;
            }
            if (tmp_len < L)
                s = s + string(" ", L-tmp_len);
            result.push_back(s);
        }
        return result;
    }
};

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为25.00%

用例:
["Listen","to","many,","speak","to","a","few."],6

对应输出应该为:

["Listen","to ","many, ","speak ","to a","few. "]

你的输出为:

["Listen","to ","many, ","speak ","to ","few. "]

同样的输入，同样的程序，为什么在本地测试输出正确，在线测试的结果就不一样，少了一个"a"。

编辑于 2019-03-10 20:53:23 回复(1)

llch__

   public ArrayList<String> fullJustify(String[] words, int L) {
        int left = 0;
        int right = 0;
        int len = 0;
        ArrayList<String> result = new ArrayList<String>();
        for(int i=0; i<words.length; i++){
            if(words[i].length()+len + i-left > L){
                right = i - 1;               
                result.add(generate(words, left, right, len, L));
                len = words[i].length();
                left = i;
            }
            else{
                len += words[i].length();
            }    
        }
        result.add(generate(words, left, words.length-1, len, L));
        return result;
    }
    private String generate(String words[], int left, int right, int len,  int L){
        StringBuffer temp = new StringBuffer("");
        if(right != words.length-1){
            int blanknum = L - len;
            int gapnum = right - left;
            int mod = 0;
            int div = 0;
            if(gapnum != 0){
                mod = blanknum % gapnum;
                div = blanknum / gapnum;
            }                
            for(int j=left; j<=right; j++){
                temp.append(words[j]);
                if(j<right){
                    if(j-left < mod){
                        temp.append(blankline(div+1));
                    }
                    else{
                        temp.append(blankline(div));
                    }
                }
            }
        }
        else{
            for(int j=left; j<=right; j++){
               temp.append(words[j]);
               if(j<right)  temp.append(" ");
            }
        }
        while(temp.length()!=L){
           temp.append(" ");
        }    
        return temp.toString();
    }
    private String blankline(int num){
        StringBuffer buffer = new StringBuffer("");
        while(num-- > 0) buffer.append(" ");
        return buffer.toString();
    }

发表于 2018-07-27 13:04:24 回复(0)

C/C++

蛟龙吐火球丰

//懒的看题，没看到末行条件，浪费好多时间
class Solution {
public:
    string base;
    void getbase(int l)
    {
        base.clear();
        for(int i=0;i<l;i++)
            base+=' ';
    }
    string merge(vector<string>& co,vector<int>& inters,int n)
    {
        string out="";
        for(int i=0;i<n;i++)       
        {
            out+=co[i];          
            out+=base.substr(0,inters[i]);
        }

        return out;
    }
    vector<string> fullJustify(vector<string> &words, int L)
    {
        vector<string> out;
        if(words.empty())
            return words;
        int sz=words.size();
        getbase(L);
        for(int i=0;i<sz;)
        {
            int curl=0;
            vector<string> tp;
            int num=0;
            while(i<sz)
            {                
                if(curl+words[i].length()<=L)
                {
                    tp.push_back(words[i]);
                    curl+=words[i].length()+1;
                    i++;
                    num++;
                }
                else
                    break;
            }
            curl-=num;
            if(num==1)
            {
                string s=tp[0];
                s+=base.substr(0,L-s.length());              
                out.push_back(s);
                continue;
            }

            if(i<sz)
            {         
                int dist=L-curl;
                int ins=num-1;  
                int bs=dist/ins;
                int ad=dist%ins;
                vector<int> inter(num);
                for(int i=0;i<num-1;i++)
                {
                    inter[i]=bs;
                    if(ad>0)
                    {   
                        inter[i]++;
                        ad--;
                    }
                }           
                inter[num-1]=0;    
                out.push_back(merge(tp,inter,num));
            }
            else
            {
                string s="";
                for(int i=0;i<num;i++)
                    i==0?s+=tp[i]:s+=' '+tp[i];
                int dist=L-s.length();
                while(dist--)
                    s+=' ';
                out.push_back(s);
            }
        }
        return out;
    }
};

发表于 2018-06-18 08:38:22 回复(0)

Java

城市里的养猫者

def fullJustify(self, words, maxWidth): res, cur, num_of_letters = [], [], 0 for w in words: if num_of_letters + len(w) + len(cur) > maxWidth: for i in range(maxWidth - num_of_letters):
                cur[i%(len(cur)-1 or 1)] += ' ' res.append(''.join(cur))
            cur, num_of_letters = [], 0 cur += [w]
        num_of_letters += len(w) return res + [' '.join(cur).ljust(maxWidth)]

How does it work? Well in the question statement, the sentence "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" was just a really long and awkward way to say round robin. The following line implements the round robin logic:

for i in range(maxWidth - num_of_letters):
                cur[i%(len(cur)-1 or 1)] += ' '

What does this line do? Once you determine that there are only k words that can fit on a given line, you know what the total length of those words is num_of_letters. Then the rest are spaces, and there are (maxWidth - num_of_letters) of spaces. The "or 1" part is for dealing with the edge case len(cur) == 1.

The following is my older solution for reference, longer and less clear. The idea is the same, but I did not figure out the nice way to distribute the space at the time.

def fullJustify(self, words, maxWidth): res, cur, num_of_letters = [], [], 0 for w in words: if num_of_letters + len(w) + len(cur) > maxWidth: if len(cur) == 1: res.append( cur[0] + ' '*(maxWidth - num_of_letters) ) else:
                num_spaces = maxWidth - num_of_letters
                space_between_words, num_extra_spaces = divmod( num_spaces, len(cur)-1) for i in range(num_extra_spaces):
                    cur[i] += ' ' res.append( (' '*space_between_words).join(cur) )
            cur, num_of_letters = [], 0 cur += [w]
        num_of_letters += len(w) res.append( ' '.join(cur) + ' '*(maxWidth - num_of_letters - len(cur) + 1) ) return res

发表于 2017-03-12 12:11:43 回复(0)

C/C++

油头教授的坩埚

vector<string> fullJustify(vector<string> &words, int L) { vector<string> res; for(int i = 0, k, l; i < words.size(); i += k) { for(k = l = 0; i + k < words.size() and l + words[i+k].size() <= L - k; k++) {
            l += words[i+k].size();
        } string tmp = words[i]; for(int j = 0; j < k - 1; j++) { if(i + k >= words.size()) tmp += " "; else tmp += string((L - l) / (k - 1) + (j < (L - l) % (k - 1)), ' ');
            tmp += words[i+j+1];
        }
        tmp += string(L - tmp.size(), ' ');
        res.push_back(tmp);
    } return res;
}

For each line, I first figure out which words can fit in. According to the code, these words are words[i] through words[i+k-1]. Then spaces are added between the words. The trick here is to use mod operation to manage the spaces that can't be evenly distrubuted: the first (L-l) % (k-1) gaps acquire an additional space.

发表于 2017-03-12 12:11:02 回复(0)

OutLaws

//主要分情况判断。首先分两大类，末行和非末行；然后末行所有单词间放一个空格，最后面补充空格；非末行再分两类，如果只有一个单词就靠左放，右边补空格；如果有多个单词，即计算有几个间隔num和几个多余的空格extra（除每两个单词间一个空格外多余的），每个间隔再多方extra/num个，前extra%num个间隔再多放个空格。
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L);
};

vector<string> Solution::fullJustify(vector<string>& words, int L) {
    int n = words.size();
    int i = 0;
    string line;
    int len;
    int j;
    vector<string> res;
    while (i<n) {
        len = words[i].size();
        line = words[i];
        for (j=i+1; j<n&&len+1+words[j].size()<=L; ++j) {
            len += 1 + words[j].size();
        }
	//末行
        if (j == n) {
            for (int k=i+1; k<n; ++k) {
                line += " " + words[k];
            }
            while (line.size()<L) {
                line += " ";
            }
        }
        else {
            int extraspace = L-len;
            int numspace = j-i-1;
		//非末行只有一个单词
            if (numspace == 0) {
                while (line.size()<L) {
                    line += " ";
                }    
            }
            else {
		//非末行，有多个单词
                for (int l=i+1; l<j; ++l) {
                    line += " ";
                    for (int k=0; k<extraspace/numspace; ++k) {
                        line += " ";
                    }
                    if (l-i <= extraspace%numspace) {
                        line += " ";
                    }
                    line += words[l];
                }    
            }
            
            
        }
        res.push_back(line);      
        i = j;
    }
    return res;
}

int main(int argc, const char *argv[]) {
    vector<string> words = {"This", "is", "an", "example", "of", "text", "justfication"};
    Solution so;
    vector<string> res = so.fullJustify(words, 16);
    return 0;
}

发表于 2016-09-17 15:00:21 回复(0)

who cares

case通过率为33.33%
测试用例:
["What","must","be","shall","be."],12

对应输出应该为:

["What must be","shall be. "]

你的输出为:

["What must be","shall be."]
有人能看出这里面的区别吗？感觉这是在鸡蛋里面挑骨头啊！

发表于 2016-09-01 16:50:16 回复(2)

xeclipse

class Solution {
public:
    string generate(vector<string>& tmp, int L){
        int count=0;
  for(int m=0;m<tmp.size();m++){
           count+=tmp[m].length();
        }
        int allSpaceLen=L-count;
        int frac=tmp.size()-1;
        if(frac==0) {
            string space(allSpaceLen,' ');
            string ret=tmp[0]+space;
            return ret;
        }
        string finall="";
        int sLen=allSpaceLen/frac;
        int mod=allSpaceLen%frac;
        string space(sLen,' ');
        if(mod==0){
            
            for(int k=0;k<frac;k++){
                finall+=(tmp[k]+space);
            }
            finall+=tmp[tmp.size()-1];
        }
        else{
            string space1(sLen+1,' ');
            int j=0;
            for(;j<mod;j++){
                finall+=(tmp[j]+space1);
            }
            for(;j<tmp.size()-1;j++){
                finall+=(tmp[j]+space);
            }
            finall+=tmp[tmp.size()-1];
        }
        return finall;
    }
    
    
string lastLine(vector<string>& tmp, int L){
 string ret="";
 for(int i=0;i<tmp.size();i++){
  ret+=tmp[i];
  if(ret.length()<L){
   ret+=" ";
  }
 }
 if(ret.length()<L){
  string space(L-ret.length(),' ');
  ret+=space;
 }
 return ret;
}
    
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> ret;
        vector<string> tmp;
        int count=0;
        for(int i=0;i<words.size();i++){
            count+=words[i].length();
            if(count>L){
                count-=words[i].length();
                ret.push_back(generate(tmp,L));
                tmp.clear();
                count=words[i].length();
            }
            else{
            }
            tmp.push_back(words[i]);
            count+=1;
        }
        ret.push_back(lastLine(tmp,L));
  return ret;
    }
};

发表于 2016-08-05 21:12:37 回复(1)

文本对齐

问题信息

热门推荐

通过挑战的用户

相关试题