我如何将
给定一个未排序整数和一个目标整数的列表，找出列表中任何对的差值是否等于带有递归的目标整数。
>>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True
>>> aList = [-1, 5, 4]
>>> target = 3
return False
- 不允许使用 For 和 while 循环。
- 不允许进口。
- .sort() 是不允许的。
我试过这个，但没有用。
def calculate(aList, target):
if len(aList) == 0 and diff != 0:
return False
startIndex = 0
endIndex = len(aList) - 1
return resursive_sum(aList, target, startIndex, endIndex)
def resursive_sum(aList, targ, start, end):
print(f'Start: {start}')
print(f'End: {end}')
if start == end:
return False
elif aList[end] - aList[start] == targ:
return True
elif aList[end] - aList[start] < targ:
return resursive_sum(values, targ, start, end - 1)
return resursive_sum(aList, targ, start + 1, end)
我不确定如果我们无法使用循环对列表进行排序，如何解决这个问题。即使我们可以使用递归对列表进行排序，递归应该如何看起来，以便它可以扫描每个对的差异？
所以我实际上实现了它，但出于教育目的，我不会发布它，直到稍后(我会在几个小时内更新它)，因为我假设这是针对一个类或其他一些设置，你应该自己弄清楚。
假设您正在尝试命中差异目标t = 5并且正在评估任意元素8。只有两个值可以让8在集合中有一个补码：8 + 5 = 13和8 - 5 = 3。
如果3或13在以前的任何元素中，你就会知道该集合有一对补语。否则，您需要记录8被看到的事实。因此，如果以后发现3，8将被查询，因为将考虑3 + 5 = 8。
换句话说，我提出了一种方法，您可以在其中递归遍历列表，并且
- (基本大小写)位于列表末尾
- 具有当前元素
a以便已看到a + t或a - t - 记录已看到当前元素并转到下一个元素
理想情况下，这应该具有 O(n) 时间复杂度和 O(n) 空间复杂度(假设使用按引用传递或类似方法有效实现，以及摊销常量时间集查询)。它也可以使用基本数组实现，但我不会说这更好(在 python 中)。
我将在几个小时内发布我的解决方案。祝你好运！
>EDIT 1：希望您有足够的时间让它工作。我描述的方法可以按如下方式完成：def hasDiffRecur(L, t, i, C):
"""
Recursive version to see if list has difference
:param L: List to be considered
:param t: Target difference
:param i: Current index to consider
:param C: Cache set
"""
# We've reached the end. Give up
if i >= len(L):
return False
print(f" > L[{i}] = {L[i]:2}; is {L[i]-t:3} or {L[i]+t:2} in {C}")
# Has the complement been cached?
if L[i] - t in C:
print(f"! Difference between {L[i]} and {L[i]-t} is {t}")
return True
if L[i] + t in C:
print(f"! Difference between {L[i]} and {L[i]+t} is {t}")
return True
# Complement not seen yet. Cache element and go to next element
C.add(L[i])
return hasDiffRecur(L, t, i+1, C)
###################################################################
def hasDiff(L, t):
"""
Initialized call for hasDiffRecur. Also prints intro message.
See hasDiffRecur for param info
"""
print(f"nIs a difference of {t} present in {L}?")
return hasDiffRecur(L, t, 0, set())
###################################################################
hasDiff([5, 4, 8, -3, 6], 9)
hasDiff([-1, 5, 4], 3)
hasDiff([-1, 5, 4, -1, 7], 0) # If concerned about set non-duplicity
输出：
Is a difference of 9 present in [5, 4, 8, -3, 6]?
> L[0] = 5; is -4 or 14 in set()
> L[1] = 4; is -5 or 13 in {5}
> L[2] = 8; is -1 or 17 in {4, 5}
> L[3] = -3; is -12 or 6 in {8, 4, 5}
> L[4] = 6; is -3 or 15 in {8, -3, 4, 5}
! Difference between 6 and -3 is 9
Is a difference of 3 present in [-1, 5, 4]?
> L[0] = -1; is -4 or 2 in set()
> L[1] = 5; is 2 or 8 in {-1}
> L[2] = 4; is 1 or 7 in {5, -1}
Is a difference of 0 present in [-1, 5, 4, -1, 7]?
> L[0] = -1; is -1 or -1 in set()
> L[1] = 5; is 5 or 5 in {-1}
> L[2] = 4; is 4 or 4 in {5, -1}
> L[3] = -1; is -1 or -1 in {4, 5, -1}
! Difference between -1 and -1 is 0
这是一个非常聪明和有效的解决方案。我确实意识到也许是根本不允许任何遍历(即不存在对集合的查询)。如果是这种情况，可以使用常量大小列表来完成上述方法，该列表预先分配给等于列表值范围的大小。
如果预分配给列表范围大小的概念仍然太多迭代，我可以想到递归实现的详尽方法。可能有一种更有效的方法，但你可以把问题归结为一个类似双循环的问题(O(n^2)时间复杂度)。这是一个微不足道的算法，我认为你可以在没有文档的情况下理解它，所以我把它放在那里完成：
def hasDiffRecur(L, t, i = 0, j = 1):
if i >= len(L): return False
if j >= len(L): return hasDiffRecur(L, t, i+1, i+2)
if abs(L[i] - L[j]) == t: return True
return hasDiffRecur(L, t, i, j+1)
###################################################################
print(hasDiffRecur([5, 4, 8, -3, 6], 9)) # True
print(hasDiffRecur([-1, 5, 4], 3)) # False
print(hasDiffRecur([-1, 5, 4, -1, 7], 0)) # True
选择
我将从一个泛型函数开始，该函数接受列表、t和许多元素来选择，n-
def choose(t, n):
if n == 0:
return [[]]
elif not t:
return []
else:
return append
( map
( choose(rest(t), n - 1)
, lambda c: append([first(t)], c)
)
, choose(rest(t), n)
)
print(choose(["a", "b", "c", "d"], 2))
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]
助手
你的问题施加了很多限制，Python是一种多范式语言，所以我们将使用一些帮助程序来使事情可读
def first(t):
return t[0]
def rest(t):
return t[1:]
def append(t0, t1):
return t0 + t1
我不知道map算不算导入，但我们会定义我们自己的以防万一——
def map(t, f):
if not t:
return []
else:
return append
( [f(first(t))]
, map(rest(t), f)
)
解决
太好了，现在我们已经完成了choose的实现，让我们看看如何将其应用于我们的问题
print(choose([5, 4, 8, -3, 6], 2))
[[5, 4], [5, 8], [5, -3], [5, 6], [4, 8], [4, -3], [4, 6], [8, -3], [8, 6], [-3, 6]]
如您所见，我们已经找到了 2 个元素的所有组合。我们只需要loop这些，check是否可以减去一对来达到我们的目标，q-
def solve(t, q):
def check(p):
(x, y) = p
return x - y == q or y - x == q
def loop(c):
if not c:
return False
else:
return check(first(c)) or loop(rest(c))
return loop(choose(t, 2))
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
允许for
这是建立递归技能的好练习。不允许for是需要克服的最具挑战性的限制。如果我们可以使用它，它会是什么样子 -
def choose(t, n):
if n == 0:
yield []
elif not t:
return
else:
for c in choose(t[1:], n - 1):
yield [t[0]] + c
yield from choose(t[1:], n)
def solve(t, q):
for (x,y) in choose(t, 2):
if x - y == q or y - x == q:
return True
return False
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
此变体还有一个额外的优点，即一旦找到解决方案，它将停止计算组合。第一个变体必须首先计算所有组合，然后开始迭代它们。
允许其他内置
Python 内置函数包括map和any，并为我们提供了另一种绕过for限制的方法，但我不确定是否允许这些 -
def choose(t, n):
if n == 0:
yield []
elif not t:
return
else:
yield from map
( lambda c: [t[0]] + c
, choose(t[1:], n - 1)
)
yield from choose(t[1:], n)
def solve(t, q):
def check(p):
(x,y) = p
return x - y == q or y - x == q
return any(map(check, choose(t, 2)))
print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
True
False
问题：
- 给定一个整数
aList和整数target数组， - 检查
aList中每个元素之间的差异是否等于target - 使用递归
- 请勿使用
.sort() - 请勿使用
while和for - 不要使用
import
例：
>>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True
>>> aList = [-1, 5, 4]
>>> target = 3
return False
比较差异：
5 4 8 -3 6
-------------------------
5 | X
4 | 1 X
8 | 3 4 X
-3 | 6 7 11 X
6 | 1 2 2 9 X
where X means that there's no difference (same number)
since we find 9 there, so it should return True (target is 9)
传统 for 循环
要解决递归问题，首先尝试使用传统的for循环来解决它：
def compareAll(lst, tgt):
for x in lst: # let's call this x loop
for y in lst: # let's call this y loop
if abs(x-y) == tgt:
return True
return False
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
这将返回True然后False
递归
现在我们可以尝试使用递归循环。由于我们已经得到了for循环，我们可以像这样转换它：
def compareAll(lst, tgt, x=0, y=0):
if(len(lst)-1 == x and len(lst) == y):
return False
if(len(lst) == x or len(lst) == y):
return compareAll(lst, tgt, x+1, 0)
if(abs(lst[x] - lst[y])==tgt):
return True
return compareAll(lst, tgt, x, y+1)
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
我如何将for循环转换为这个：
- Python 的
for循环实际上是大多数其他语言foreach
循环 - 因此，Python 中的纯
for循环如下所示：
def compareAll(lst, tgt):
x = 0
while x < len(lst): # let's call this x loop
y = 0
while y < len(lst): # let's call this y loop
if abs(lst[x]-lst[y]) == tgt:
return True
y = y+1
x = x+1
return False
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
- 注意
x loop的停止条件：当所有数组元素都已循环时- 所以我们在这里添加停止条件：
if(len(lst)-1 == x and len(lst) == y): return False
- 所以我们在这里添加停止条件：
- 注意
y loop的停止条件：当所有数组元素都已循环时- 所以我们在这里添加停止条件：
if(len(lst) == x or len(lst) == y): return compareAll(lst, tgt, x+1, 0) - 这将停止当前
y loop并继续x loop
- 所以我们在这里添加停止条件：
- 然后，我们添加循环的实际内容：
if(abs(lst[x] - lst[y])==tgt): return True - 最后，我们必须继续循环：
return compareAll(lst, tgt, x, y+1)
将 for 循环转换为递归循环的关键只是确定循环何时结束，以及循环何时应继续。
这应该有效并且非常简洁：
def q(target, aList, memo=set()):
if len(aList) == 0:
return False
num = aList.pop()
memo.add(num)
if target + num in memo:
return True
return q(target, aList, memo)
q(target=9, aList=[5, 4, 8, -3, 6]) # True
q(target=3, aList=[-1,5,4]) # False
对我来说，关键的见解是，一个目标t和一个给定的数字n，d的差异是已知的。 字典/集合/哈希图可以快速检测成员资格，无论添加多少项。 所以。。。只需pop值列表并将它们放入哈希图中以供以后比较。
这个问题可以通过检查列表中每对可能的数字来解决问题。 如果你被允许使用Python的标准库，那么解决方案非常简单。
from itertools import product
def check(xs, target):
return any(map(lambda x: x[0]-x[1] == target, product(xs, xs)))
故障
product(xs, xs)给出了 xs 与自身的交叉乘积- 如果可迭代的任何元素为真，则返回 true
any(iterable) - 懒惰地
map(function, iterable)(将函数应用于可迭代的每个元素) lambda arg_tuple: expression带有参数的匿名函数arg_tuple并返回表达式的结果
check中的 return 语句使用惰性结构，因此它只执行与 是必需的，并且节省空间。
假设这只是递归练习，它可能不排除"蛮力"方法。 您可以使用递归将每个值与剩余值配对，直到找到匹配的差异。
例如：
def hasDiff(L,diff,base=None):
if not L: return False # empty list: no match
if base is None: # search with & without first as base
return hasDiff(L[1:],diff,L[0]) or hasDiff(L[1:],diff)
return abs(base-L[0]) == diff or hasDiff(L[1:],diff,base) # match or recurse
print(hasDiff([5, 4, 8, -3, 6],9)) # True
print(hasDiff([-1, 5, 4],3)) # False
当函数使用基值递归时，它仅检查列表其余部分中的第一项，并递归其他值。 当函数在没有基值的情况下递归时，它会尝试查找不涉及第一项的新对(即在列表的其余部分中)