CodeWars 中存在一个涉及搜索算法的问题，由于我还是一个初学者，所以在尝试优化我的代码时遇到了一些困难，它工作正常，但我希望它更快。 如果您想检查一下，这就是问题所在：灯开关
# n is the number of lights
# corresponding_lights_list is the array representing relationships between lights and switches
# returns a boolean, represents whether it is possible to turn all the lights on.
def light_switch(n, corresponding_lights_list):
lights = [0]*n
oldlights = []
queue = []
while True:
for s in corresponding_lights_list :
newlights = [1 - lights[l] if l in s else lights[l] for l in range(n)]
if newlights == [1]*n :
return True
if not (newlights in oldlights or newlights in queue) :
queue.append(newlights)
oldlights.append(lights)
lights = queue.pop(0)
if len(queue) == 0 :
return False
from collections import deque
def light_switch(n, corresponding_lights_list):
lights1 = [0]*n
lights2 = [1]*n
oldlights1 = []
oldlights2 = []
queue1 = deque()
queue2 = deque()
while True:
oldlights1.append(lights1)
oldlights2.append(lights2)
for s in corresponding_lights_list :
newlights1 = [1 - lights1[l] if l in s else lights1[l] for l in range(n)]
newlights2 = [1 - lights2[l] if l in s else lights2[l] for l in range(n)]
if not (newlights1 in oldlights1 or newlights1 in queue1) :
queue1.append(newlights1)
if not (newlights2 in oldlights2 or newlights2 in queue2) :
queue2.append(newlights2)
if newlights2 in queue1 :#or newlights2 in oldlights1 or newlights1 in queue2 or newlights1 in oldlights2 :
return True
lights1 = queue1.popleft()
lights2 = queue2.popleft()
if len(queue1) == 0 :
return False
我希望你们能帮助我改进我的代码，甚至建议一种新方法，但请尽可能保持通用，因为我仍然想自己解决这个问题。
您可以执行高斯消除，其中每个开关都是未知的（变量），并且对于每个灯，您可以制定一个约束，该约束本质上表明切换该灯的activated开关的总和必须是奇数（或者以其他方式将：它们的异或应该是1)。
例如，对于此输入：
[
[0, 1, 2], # switch 0 controls light 0, 1, 2
[1, 2], # switch 1 controls light 1, 2
[1, 2, 3, 4], # switch 2 controls light 1, 2, 3, 4
[1, 4] # switch 3 controls light 1, 4
]
...我们可以将𝑠𝑖定义为索引为𝑖的开关的状态，然后写出这些XOR方程（每个灯一个），必须满足：
这可以表示为扩展矩阵：
1 0 0 0 | 1
1 1 1 1 | 1
1 1 1 0 | 1
0 0 1 0 | 1
0 0 1 1 | 1
由于这些是布尔值，您也可以将此矩阵表示为集合列表：
{0, 4}
{0, 1, 2, 3, 4}
{0, 1, 2, 4}
{2, 4}
{2, 3, 4}
每组中的值代表开关，除了值 4，它是一个单独的值，代表扩展矩阵中的最后一列。
然后通过行（组）彼此进行异或来执行高斯消除，最终得到一个矩阵，其中开关最多属于一行（组）。那么不应该有其他非空行（集合）（因为它们可能仍然包含 4）：这表示不一致，在这种情况下应该返回 False。
如果你无法让它工作，这里有一个剧透：
def light_switch(num_lights, corresponding_lights_list): num_switches = len(corresponding_lights_list) # Build extended matrix for Gaussian elimination. As the variables (switch states) # are booleans, a matrix row can be represented with a set (of switches) # The num_switches value represents the desired outcome by xoring the states # of the relevant switches (i.e. the light should be ON) gauss = [{num_switches} for _ in range(num_lights)] # Populate the matrix: for switch, lights in enumerate(corresponding_lights_list): for light in lights: gauss[light].add(switch) # Perform Gaussian elimination light = 0 for switch in range(num_switches): # iterate columns (switches) # Find a constraint that involves this switch i = next((i for i in range(light, num_lights) if switch in gauss[i]), -1) if i == -1: # No constraint found for this switch: it is irrelevant continue # Swap constraint gauss[light], gauss[i] = gauss[i], gauss[light] selected = gauss[light] # Make this the only constraint that involves the current switch for other_light in gauss: if switch in other_light and other_light is not selected: # Redefine constraint as a XOR of itself with the selected constraint other_light.symmetric_difference_update(selected) light += 1 # Confirm there are no constraints without switches that must produce light return not any(rule for rule in gauss[light:])
最后，有一些Python模块可以为你执行高斯消除，如果用C实现，它们肯定会更快地完成这项工作。