Python程式：查詢操作次數最少的和相等的陣列

假設我們有兩個名為nums1和nums2的陣列。陣列中的值介於1到6（包括1和6）。在一個操作中，我們可以將任何一個數組中的任何值更新為1到6之間的任何值。我們必須找到使nums1的值之和等於nums2的值之和所需的最少操作次數。如果不可能，則必須返回-1。

因此，如果輸入類似於nums1 = [1,5,6]，nums2 = [4,1,1]，則輸出將為2，因為我們可以在第一次操作中將nums2從[4,1,1]更改為[4,1,6]，在第二次操作中更改為[4,2,6]，使其等於nums1。

為了解決這個問題，我們將遵循以下步驟：

  • s1 := nums1中所有元素的和

  • s2 := nums2中所有元素的和

  • 對列表nums1和列表nums2進行排序

  • 如果s1 > s2，則

    • 交換nums1和nums2

    • 交換s1和s2

  • ans := 0

  • left := 0, right := nums2的大小 - 1

  • 當left < nums1的長度 或 right >= 0 時，執行：

    • 如果s1等於s2，則

      • 返回ans

    • curr_left := 如果left < nums1的長度，則為nums1[left]，否則為7

    • curr_right := 如果right >= 0，則為nums2[right]，否則為0

    • 如果6-curr_left >= curr_right-1，則

      • s1 := s1 + min(6-curr_left, s2-s1)

      • left := left + 1

    • 否則，

      • s2 := s2 - min(curr_right-1, s2-s1)

      • right := right - 1

    • ans := ans + 1

  • 如果s1不等於s2，則返回-1，否則返回ans

示例

讓我們看看下面的實現來更好地理解：

def solve(nums1, nums2):
   s1 = sum(nums1)
   s2 = sum(nums2)
   nums1.sort()
   nums2.sort()
   if s1>s2:
      nums1, nums2 = nums2, nums1
      s1, s2 = s2, s1

   ans = 0
   left, right = 0, len(nums2)-1
   while(left<len(nums1) or right>=0):
      if s1==s2:
         return ans
      curr_left = nums1[left] if left<len(nums1) else 7
      curr_right = nums2[right] if right>=0 else 0
      if 6-curr_left>=curr_right-1:
         s1+= min(6-curr_left, s2-s1)
         left+=1
      else:
         s2-= min(curr_right-1, s2-s1)
         right-=1
      ans+=1
   return -1 if s1!=s2 else ans

nums1 = [1,5,6]
nums2 = [4,1,1]
print(solve(nums1, nums2))

輸入

[1,5,6], [4,1,1]

輸出

2

更新於：2021年10月6日

瀏覽量：558

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告