[LeetCode] 68.Text Justification 文本左右對齊

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

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 extraspace is inserted between words.

Note:

• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

Example 1:

Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This    is    an",
"example  of text",
"justification.  "
]

Example 2:

Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What   must   be",
"acknowledgment  ",
"shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.

Example 3:

Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science  is  what we",
"understand      well",
"enough to explain to",
"a  computer.  Art is",
"everything  else  we",
"do                  "
]

我將這道題翻譯為文本的左右對齊是因?yàn)檫@道題像極了word軟件里面的文本左右對齊功能，這道題我前前后后折騰了快四個(gè)小時(shí)終于通過了OJ，完成了之后想著去網(wǎng)上搜搜看有沒有更簡單的方法，搜了一圈發(fā)現(xiàn)都差不多，都挺復(fù)雜的，于是乎就按自己的思路來說吧，由于返回的結(jié)果是多行的，所以我們在處理的時(shí)候也要一行一行的來處理，首先要做的就是確定每一行能放下的單詞數(shù)，這個(gè)不難，就是比較n個(gè)單詞的長度和加上n - 1個(gè)空格的長度跟給定的長度L來比較即可，找到了一行能放下的單詞個(gè)數(shù)，然后計(jì)算出這一行存在的空格的個(gè)數(shù)，是用給定的長度L減去這一行所有單詞的長度和。得到了空格的個(gè)數(shù)之后，就要在每個(gè)單詞后面插入這些空格，這里有兩種情況，比如某一行有兩個(gè)單詞"to" 和 "a"，給定長度L為6，如果這行不是最后一行，那么應(yīng)該輸出"to   a"，如果是最后一行，則應(yīng)該輸出 "to a  "，所以這里需要分情況討論，最后一行的處理方法和其他行之間略有不同。最后一個(gè)難點(diǎn)就是，如果一行有三個(gè)單詞，這時(shí)候中間有兩個(gè)空，如果空格數(shù)不是2的倍數(shù)，那么左邊的空間里要比右邊的空間里多加入一個(gè)空格，那么我們只需要用總的空格數(shù)除以空間個(gè)數(shù)，能除盡最好，說明能平均分配，除不盡的話就多加個(gè)空格放在左邊的空間里，以此類推，具體實(shí)現(xiàn)過程還是看代碼吧：

class Solution {
public:
    vector<string> fullJustify(vector<string> &words, int L) {
        vector<string> res;
        int i = 0;
        while (i < words.size()) {
            int j = i, len = 0;
            while (j < words.size() && len + words[j].size() + j - i <= L) {
                len += words[j++].size();
            }
            string out;
            int space = L - len;
            for (int k = i; k < j; ++k) {
                out += words[k];
                if (space > 0) {
                    int tmp;
                    if (j == words.size()) { 
                        if (j - k == 1) tmp = space;
                        else tmp = 1;
                    } else {
                        if (j - k - 1 > 0) {
                            if (space % (j - k - 1) == 0) tmp = space / (j - k - 1);
                            else tmp = space / (j - k - 1) + 1;
                        } else tmp = space;
                    }
                    out.append(tmp, ' ');
                    space -= tmp;
                }
            }
            res.push_back(out);
            i = j;
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(68.文本左右對齊)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)文本左右對齊內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論