首页 > 代码库 > leetcode第一刷_Text Justification

leetcode第一刷_Text Justification

这个题的接受率好低,搞得我一直不敢做。后来认真的看了一下题目,不是非常难嘛。字符串的题目ac率就是低,除了难,还由于它的測试用例太多。

思路不难,主要是由于特殊情况太多。纯模拟,我把全部的情况罗列一下,细致一点的话就能写好了。

1. 当word为空,也就是""时,应该返回一行跟L数目相等的空格。

这样的情况须要提前推断和处理。

2. 当当前行不是最后一行时,应该尽可能多的放单词,单词不能截断。在这一行上,单词应该分布的尽可能均匀,且要把这一行填满,效果就跟word排版里面的撑满整行非常像。如何实现这个功能呢?我的做法是先确定这一行中能放多少个单词。注意计算的时候。要在单词之间插入一个空格。

然后看看这一行中一共须要插入多少个空格(L-单词的总长度)。用 总的空格数/(单词数-1),就知道每一个单词之间至少插入多少个空格。假设还有剩余(总空格数%(单词数-1)),就从左往右,每次填上一个,用完为止。

另一种情况,假设这一行中仅仅能放一个单词。要把这个单词放在最左边,然后加入空格到L长度。

3. 假设当前行是最后一行,那么要将单词尽可能的往左边排列,单词之间插入一个空格。右側用空格填充到L。

如何知道当前行是不是最后一行呢。我的方法是每次确定单词范围时,看看这个范围的尾部是不是word的结尾。

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        int msize = words.size();
        int i=0, j, part, tpl;
        vector<string> res;
        if(words[0] == ""){
            string s(L, ‘ ‘);
            res.push_back(s);
            return res;
        }
        string tpline, spspace;
        while(i<msize){
            part = 1;
            tpl = words[i].length();
            j = i+1;
            while(j<msize&&tpl+words[j].length()+part<=L){
                tpl += words[j].length();
                ++part;
                ++j;
            }
            --part;
            tpline = words[i];
            if(j != msize&&part!=0){
                int spaces = L-tpl;
                int extraspace = spaces%part;
                int spa=spaces/part;
                string sspace(spa, ‘ ‘);
                for(int k=i+1;k<j;k++){
                    spspace = sspace;
                    if(extraspace>0){
                        spspace += " ";
                        --extraspace;
                    }
                    tpline += spspace + words[k];
                }
                res.push_back(tpline);
            }else{
                for(int k=i+1;k<j;k++){
                    tpline += " " + words[k];
                }
                int l=tpline.length();
                for(int k=0;k<L-l;k++)
                	tpline += " "; 
                res.push_back(tpline);
            }
            //cout<<tpline<<endl;
            i = j;
        }
        return res;
    }
};


leetcode第一刷_Text Justification