Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Text Justification

Leetcode algorithms 第 68 题:Text Justification。

题目

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 exactlyL 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.

解答

给n个单词和一个长度L,要求把所有的单词逐行摆放,每行放尽量多的单词,一个单词不能占两行,一行内的单词尽量均匀分布,不能均匀分布时尽量左边的单词空格较大。

直接寻找能够放在一行的最大单词数量,求出这些单词的长度以及剩下的空格数目,把空格数目平均分给每个单词,除不尽的空格数分给靠左边的单词,然后进行输出。

注意一行只有一个单词的特殊情况,以及最后一行的输出。

具体代码如下:

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> ans;
        for (int i = 0, j = 0, sum = 0; j < words.size(); j++) //i为起点单词,j为终点单词
        {
            sum += words[j].size() + 1; //当前单词所占长度(每个单词末尾有一个空格)
            if (j == words.size() - 1) //到达末尾
            {
                string tem = words[i]; //从左到右摆放
                for (int k = i + 1; k <= j; k++) tem += " " + words[k];
                tem += string(L - tem.size(), ' '); //补充最右的空格字符
                ans.push_back(tem);
            }
            else if (sum + words[j+1].size() > L) //加上下一个单词的话长度会超,于是输出一行
            {
                sum = L - (sum - (j - i + 1)); //空格数
                int num = j - i; //单词数-1,间隙数
                if (num == 0) //只有一个单词需要额外讨论
                {
                    ans.push_back(words[i] + string(L - words[i].size(), ' '));
                }
                else
                {
                    int a = sum / num, b = sum % num; //平均每个单词后接a个空格,前b个单词的空格长度会多1
                    string tem;
                    for (int k = i; k < i + b; k++) tem += words[k] + string(a + 1, ' ');
                    for (int k = i + b; k < j; k++) tem += words[k] + string(a, ' ');
                    tem += words[j];
                    ans.push_back(tem);
                }
                i = j + 1, sum = 0; //设置新的起点和长度
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论