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, 1, 2, 3, 3, 4]拆分为头元素1和剩余列表[1, 2, 3, 3, 4],打包剩余列表
  2. 将列表[1, 2, 3, 3, 4]拆分为头元素1和剩余列表[2, 3, 3, 4],继续打包剩余列表
  3. 将列表[2, 3, 3, 4]拆分为头元素2和剩余列表[3, 3, 4],继续打包剩余列表
  4. 将列表[3, 3, 4]拆分为头元素3和剩余列表[3, 4],继续打包剩余列表
  5. 将列表[3, 4]拆分为头元素3和剩余列表[4]
  6. 列表中仅有一个元素4,将其打成一个子列表[[4]]
  7. 比较这一层中拆分出来的头元素3和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[3], [4]]
  8. 比较这一层中拆分出来的头元素3和打包后剩余列表中第一个子列表的元素,发现它们相同,所以将头元素拼进第一个子列表中,得到[[3, 3], [4]]
  9. 比较这一层中拆分出来的头元素2和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[2], [3, 3], [4]]
  10. 比较这一层中拆分出来的头元素1和打包后剩余列表中第一个子列表的元素,发现它们不相同,所以将头元素做为一个独立的子列表拼接剩余列表,得到[[1], [2], [3, 3], [4]]
  11. 比较最后一层中拆分出来的头元素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

results matching ""

    No results matching ""