锁箱问题：列表内的列表，每个列表都包含解锁其他箱子的钥匙

Question

问题来了： 你面前有n个上锁的盒子。每个盒子按从 0 到 n-1 的顺序编号，每个盒子可能包含其他盒子的钥匙。

boxes 是列表的列表

与盒子编号相同的钥匙可以打开该盒子

您可以假设所有键都是正整数

第一个盒子[0]已解锁

如果所有盒子都可以打开则返回 True，否则返回 False

这是我的代码，但我发现在某些情况下它会获取列表的所有值并存储它们，甚至是无法解锁的值：

def canUnlockAll(boxes):
    newlist = []
    k = len(boxes)
    for i in boxes:
        if len(i) == 0 and i is not boxes[k-1]:
            return False
        for j in i:
            newlist.append(j)
    print(newlist)
    for index, keys in enumerate(boxes):
        if index in newlist or index < k-1:
            return True
        else:
            return False

这是我使用的测试用例：

#!/usr/bin/python3

canUnlockAll = __import__('0-lockboxes').canUnlockAll

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6], [7]]
print(canUnlockAll(boxes), "\t: False")
print('-----------------------------')

我的问题是如何解决索引 7 中的盒子被解锁但不应该解锁的问题！

Answer 1

尝试这个代码：

def join(T,R):
  res =[]
  for e in R:
    res += T[e]
  return res

def canUnlockAll(boxes):
  index = 0
  total = list(set(boxes[0])| {0})
  added = True
  while added:
    added = False
    for j in join(boxes,total[index:]):
      if j not in total:
        total.append(j)
        index +=1
        added= True
  print(total)
  
  return len(total)==len(boxes)

测试：

boxes = [[1], [2], [3], [4], [5], [6], [7], [0]]
print(canUnlockAll(boxes), "\t: True\n")

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6], [7]]
print(canUnlockAll(boxes), "\t: False")

结果：

[0, 1, 2, 3, 4, 5, 6, 7]
True    : True

[0, 1, 4, 6, 2, 3, 5]
False   : False

Answer 2

我面临着类似的任务，这是我使用的代码。 我已经用你的测试用例对其进行了测试，并且有效。也许你可以尝试一下。

def canUnlockAll(boxes):
    unlocked = [0]
    for box_id, box in enumerate(boxes):
        if not box:
            continue
        for key in box:
            if key < len(boxes) and key not in unlocked and key != box_id:
                unlocked.append(key)
    if len(unlocked) == len(boxes):
        return True
    return False

Answer 3

[✨已解决]这是我能找到的最快|最简单的方法：

def canUnlockAll(boxes):
    """ Method that determines if all boxes can be opened """

    for key in range(1, len(boxes)):
        flag = False
        for box in range(len(boxes)):
            if key in boxes[box] and box != key:
                flag = True
                break
        if not flag:
            return False

    return True

✅ 成功通过所有测试用例

boxes = [[]]
print(canUnlockAll(boxes))

boxes = [[1], [2], [3], [4], []]
print(canUnlockAll(boxes))

boxes = [[1, 4, 6], [2], [0, 4, 1], [5, 6, 2], [3], [4, 1], [6]]
print(canUnlockAll(boxes))

boxes = [[1, 4], [2], [0, 4, 1], [3], [], [4, 1], [5, 6]]
print(canUnlockAll(boxes))

boxes = [[], [2], [1], [4], []]
print(canUnlockAll(boxes))