leetcode: 68. Text Justification [✗]

Problem

```# 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.```

AC

```class Solution(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
lines = []
i = 0
while i<len(words):
llen = 0
cur = i
while i<len(words):
llen += len(words[i])
if llen>maxWidth:
llen -= len(words[i])
break
llen+=1
i+=1

llen -=1
if i != len(words):
wordcnt = i-cur
extra = maxWidth-llen
if wordcnt>1:
spaces = extra/(wordcnt-1)
r = extra%(wordcnt-1)
else:
spaces = extra
r = 0
else:
spaces = 0
r = 0

line = ""
for word in words[cur:i]:
line += word
line += " "*(spaces+1)
if r>0:
line += " "
r -= 1

line = line[:maxWidth]
if len(line)<maxWidth:
line+=" "*(maxWidth-len(line))

lines.append(line)

return lines

# Time:  O(n)
# Space: O(k), k is maxWidth.
class Solution2(object):
def fullJustify(self, words, maxWidth):
"""
:type words: List[str]
:type maxWidth: int
:rtype: List[str]
"""
if i < spaceCnt:
return 1 if is_last else (maxWidth // spaceCnt) + int(i < maxWidth % spaceCnt)
return 0

def connect(words, maxWidth, begin, end, length, is_last):
s = []  # The extra space O(k) is spent here.
n = end - begin
for i in range(n):
s += words[begin + i],
s += ' ' * addSpaces(i, n - 1, maxWidth - length, is_last),
# For only one word in a line.
line = "".join(s)
if len(line) < maxWidth:
line += ' ' * (maxWidth - len(line))
return line

res = []
begin, length = 0, 0
for i in range(len(words)):
if length + len(words[i]) + (i - begin) > maxWidth:
res += connect(words, maxWidth, begin, i, length, False),
begin, length = i, 0
length += len(words[i])

# Last line.
res += connect(words, maxWidth, begin, len(words), length, True),
return res

if __name__ == "__main__":
assert Solution().fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16) \
== ['This    is    an', 'example  of text', 'justification.  ']```

0 条评论

• jasmine.FunctionMatchers.toHaveBeenCalledWith的单步调试

checkoutConfigService会调用getPreferredDeliveryMode, 输入的参数值为deliveryModes：

• 算法笔记（九）：希尔排序和桶排序

先将整个待排记录序列分割成若干个子序列，然后分别进行直接插入排序，待整个序列中的数据基本有序时，再对全体记录进行一次直接插入排序。具体做法是：

• 最近写了一个博客程序： QuickBlog PHP 开源的一文多发系统

在开始之前也用到了一些其他类似的系统，区别大概就是非开源的商业化产品不安全，无法进行自我数据存储管理。开源的产品部署起来总有一些问题或者有很多自己想实现的点没有...

• 【Storm篇】--Storm中的同步服务DRPC

Drpc（分布式远程过程调用）是一种同步服务实现的机制，在Storm中客户端提交数据请求之后，立刻取得计算结果并返回给客户端。同时充分利用Storm的计算能力实...

• 边做算法边学go语言之LeetCode1160：拼写单词

题目位置：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-character...

• g++ 编译 c++ 程序时需要包括 include .h 文件，还是需要 .cpp 文件

g++ 编译 c++ 程序时需要包括 include .h 文件，还是需要 .cpp 文件 最近用Eclipse 下的cdt...

• 持久化储存（一）

https://yeasy.gitbooks.io/docker_practice/install/mac.html