使用Python检查数组对是否可被k整除的程序

假设我们有一个名为nums的数组，该数组包含偶数个元素，还有一个值k。我们必须将nums分成恰好n/2对，使得每对的和都能被k整除。如果我们可以这样做，则返回true，否则返回false。

因此，如果输入类似于nums = [9,5,3,4,7,10,20,8] k = 3，则输出将为True，因为我们可以构成如下对：(9,3), (5,7), (4,20), (8,10)，所有对的和都能被3整除。

为了解决这个问题，我们将遵循以下步骤：

  • dp := 新列表

  • count:= 0

  • 对于nums中的每个x，执行：

    • t:= k - (x mod k)

    • 如果t等于k，则：

      • count := count + 1

    • 否则：

      • 将t插入dp的末尾

  • 如果count mod 2不等于0，则：

    • 返回False

  • 对列表dp进行排序

  • low := 0

  • high := dp的大小 - 1

  • 当low < high时，执行：

    • 如果dp[low] + dp[high]不等于k，则：

      • 返回False

    • low := low + 1

    • high := high - 1

  • 返回True

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

def solve(nums, k):
   dp=[]
   count=0
   for x in nums:
      t=k-(x % k)
      if t == k:
         count+=1
      else:
         dp.append(t)
   if count % 2 != 0:
      return False
   dp.sort()
   low = 0
   high = len(dp)-1
   while low < high:
      if dp[low] + dp[high] != k:
         return False
      low += 1
      high -= 1
   return True
nums = [9,5,3,4,7,10,20,8]
k = 3
print(solve(nums, k))

输入

[9,5,3,4,7,10,20,8], 3

输出

True

更新于：2021年5月29日

262 次浏览

开始您的职业生涯

完成课程后获得认证

开始
广告