TangRui's Blog
0%

白猫灰猫黑猫算法

发表于 更新于 分类于

背景

  • 偶尔发现一篇文章, 提到了白猫灰猫黑猫的问题

问题

  • 问题1: 有一个数组，数组中存储的是 Cat 对象，每个 Cat 对象有多个成员变量，其中一个代表颜色 color，有两个值白色和黑色，要求编写一个函数将数组中所有的白猫都放到黑猫前面
  • 问题2: 如果猫的颜色有三种，白色、黑色、灰色，编写一个函数将数组中白猫放到最前面，灰猫放到中间，黑猫放到最后面，比如：原来数组为 黑白灰白白黑灰灰，经过排序之后白白白灰灰黑黑
  • 问题3: 不仅白灰黑之间按顺序排列，而且白猫，灰猫，黑猫各自内部原来的先后顺序也不能变

思考

  • 思考本质其实某些算法的变种
  • 数组的原地排序，可以想到双指针算法 coding先写一个

  • 问题1 代码 双指针算法 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    In [29]: class Cat:
        ...:     def __init__(self, color):
        ...:         self.color = color
        ...:     def __repr__(self):
        ...:         return 'id: {0}, color: {1}'.format(id(self), self.color)
        ...:

    In [30]: cats_list = [Cat('white'), Cat('black'), Cat('white'), Cat('black')]

    In [31]: cats_list
    Out[31]:
    [id: 4555864208, color: white,
     id: 4555865488, color: black,
     id: 4555863696, color: white,
     id: 4555863056, color: black]

    In [32]: def cat_sort(cats_list):
        ...:     i = 0
        ...:     for j, cat in enumerate(cats_list):
        ...:         if cat.color == 'white':
        ...:              cats_list[i], cats_list[j] = cats_list[j], cats_list[i]
        ...:              i += 1
        ...:
        ...:

    In [33]: cat_sort(cats_list)

    In [34]: cats_list
    Out[34]:
    [id: 4555864208, color: white,
     id: 4555863696, color: white,
     id: 4555865488, color: black,
     id: 4555863056, color: black]

  • 问题2 还是可以用双指针/多指针 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    In [40]: cats_list = [Cat('white'), Cat('black'), Cat('grey'), Cat('white'), Cat('grey'), Cat('black'), Cat('white')]

    In [41]: cats_list
    Out[41]:
    [id: 4560231120, color: white,
     id: 4560232208, color: black,
     id: 4560230416, color: grey,
     id: 4560232016, color: white,
     id: 4560232144, color: grey,
     id: 4560231376, color: black,
     id: 4560231952, color: white]

    In [42]: def cat_sort(cats_list):
        ...:     i = 0
        ...:     # 排序白色猫
        ...:     for j, cat in enumerate(cats_list):
        ...:         if cat.color == 'white':
        ...:              cats_list[i], cats_list[j] = cats_list[j], cats_list[i]
        ...:              i += 1
        ...:     #排序灰色猫
        ...:     k = i
        ...:     for index in range(i, len(cats_list)):
        ...:         if cats_list[index].color == 'grey':
        ...:             cats_list[k], cats_list[index] = cats_list[index], cats_list[k]
        ...:             k += 1
        ...:

    In [43]: cat_sort(cats_list)

    In [44]: cats_list
    Out[44]:
    [id: 4560231120, color: white,
     id: 4560232016, color: white,
     id: 4560231952, color: white,
     id: 4560232144, color: grey,
     id: 4560230416, color: grey,
     id: 4560231376, color: black,
     id: 4560232208, color: black]

  • 问题3，思考了下，双指针的排序，但是在顺序上是有变化的

  • 这里借助网络查询，google到 双指针/多指针问题 查询得到文章地址
  • 发现是荷兰国旗问题 LeetCode第75题
  • 参考LeetCode第75题，完善问题2，三指针，实现一次循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
In [45]: def cat_sort(cats_list):
    ...:     p0 = curr = 0
    ...:     p2 = len(cats_list) - 1
    ...:     while curr <= p2:
    ...:         if cats_list[curr].color == 'white':
    ...:             cats_list[curr], cats_list[p0] = cats_list[p0], cats_list[curr]
    ...:             p0 += 1
    ...:             curr += 1
    ...:         elif cats_list[curr].color == 'black':
    ...:             cats_list[curr], cats_list[p2] = cats_list[p2], cats_list[curr]
    ...:             p2 -= 1 # 交换位置后需判断curr，所以curr不加1
    ...:         else:
    ...:             curr += 1  
    ...:
  • 目前问题3 还没有找到解题方法

反思

  • 问题的本质是数组的原地排序，双指针/多指针问题
  • 有些时候，我们直接去寻找问题，可能并不会得到结果。这时候，我们不妨想想，这个问题的本质是用了哪类型的算法，是不是它的变种
  • 这样就会更好的去找到问题和解决问题