Leetcode 068 文字左右對齊 Python C

NO IMAGE

題目:

給定一個單詞陣列和一個長度 maxWidth,重新排版單詞,使其成為每行恰好有 maxWidth 個字元,且左右兩端對齊的文字。

你應該使用“貪心演算法”來放置給定的單詞;也就是說,儘可能多地往每行中放置單詞。必要時可用空格 ' ' 填充,使得每行恰好有 maxWidth 個字元。

要求儘可能均勻分配單詞間的空格數量。如果某一行單詞間的空格不能均勻分配,則左側放置的空格數要多於右側的空格數。

文字的最後一行應為左對齊,且單詞之間不插入額外的空格。

說明:

  • 單詞是指由非空格字元組成的字元序列。
  • 每個單詞的長度大於 0,小於等於 maxWidth
  • 輸入單詞陣列 words 至少包含一個單詞。

示例:

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

示例 2:

輸入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
輸出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解釋: 注意最後一行的格式應為 "shall be    " 而不是 "shall     be",
     因為最後一行應為左對齊,而不是左右兩端對齊。       
第二行同樣為左對齊,這是因為這行只包含一個單詞。

示例 3:

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

 

我寫的思路(Python):

演算法過程:1.通過設立指標(begin ,end)來圈定一個區間,使得這個區間裡的所有單詞能加入這一次要構造的字串中,其中要保留n-1的空格數(4個單詞至少留3個空)。

2.確立了要新增入這一行字串(輸出中的每一個字串)的單詞後,通過計算,得出還剩下的空間,然後把剩下的空間多一些分給在左邊的單詞,少一些分給在右邊的單詞。簡而言之,就是合理分配我們的空格。

 

3.最終把我們的字串結果加入答案,並且保證最後一個字串的寬度也達到標準。

 

class Solution:
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
#儲存答案
ans_list = []
#用來切割words的指標
i = 0
while i < len(words):#開始遍歷字串
beigin = i#選取的區間開始的指標
wordsum = 0 #所有數字加起來的總字數
leastspace = 0 #最少需要空幾個空格
end = i#選取的區間結尾的指標
oneresult = ""#儲存這一次添入最終結果的答案
#不斷去擴充套件end的範圍,在能新增的情況下不斷新增單詞
while end < len(words) and len(words[end])   wordsum   leastspace <= maxWidth:
leastspace  = 1
wordsum  = len(words[end])
end  = 1
leastspace -= 1
oneresult = ""
#如果end到了最後一項,也就是剛好把最後一個單詞也包括了
if end == len(words):
for i in words[beigin:end]:
oneresult  = i
if leastspace != 0:
#適當地新增空格
oneresult  = " "
leastspace -= 1
ans_list.append(oneresult)
break
realsum = 0 
for j in words[beigin:end]:
realsum  = len(j)#算出所有單詞的總字元數
#還剩下多少個位置可以留給空格
left_space = maxWidth - realsum
if leastspace != 0:
#分配給每個單詞後的空格
eachspace = left_space // (leastspace)
left_space2 = left_space - eachspace*leastspace
else:
oneresult  = words[beigin]   left_space*" "
ans_list.append(oneresult)
i = end
continue
oneresult = ""
for j in words[beigin:end]:#新增空格,並且保證先新增比較多的空格
oneresult  = j 
if leastspace > 0:
oneresult  = eachspace*" "
leastspace -= 1
if left_space2 > 0:#left_space2是用來新增額外的空格的,來營造出左邊的空格比較多的效果
oneresult  = " "
left_space2 -= 1
ans_list.append(oneresult)
i = end
#保證最後一項的maxWidth達到標準(補全空格)
if len(ans_list[-1]) < maxWidth:
ans_list[-1]  = " "*(maxWidth-len(ans_list[-1]))
return ans_list

 

 

 

C 解法:

這裡的思路跟python是非常像的,但我還是再多說一些。

這道題像極了word軟體裡面的文字左右對齊功能。

由於返回的結果是多行的,所以我們在處理的時候也要一行一行的來處理。

首先要做的就是確定每一行能放下的單詞數,這個不難,就是比較n個單詞的長度和加上n – 1個空格的長度跟給定的長度L來比較即可,找到了一行能放下的單詞個數,然後計算出這一行存在的空格的個數,是用給定的長度L減去這一行所有單詞的長度和。得到了空格的個數之後,就要在每個單詞後面插入這些空格,這裡有兩種情況,比如某一行有兩個單詞”to” 和 “a”,給定長度L為6,如果這行不是最後一行,那麼應該輸出”to   a”,如果是最後一行,則應該輸出 “to a  “,所以這裡需要分情況討論。

最後一行的處理方法和其他行之間略有不同。

後一個難點就是,如果一行有三個單詞,這時候中間有兩個空,如果空格數不是2的倍數,那麼左邊的空間裡要比右邊的空間裡多加入一個空格,那麼我們只需要用總的空格數除以空間個數,能除盡最好,說明能平均分配,除不盡的話就多加個空格放在左邊的空間裡,以此類推,具體實現過程還是看程式碼吧。

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;
}
};

 

沒什麼好總結的,因為這道題對演算法方面的考察太少,但是卻特別的繁瑣麻煩,所以個人不太推薦死死盯著這題。