菜鸟追leetcode之一[text justification]# JobHunting - 待字闺中
s*e
1 楼
为了积攒人品RP，为了H1B顺利，为了有更好的工作，为了有一个更好的将来，开始追
leetcode，并写下自己的做题感受和大家分享，更是作为自己的督促。做题目的原则如
下：
1) Optimized Algorithms to pass the "large" test.
2) Proper abstraction
3) Write the code whose correctness is *easy* to reason about.
4) Favor readability over efficiency without compromising item 1).
5) Rearrangement and tweaking
我试图对自己进行训练的目标就是写完代码，能够确认自己写对了。目前为止，我有一
些小小的心得，会贯穿在下面和以后的文章中。第一，循环不变式；第二，优化控制流
；第三，适度抽象，语义精确的子函数。
抛砖引玉，献上第一弹：Text Justification. 为了更好的可读性，想用一种类C的伪
代码并尽量省略一些类型声明。很多叙述可能比较罗嗦，见谅。
首先要考虑的是怎样断行。因为长度L是给定的，假如有W0...WN-1个单词，L(Wi)为单
词长度，空格长度为1，当(L(W0) + ... + L(Wi)) + i > L的时候，说明第 i-1个单
词之后就是断行的位置。因此只要依次扫描每一个单词，就可以找到每一个断行点。
断行的问题解决了，下一步就是对齐问题了。从题目看，有左对齐和左右对齐两种方式
。何时左对齐，何时左右对齐呢？如下：
i) 这一行只有一个单词的时候要左对齐
ii) 最后一行也要左对齐
iii) 除去左对齐的情况，其他所有的时候都左右对齐就好。
因此可以写出如下的伪代码：
[tj-v1]
j = 0
for i from [0,N)
if i == N - 1 // 最后一行
left_justify(W[j..N-1])
elseif line-break-right-after-ith?
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
else
; // do noting...
do nothing这里是为了提醒一下，如果写if-elseif-elseif-...-else 结构的话，一定
不要忘了加上最后的else，上面的代码else分支用continue也是可以的。这样的互斥结
构保证只会掉入其中一个分支。当然，更可以只用if-else写成这样:
[tj-v2]
j = 0
for i from [0,N)
if i == N - 1 // 最后一行
left_justify(W[j..N-1])
else
if line-break-right-after-ith?
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
[lbrai?-v1]
bool line-break-right-after-ith?(W, i, j, L)
for m from [j, i]
acc = acc + (W[m].size + 1)
if acc + W[i+1] > L
return true
else
return false
上面的代码会引出一个问题，W[i+1]会被访问到，而当i == N - 1的时候，会出现访问
越界。但是观察tj-v2的代码的if-else-clause保证了i != N - 1。尽管不会出现错误
，但是line-break-right-after-ith?的语义是不精确的，因为没有定义最后一个单词W
[N-1]后面是否有line break，而是用上层的caller来保证不进入没有定义的地区，这
不符合"适度抽象，语义精确的子函数”原则。line-break-right-after-ith?的精确语
义应该是“是否会在第i个词之后断行？”，因此可以修改为:
[lbrai-v2]
bool line-break-right-after-ith?(W, i, j, L)
if j == N - 1
return true;
for m from [j, i]
acc = acc + (W[m].size + 1)
if acc + W[i+1] > L
return true
else
return false
进行如下修改之后，tj-v2的控制流也可以得到简化，变成:
[tj-v3]
j = 0
for i from [0,N)
if line-break-right-after-ith?
if i == N - 1 or i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
上面的代码看上去就非常清楚了，而且可以非常容易的推测算法的正确性。到这里可能
有同学发现lbrai-v2有重复的计算。每次调用都要进行从j到i的循环累加。可以有更有
效的代码:
[tj-v3]
j = 0
while i = find_next_line_break_point(j, W) && i < N - 1
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + i
left_justify(W[j..N-1]) // 最后一行要left justify
这里find_next_line_break_point的语义为“返回W里面从j开始的下一个断行点”。
剩下的事情就是具体写出left_justify和left_right_justify这两个函数了。left_
justify简单一些，就是把单词和单词之间用一个空格连起来，左对齐。所以有：
[lj-v1]
string left_justify(l, u, W)
string s;
for i from [l,u)
s[i] << W[i] + ' '
s << W[u]
padding spaces if s.length() < L
return s
left_right_justify稍微麻烦一些。因为是左右对齐，假设单词数是 M，所以空隙的数
量必然是 M - 1。在L长度的一行之中，除了单词的净长度 R，剩下的就是空格数 L-R
。我们需要把这些空格尽可能平均的放在单词中间。如果每个空隙用掉(L - R) / (M -
1)，那么还会多出(L - R) % (M - 1)个空格，如何分配呢？题目说"the empty slots
on the left will be assigned more spaces than the slots on the right"，所以
我们从左到右，每个空隙多分配一个，直到用完为止。所以我们可以写出代码如下:
[lrj-v1]
string left_right_justify(l, u, W)
string s
raw = 0;
for i from [l,u]
raw = raw + W[i].length
avg = (L - raw) / (u - l)
extra = (L - raw) % (u - 1)
for i from [l,u)
s << W[i] + string(avg, ' ')
if extra > 0
s << ' '
extra = extra - 1
s << W[u]
return s
到这里题目就算基本做完了。细心的同学可能发现如下的一些问题。首先，题目给的输
入格式不好，需要处理一下输入找出每个单词再放在数组里。第二，前面tj-v123里面
并没有把处理过的文本存起来，而且函数的参数设定也和后面不同，前面的写法主要是
为了突出算法的可读性，现在将其补全。以版本3为例:
string[] text_justification(string[] words, int L)
result = [] // the justified text to return
W = to_words(words)
j = 0
while i = find_next_line_break_point(j, W, L) && i < N - 1
if i == j
result << left_justify(j, i, W)
else
result << left_right_justify(j, i, W)
j = i + i
result << left_justify(W[j..N-1]) // 最后一行要left justify
写到这里突然发现我们还需要to_words和find_next_line_break_point这两个函数。先
给出find_next_line_break_point:
int find_next_line_break_point(start, W, L)
N = W.length
acc = 0
for i from [start, N)
acc = acc + (W[i] + 1)
if acc - 1 > L
return i - 1
return N - 1
这个题目就先写到这里。回头看写的很罗嗦，但是我尽量突出我试图表达的和总结的地
方。版上有很多做题很多或是思维超群的大牛，希望别拍的太狠。主要是写给我自己和
那些刚刚开始追leetcode的同学们。如果大家认为我写的有价值，我会接着写下去。如
果不好，我也会写下去。我稍后会把完整的C++代码贴上作为参考。
leetcode，并写下自己的做题感受和大家分享，更是作为自己的督促。做题目的原则如
下：
1) Optimized Algorithms to pass the "large" test.
2) Proper abstraction
3) Write the code whose correctness is *easy* to reason about.
4) Favor readability over efficiency without compromising item 1).
5) Rearrangement and tweaking
我试图对自己进行训练的目标就是写完代码，能够确认自己写对了。目前为止，我有一
些小小的心得，会贯穿在下面和以后的文章中。第一，循环不变式；第二，优化控制流
；第三，适度抽象，语义精确的子函数。
抛砖引玉，献上第一弹：Text Justification. 为了更好的可读性，想用一种类C的伪
代码并尽量省略一些类型声明。很多叙述可能比较罗嗦，见谅。
首先要考虑的是怎样断行。因为长度L是给定的，假如有W0...WN-1个单词，L(Wi)为单
词长度，空格长度为1，当(L(W0) + ... + L(Wi)) + i > L的时候，说明第 i-1个单
词之后就是断行的位置。因此只要依次扫描每一个单词，就可以找到每一个断行点。
断行的问题解决了，下一步就是对齐问题了。从题目看，有左对齐和左右对齐两种方式
。何时左对齐，何时左右对齐呢？如下：
i) 这一行只有一个单词的时候要左对齐
ii) 最后一行也要左对齐
iii) 除去左对齐的情况，其他所有的时候都左右对齐就好。
因此可以写出如下的伪代码：
[tj-v1]
j = 0
for i from [0,N)
if i == N - 1 // 最后一行
left_justify(W[j..N-1])
elseif line-break-right-after-ith?
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
else
; // do noting...
do nothing这里是为了提醒一下，如果写if-elseif-elseif-...-else 结构的话，一定
不要忘了加上最后的else，上面的代码else分支用continue也是可以的。这样的互斥结
构保证只会掉入其中一个分支。当然，更可以只用if-else写成这样:
[tj-v2]
j = 0
for i from [0,N)
if i == N - 1 // 最后一行
left_justify(W[j..N-1])
else
if line-break-right-after-ith?
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
[lbrai?-v1]
bool line-break-right-after-ith?(W, i, j, L)
for m from [j, i]
acc = acc + (W[m].size + 1)
if acc + W[i+1] > L
return true
else
return false
上面的代码会引出一个问题，W[i+1]会被访问到，而当i == N - 1的时候，会出现访问
越界。但是观察tj-v2的代码的if-else-clause保证了i != N - 1。尽管不会出现错误
，但是line-break-right-after-ith?的语义是不精确的，因为没有定义最后一个单词W
[N-1]后面是否有line break，而是用上层的caller来保证不进入没有定义的地区，这
不符合"适度抽象，语义精确的子函数”原则。line-break-right-after-ith?的精确语
义应该是“是否会在第i个词之后断行？”，因此可以修改为:
[lbrai-v2]
bool line-break-right-after-ith?(W, i, j, L)
if j == N - 1
return true;
for m from [j, i]
acc = acc + (W[m].size + 1)
if acc + W[i+1] > L
return true
else
return false
进行如下修改之后，tj-v2的控制流也可以得到简化，变成:
[tj-v3]
j = 0
for i from [0,N)
if line-break-right-after-ith?
if i == N - 1 or i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + 1;
上面的代码看上去就非常清楚了，而且可以非常容易的推测算法的正确性。到这里可能
有同学发现lbrai-v2有重复的计算。每次调用都要进行从j到i的循环累加。可以有更有
效的代码:
[tj-v3]
j = 0
while i = find_next_line_break_point(j, W) && i < N - 1
if i == j
left_justify(W[i])
else
left_right_justify(W[j..i])
j = i + i
left_justify(W[j..N-1]) // 最后一行要left justify
这里find_next_line_break_point的语义为“返回W里面从j开始的下一个断行点”。
剩下的事情就是具体写出left_justify和left_right_justify这两个函数了。left_
justify简单一些，就是把单词和单词之间用一个空格连起来，左对齐。所以有：
[lj-v1]
string left_justify(l, u, W)
string s;
for i from [l,u)
s[i] << W[i] + ' '
s << W[u]
padding spaces if s.length() < L
return s
left_right_justify稍微麻烦一些。因为是左右对齐，假设单词数是 M，所以空隙的数
量必然是 M - 1。在L长度的一行之中，除了单词的净长度 R，剩下的就是空格数 L-R
。我们需要把这些空格尽可能平均的放在单词中间。如果每个空隙用掉(L - R) / (M -
1)，那么还会多出(L - R) % (M - 1)个空格，如何分配呢？题目说"the empty slots
on the left will be assigned more spaces than the slots on the right"，所以
我们从左到右，每个空隙多分配一个，直到用完为止。所以我们可以写出代码如下:
[lrj-v1]
string left_right_justify(l, u, W)
string s
raw = 0;
for i from [l,u]
raw = raw + W[i].length
avg = (L - raw) / (u - l)
extra = (L - raw) % (u - 1)
for i from [l,u)
s << W[i] + string(avg, ' ')
if extra > 0
s << ' '
extra = extra - 1
s << W[u]
return s
到这里题目就算基本做完了。细心的同学可能发现如下的一些问题。首先，题目给的输
入格式不好，需要处理一下输入找出每个单词再放在数组里。第二，前面tj-v123里面
并没有把处理过的文本存起来，而且函数的参数设定也和后面不同，前面的写法主要是
为了突出算法的可读性，现在将其补全。以版本3为例:
string[] text_justification(string[] words, int L)
result = [] // the justified text to return
W = to_words(words)
j = 0
while i = find_next_line_break_point(j, W, L) && i < N - 1
if i == j
result << left_justify(j, i, W)
else
result << left_right_justify(j, i, W)
j = i + i
result << left_justify(W[j..N-1]) // 最后一行要left justify
写到这里突然发现我们还需要to_words和find_next_line_break_point这两个函数。先
给出find_next_line_break_point:
int find_next_line_break_point(start, W, L)
N = W.length
acc = 0
for i from [start, N)
acc = acc + (W[i] + 1)
if acc - 1 > L
return i - 1
return N - 1
这个题目就先写到这里。回头看写的很罗嗦，但是我尽量突出我试图表达的和总结的地
方。版上有很多做题很多或是思维超群的大牛，希望别拍的太狠。主要是写给我自己和
那些刚刚开始追leetcode的同学们。如果大家认为我写的有价值，我会接着写下去。如
果不好，我也会写下去。我稍后会把完整的C++代码贴上作为参考。
