P109: Pack consecutive duplicates of list elements into sublists
打包连续重复的元素为子列表。 要养成良好的习惯,先写测试用例:
from python99.lists.p109 import pack
def test_pack():
assert pack([]) == []
assert pack([1]) == [[1]]
assert pack([1, 1, 2, 3, 3, 4]) == [[1, 1], [2], [3, 3], [4]]
然后就不知道怎么办了?记住!
没有什么问题是递归解决不了的!
先假定已经拥有了一个打包方法,其可以将列表中连续重复的元素打包成子列表。然后,将列表拆分为第一个元素和剩余列表。再然后,将剩余列表中连续重复的元素打包成子列表。最后,将拆分出来的第一个元素拼入打包后的剩余列表。如果第一个元素和打包后的剩余列表中第一个子列表中的元素相同,则将第一个元素打包进第一个子列表。否则,第一个元素以独立的子列表拼入剩余列表。打包方法会持续拆分剩余列表,直至其为仅包含一个元素的列表。
举个例子,给定列表[1, 1, 2, 3, 3, 4]
:
- 将列表
[1, 1, 2, 3, 3, 4]
拆分为头元素1
和剩余列表[1, 2, 3, 3, 4]
,打包剩余列表 - 将列表
[1, 2, 3, 3, 4]
拆分为头元素1
和剩余列表[2, 3, 3, 4]
,继续打包剩余列表 - 将列表
[2, 3, 3, 4]
拆分为头元素2
和剩余列表[3, 3, 4]
,继续打包剩余列表 - 将列表
[3, 3, 4]
拆分为头元素3
和剩余列表[3, 4]
,继续打包剩余列表 - 将列表
[3, 4]
拆分为头元素3
和剩余列表[4]
- 列表中仅有一个元素
4
,将其打成一个子列表[[4]]
- 比较这一层中拆分出来的头元素
3
和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[3], [4]]
- 比较这一层中拆分出来的头元素
3
和打包后剩余列表中第一个子列表的元素,发现它们相同,所以将头元素拼进第一个子列表中,得到[[3, 3], [4]]
- 比较这一层中拆分出来的头元素
2
和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[2], [3, 3], [4]]
- 比较这一层中拆分出来的头元素
1
和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[1], [2], [3, 3], [4]]
- 比较最后一层中拆分出来的头元素
1
和打包后剩余列表中第一个子列表的元素,发现它们相同,所以将头元素拼进第一个子列表中,得到最终结果[[1, 1], [2], [3, 3], [4]]
代码实现:
# Pack consecutive duplicates of list elements into sublists.
# If a list contains repreated elements they should be placed in separate sublists
def pack(l):
if l is None:
return []
if len(l) == 0:
return []
if len(l) == 1:
return [l]
first = l[0]
remain = l[1:len(l)]
remain_pack = pack(remain)
if len(remain_pack) == 0:
return [[first]]
elif first in remain_pack[0]:
remain_pack[0].append(first)
return remain_pack
else:
return [[first]]+remain_pack