Redian新闻
>
菜鸟追leetcode之一[text justification]
avatar
菜鸟追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++代码贴上作为参考。
avatar
z*u
2
没有更新了
avatar
r*e
3
接着来啊,看看别人的思路总是有用的,+U!

【在 s*********e 的大作中提到】
: 为了积攒人品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
: 我试图对自己进行训练的目标就是写完代码,能够确认自己写对了。目前为止,我有一
: 些小小的心得,会贯穿在下面和以后的文章中。第一,循环不变式;第二,优化控制流

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。