时间戳

首页 > 解决方案 > 使用递归找到一对中的目标差异

python - 使用递归找到一对中的目标差异

问题描述

给定一个未排序整数列表和一个目标整数，通过递归找出列表中任何对的差是否等于目标整数。

>>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True

>>> aList = [-1, 5, 4]
>>> target = 3
return False

我试过了，但没有用。

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)

如果我们不能使用循环对列表进行排序，我不确定如何解决这个问题。即使我们可以使用递归对列表进行排序，递归应该如何查看每一对的差异？

标签： pythonrecursion

解决方案

所以我实际上实现了它，但出于教育目的，我要稍后再发布它（我会在几个小时内更新它），因为我认为这是针对课程或其他一些你应该弄清楚的设置靠自己。

假设您正在尝试达到差异目标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 中）。

我会在几个小时后发布我的解决方案。祝你好运！

编辑 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

编辑2：

这是一个非常聪明和有效的解决方案。我确实意识到可能根本不允许任何遍历（即不存在查询集合）。如果是这种情况，上述方法可以使用一个固定大小的列表来完成，该列表预先分配的大小等于列表值的范围。

如果预先分配给列表范围大小的概念仍然是太多的迭代，我可以考虑递归实现的穷举方法。可能有一种更有效的方法，但您可以将问题归结为类似双循环的问题（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

推荐阅读