我正在尝试解决我在网上发现的一些编码难题。但是我被下面的问题拦住了。我尝试使用递归来解决它,但是我觉得我缺少递归中一个非常重要的概念。我的代码适用于以下所有示例,但最后一个示例将崩溃。
有人可以指出我在此递归代码中犯的错误吗?或者也许可以指导我解决问题?
我知道为什么我的代码会中断,但是我不知道如何解决Python中的“按对象引用传递”问题,我认为这会给我带来更大的问题。
编码问题是:
在一个神秘的小岛上,有被称为Quxes的生物以三种颜色出现:红色,绿色和蓝色。 Qux的一项功能是,如果其中两个彼此并排站立,它们可以转变为具有第三种颜色的单个生物。
给定N个Quxes排成一行,请确定在进行此类转换的任何可能序列后剩余的数量最少。
例如,给定输入['R', 'G', 'B', 'G', 'B'],可以通过以下步骤最终得到一个Qux:
Arrangement | Change
----------------------------------------
['R', 'G', 'B', 'G', 'B'] | (R, G) -> B
['B', 'B', 'G', 'B'] | (B, G) -> R
['B', 'R', 'B'] | (R, B) -> G
['B', 'G'] | (B, G) -> R
['R'] |
________________________________________
我的代码是:
class fusionCreatures(object):
"""Regular Numbers Gen.
"""
def __init__(self , value=[]):
self.value = value
self.ans = len(self.value)
def fusion(self, fus_arr, i):
color = ['R','G','B']
color.remove(fus_arr[i])
color.remove(fus_arr[i+1])
fus_arr.pop(i)
fus_arr.pop(i)
fus_arr.insert(i, color[0])
return fus_arr
def fusionCreatures1(self, arr=None):
# this method is to find the smallest number of creature in a row after fusion
if arr == None:
arr = self.value
for i in range (0,len(arr)-1):
#print(arr)
if len(arr) == 2 and i >= 1 or len(arr)<2:
break
if arr[i] != arr[i+ 1]:
arr1 = self.fusion(arr, i)
testlen = self.fusionCreatures1(arr)
if len(arr) < self.ans:
self.ans = len(arr)
return self.ans
测试数组(除最后一个数组外,其他所有数组均有效):
t1 = fusionCreatures(['R','G','B','G','B'])
t2 = fusionCreatures(['R','G','B','R','G','B'])
t3 = fusionCreatures(['R','R','G','B','G','B'])
t4 = fusionCreatures(['G','R','B','R','G'])
t5 = fusionCreatures(['G','R','B','R','G','R','G'])
t6 = fusionCreatures(['R','R','R','R','R'])
t7 = fusionCreatures(['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B'])
print(t1.fusionCreatures1())
print(t2.fusionCreatures1())
print(t3.fusionCreatures1())
print(t4.fusionCreatures1())
print(t5.fusionCreatures1())
print(t6.fusionCreatures1())
print(t7.fusionCreatures1())
请您参考如下方法:
我将首先提到在O(n)中有一种演绎方法,该方法在blog post中有详细介绍。归结为检查列表中三种类型元素的计数的奇偶性,以确定发生一些固定结果中的哪一个。
您提到您更喜欢使用递归方法,即O(n!)。这是一个好的开始,因为它可以用作帮助获得O(n)解决方案的工具,并且是一种常见的递归模式。
因为我们不知道两个Qux之间的给定融合是否最终会导致最佳的全局解决方案,所以我们不得不尝试各种可能性。我们通过遍历列表并寻找潜在的融合来做到这一点。找到一个后,在新列表中执行转换并在其上调用fuse_quxes。一路走来,我们一直在追踪达到的最小长度。
这是一种方法:
def fuse_quxes(quxes, choices="RGB"):
fusion = {x[:-1]: [x[-1]] for x in permutations(choices)}
def walk(quxes):
best = len(quxes)
for i in range(1, len(quxes)):
if quxes[i-1] != quxes[i]:
sub = quxes[:i-1] + fusion[quxes[i-1], quxes[i]] + quxes[i+1:]
best = min(walk(sub), best)
return best
return walk(quxes)
这几乎是您提供的代码所朝的方向,但是实现方式似乎不清楚。不幸的是,我看不到任何单一或快速修复。以下是一些一般性问题:
将
fusionCreatures1函数放到一个类中可以使它改变外部状态,即
self.value和
self.ans。特别是
self.value的名字不好用,很难追踪。似乎打算将其用作参考副本以将
arr重置为其默认值,但是
arr = self.value意味着当
fus_arr在
fusion()中发生突变时,
self.value也是如此。几乎所有内容都引用了一个基础列表。
将切片添加到这些副本至少可以使程序更易于推理,例如
arr = self.value[:]函数中的
fus_arr = fus_arr[:]和
fusion()。简而言之,尝试编写
pure functions。
self.ans也是不清楚和不必要的;最好将结果值保留在递归函数中的局部变量中。
似乎没有必要将无状态函数放入类中,除非它是纯静态方法并且该类充当名称空间。
造成认知超负荷的另一个原因是分支语句,例如
if和
break。我们想要最小化它们的频率和嵌套。这是伪代码中的
fusionCreatures1,带有突变和复杂交互的注释:
def fusionCreatures1():
if ...
read mutated global state
for i in len(arr):
if complex length and index checks:
break
if arr[i] != arr[i+ 1]:
impure_func_that_changes_arr_length(arr)
recurse()
if new best compared to global state:
mutate global state
您可能会同意,在头脑上逐步运行此功能非常困难。
在
fusionCreatures1()中,两个变量未使用:
arr1 = self.fusion(arr, i)
testlen = self.fusionCreatures1(arr)
赋值
arr1 = self.fusion(arr, i)(以及
return fus_arr)似乎表明缺乏对
self.fusion确实是一个变异其参数数组的
in-place函数的理解。因此,调用它的意思是
arr1 is arr,我们还有另一个别名变量可以推断。
除此之外,程序中均未使用
arr1或
testlen,因此其意图尚不清楚。
一个好的 linter会选取这些未使用的变量,并找出我提到的大多数其他复杂性问题。
在循环遍历列表时对其进行突变通常是灾难性的。
self.fusion(arr, i)会在循环内对
arr进行突变,这使得很难推断其长度,并且当
range(len(arr))不再与函数主体中的实际
len(arr)匹配时(或至少需要使用-身体前提)。如上所述,使用切片使
self.fusion(arr, i)纯净,可以解决此问题,但显示没有递归
base case,从而导致堆栈溢出错误。
除非上下文很明显,否则避免使用变量名称,例如
arr,
arr1,
value。同样,这些混淆了意图并使程序难以理解。
一些次要的风格建议:
每个 PEP-8使用
snake_case。类名应为
TitleCased,以区别于功能。无需从
object继承-这是隐式的。
在函数和运算符之间使用一致的间距:例如,
range (0,len(arr)-1):更清晰地表示为
range(len(arr) - 1):。在块周围使用垂直空格。
使用列表而不是键入
t1,
t2,...
t7。
函数名称应该是动词,而不是名词。诸如
fusionCreatures之类的带有
fusionCreatures1方法的类尚不清楚。像
QuxesSolver.minimize(creatures)这样的意图会更加明显。
至于我上面提供的解决方案,还有其他一些技巧值得考虑以加快速度。一个是 memoization,它可以帮助避免重复工作(任何给定列表始终会产生相同的最小长度,因此我们只是将此计算存储在dict中,如果再次看到它就将其吐出)。如果长度为1,那是我们在全局范围内可以做的最好的事情,因此我们可以跳过其余的搜索。
这是一个完整的介绍,包括转换为Python的线性解决方案(同样,请参阅博客文章以了解其工作原理):
from collections import defaultdict
from itertools import permutations
from random import choice, randint
def fuse_quxes_linear(quxes, choices="RGB"):
counts = defaultdict(int)
for e in quxes:
counts[e] += 1
if not quxes or any(x == len(quxes) for x in counts.values()):
return len(quxes)
elif len(set(counts[x] % 2 for x in choices)) == 1:
return 2
return 1
def fuse_quxes(quxes, choices="RGB"):
fusion = {x[:-1]: [x[-1]] for x in permutations(choices)}
def walk(quxes):
best = len(quxes)
for i in range(1, len(quxes)):
if quxes[i-1] != quxes[i]:
sub = quxes[:i-1] + fusion[quxes[i-1], quxes[i]] + quxes[i+1:]
best = min(walk(sub), best)
return best
return walk(quxes)
if __name__ == "__main__":
tests = [
['R','G','B','G','B'],
['R','G','B','R','G','B'],
['R','R','G','B','G','B'],
['G','R','B','R','G'],
['G','R','B','R','G','R','G'],
['R','R','R','R','R'],
['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B']
]
for test in tests:
print(test, "=>", fuse_quxes(test))
assert fuse_quxes_linear(test) == fuse_quxes(test)
for i in range(100):
test = [choice("RGB") for x in range(randint(0, 10))]
assert fuse_quxes_linear(test) == fuse_quxes(test)
输出:
['R', 'G', 'B', 'G', 'B'] => 1
['R', 'G', 'B', 'R', 'G', 'B'] => 2
['R', 'R', 'G', 'B', 'G', 'B'] => 2
['G', 'R', 'B', 'R', 'G'] => 1
['G', 'R', 'B', 'R', 'G', 'R', 'G'] => 2
['R', 'R', 'R', 'R', 'R'] => 5
['R', 'R', 'R', 'G', 'G', 'G', 'B', 'B', 'B'] => 2
