时间戳

首页 > 解决方案 > 查找最小幸存者数量的函数

algorithm - 查找最小幸存者数量的函数

问题描述

给出了不同类型的细胞，它们可以吞噬它们的直接邻居：

计算最小的幸存者人数。


## Example:

    C=[X,Y,Z,X,Z,Z,Y] 

Answer is: 3.
 
* C0 swallows C1, [X,Z,X,Z,Z,Y]
* C5 swallows C4, then C3 [X,Z,X,Y]
* C2 swallows C3 [X,Z,X]

如何实现这样的功能？

标签： algorithm

解决方案

我们可以进行以下观察：

  • 如果列表没有 Y，那么什么都不能吞下
  • 如果列表只有 Y，那么什么都不能吞
  • 在所有其他情况下，都有可能吞下某些东西，因为这意味着有一个 Y 有一个不是 Y 的邻居。如果那个邻居是一个 X，那么这个 Y 可以被那个邻居吞下，或者如果那个邻居是Z，那么这个 Y 可以吞掉那个邻居。
  • 一个 X 不能被吞下，所以所有的 X 都留下了。

因此，我们应该优先考虑 Y 吞下 Z 的动作。这不会消除 X 吞下 Y 的任何可能性，......所以我们可以推迟这些动作，而不会冒险采取不太理想的路径。

当无法再进行此类移动时，执行唯一剩下的移动类型，即 X 吞下 Y。

如果这一举动也不再可能，我们已经达到了最低限度。

为了确保算法有效，可以将输入存储在链表中。第一步（Y 吞下 Z）可以通过链表一次扫描执行。如果当前节点是 Y 而前一个节点是 Z，则从列表中删除 Z，并保持与当前节点相同的节点用于下一次迭代。如果前一个节点不是 Z，但下一个节点是，则删除下一个节点并保持与当前节点相同的节点用于下一次迭代。如果两者都不成立，则将下一个节点设为当前节点并重复。

这具有线性时间复杂度。

下一阶段（X 吞噬 Y）遵循相同的原则。

执行

我将在这里给出一个 Python 实现。首先遵循使用哨兵节点的通用双向链表的代码：

class Node:
    def __init__(self, val, prev=None):
        self.val = val
        self.prev = prev or self
        self.next = prev.next if prev else self
        self.next.prev = self.prev.next = self

    def remove(self):
        self.prev.next = self.next
        self.next.prev = self.prev

class LinkedList(Node):
    def __init__(self, lst=None):
        super().__init__(None)  # A sentinel node
        if lst:
            node = self
            for val in lst:
                node = Node(val, node)

    def values(self):
        for node in self.nodes():
            yield node.val

    def nodes(self):
        node = self.next
        while node != self:
            yield node
            node = node.next

实际的算法将如下所示：

def swallow(c):
    ll = LinkedList(c)  # create doubly linked list for input

    for eater, food in ("YZ", "XY"):  # two phases
        for node in ll.nodes():
            if node.val == eater:
                while node.prev.val == food:
                    node.prev.remove()
                while node.next.val == food:
                    node.next.remove()

    return list(ll.values())  # return result as a standard list

你可以这样称呼它：

c = ["X","Y","Z","X","Z","Z","Y"]
print(swallow(c))  # ['X', 'X']

替代实施

除了链表，您还可以使用字符串和正则表达式来删除：

  • 出现在 Z 之前的任何 Y 序列
  • 紧跟在 Z 之后的任何 Y 序列
  • 任何出现在 Y 之前的 X 序列
  • 紧跟在 Y 之后的任何 X 序列

... 以该顺序。

import re

def swallow(c):
    s = "".join(c)  # convert to string
    s = re.sub(r"Z+Y", "Y", s)    
    s = re.sub(r"YZ+", "Y", s)    
    s = re.sub(r"X+Y", "X", s)    
    s = re.sub(r"YX+", "X", s)    
    return list(s)  # convert back to list

推荐阅读