程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Text Justification

LeetCode Text Justification

編輯:關於C++

LeetCode解題之Text Justification


原題

把一個集合的單詞按照每行L個字符存放,不足的在單詞間添加空格,每行要兩端對齊(即兩端都要是單詞),如果空格不能均勻分布在所有間隔中,那麼左邊的空格要多於右邊的空格,最後一行靠左對齊,每個單詞間一個空格。

注意點:

單詞的順序不能發生改變 中間行也可能出現只有一個單詞,這時要靠左對齊 每行要盡可能多的容納單詞

例子:

輸入: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16

輸出:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

解題思路

這道題比較繁瑣,題目就一大段。采用雙指針的方法來標記當前行的單詞,如果加上下一個單詞的長度和每個單詞間至少一個空格時的總長度大於目標長度,說明此時的單詞就是該行應該存放的。要分是否只有一個單詞還是多個單詞進行討論,如果有多個單詞,需要平均分配單詞間的空格。現在可以知道總的空格數和單詞間隔數,所以計算單詞間的間隔比較簡單,注意多余的空格要優先添加到左邊的單詞間隔中。不要忘記添加最後一行的單詞。

AC源碼

class Solution(object):
    def fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        start = end = 0
        result, curr_words_length = [], 0
        for i, word in enumerate(words):
            if len(word) + curr_words_length + end - start  > maxWidth:
                if end - start == 1:
                    result.append(words[start] + ' ' * (maxWidth - curr_words_length))
                else:
                    total_space = maxWidth - curr_words_length
                    space, extra = divmod(total_space, end - start - 1)
                    for j in range(extra):
                        words[start + j] += ' '
                    result.append((' ' * space).join(words[start:end]))
                curr_words_length = 0
                start = end = i
            end += 1
            curr_words_length += len(word)
        result.append(' '.join(words[start:end]) + ' ' * (maxWidth - curr_words_length - (end - start - 1)))
        return result


if __name__ == "__main__":
    assert Solution().fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16) == [
        "This    is    an",
        "example  of text",
        "justification.  "
    ]
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved