Python程序：计算行程长度编码向量的点积

假设我们有两个列表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))

输入

[2, 7, 5, 3], [3, 5, 4, 2]

输出

109

更新于：2021年10月16日

270 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告