leetcode 68. Text Justification 文本对齐

男娘i 2022-06-09 11:54 189阅读 0赞

Given an array of words and a length L, format the text such that each line has exactly L 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 L 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.

For example,  
words: \[“This”, “is”, “an”, “example”, “of”, “text”, “justification.”\]  
L: 16.

Return the formatted lines as:  
\[  
“This is an”,  
“example of text”,  
“justification. ”  
\]  
Note: Each word is guaranteed not to exceed L in length.

这道题考察的就是给定的文本使对齐，就是找到每一行的words然后对齐即可。主要的做法如下：  
1）寻找若干个word，确保这个几个word要在一行；  
2）平均分配空格，假如可以平均分配直接平均分配，假如不可以平均，然后把多余的空格尽量平分给前面的words，不过要针对最后一行做特殊处理。

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * 这个问题十分简单，就是十分麻烦
     * 
     * */
    public class Solution 
    {
        public List<String> fullJustify(String[] words, int maxWidth) 
        {
            List<String> res=new ArrayList<String>();
            if(words==null || words.length<=0)
                return res;
            if(maxWidth<=0)
            {
                res.add("");
                return res;
            }
    
            int i=0,j=0;
            while(i<words.length)
            {
                //找到应该组合为一行的word元素
                int lenFowWords=0;
                List<String> one=new ArrayList<String>();
                for(j=i;j<words.length;j++)
                {
                    if(lenFowWords+words[j].length()+ one.size() <= maxWidth )
                    {
                        lenFowWords=lenFowWords+words[j].length();
                        one.add(words[j]);
                    }else
                        break;      
                }
                i=j;
    
                //最后一行的特殊处理
                if(i==words.length)
                {
                    StringBuilder tmp=new StringBuilder();
                    tmp.append(one.get(0));
                    for(int k=1;k<one.size();k++)
                        tmp.append(" "+one.get(k));
    
                    //粘贴多余的空格
                    int moreSp=maxWidth-tmp.length();
                    for(int g=0;g <moreSp ;g++)
                        tmp.append(" ");
    
                    res.add(tmp.toString());
                    continue;
                }
    
                if(one.size()==1)
                {
                    StringBuilder tmp=new StringBuilder();
                    tmp.append(one.get(0));
    
                    //粘贴多余的空格
                    for(int k=0;k<maxWidth-lenFowWords;k++)
                        tmp.append(" ");
    
                    res.add(tmp.toString());
    
                }else
                {
                    //计算平均量
                    int sp=(maxWidth-lenFowWords) / (one.size()-1);
                    StringBuilder spBuilder=new StringBuilder();
                    for(int k=0;k<sp;k++)
                        spBuilder.append(" ");
    
                    if( (maxWidth-lenFowWords) % (one.size()-1)==0 )
                    {
                        StringBuilder tmp=new StringBuilder();
                        tmp.append(one.get(0));
                        for(int k=1;k<one.size();k++)
                            tmp.append(spBuilder.toString()+one.get(k));
    
                        res.add(tmp.toString());
                    }else
                    {
                        StringBuilder tmp=new StringBuilder();
                        tmp.append(one.get(0));
    
                        //这个是为了尽量平均的分配空格
                        int moreSp=maxWidth-lenFowWords-(one.size()-1)*sp;
                        for(int k=1;k<one.size();k++)
                        {
                            if(moreSp>0)
                            {
                                tmp.append(" "+spBuilder.toString()+one.get(k));
                                moreSp--;
                            }
                            else 
                                tmp.append(spBuilder.toString()+one.get(k));
                        }
                        res.add(tmp.toString());                
                    }   
                }
            }
            return res;
        }
    
        public static void main(String[] args) 
        {
            Solution solution=new Solution();
            String []words={
       "Listen","to","many,","speak","to","a","few."};
            int maxWidth=6;
    
            System.out.println(solution.fullJustify(words, maxWidth));
        }
    }

说实话，这道题十分繁琐，但是很简单，C++的做法先这么做吧

代码如下

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    
    class Solution 
    {
    public:
        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() && 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;
        }
    };