用 Python 编写的程序，用于查找游程编码向量的点积

pythonserver side programmingprogramming更新于 2026/1/11 14:04:17

假设我们有两个列表 nums1 和 nums2。这两个列表中的每一个都表示一个游程编码形式的向量。例如，向量 [1, 1, 1, 2, 2, 2, 2] 表示为 [3, 1, 4, 2]。(因为有 3 个 1 和 4 个 2)。所以我们必须找到这两个向量的点积。(点积是两个向量中存在的项的元素乘积之和)。

因此，如果输入为 nums1 = [2, 7, 5, 3] nums2 = [3, 5, 4, 2]，则输出将为 109，因为向量为 [7, 7, 3, 3, 3, 3, 3] • [5, 5, 5, 2, 2, 2, 2] = 7*5 + 7*5 + 3*5 + 3*2 + 3*2 + 3*2 + 3*2 = 35 + 35 + 15 + 6 + 6 + 6 + 6 = 109。

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

ans := 0
当 nums1 和 nums2 都非空时，执行
- val1 := nums1 中的最后一个元素并删除最后一项
- count1 := nums1 中的最后一个元素并删除最后一项
- val2 := nums2 中的最后一个元素并删除最后一项
- count2 := nums2 中的最后一个元素和删除最后一项
- ans := ans + (val1 * val2) * (count2 和 count1 中的最小值)
- 如果 count2 > count1，则
  - 在 nums2 末尾插入 |count2 - count1|
  - 在 nums2 末尾插入 val2
- 否则，当 count1 > count2 时，则
  - 在 nums1 末尾插入 |count2 - count1|
  - 在 nums1 末尾插入 val1
返回 ans

示例

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

def solve(nums1, nums2):
   ans = 0

   while nums1 and nums2:
      val1 = nums1.pop()
      count1 = nums1.pop()
      val2 = nums2.pop()
      count2 = nums2.pop()

      ans += (val1 * val2) * min(count2, count1)

      if count2 > count1:
         nums2.append(abs(count2 - count1))
         nums2.append(val2)
      elif count1 > count2:
         nums1.append(abs(count2 - count1))
         nums1.append(val1)

   return ans

nums1 = [2, 7, 5, 3]
nums2 = [3, 5, 4, 2]
print(solve(nums1, nums2))