Pythonでランレングスエンコードされたベクトルの内積を見つけるプログラム

nums1とnums2の2つのリストがあるとします。これらの2つのリストはそれぞれ、ランレングスエンコード形式のベクトルを表しています。したがって、例として、ベクトル[1、1、1、2、2、2、2]は[3、1、4、2]として表されます。 （3つの1と4つの2があるため）。したがって、これら2つのベクトルの内積を見つける必要があります。 （内積は、2つのベクトルに存在する項目の要素ごとの乗算の合計です。）

したがって、入力がnums1 =[2、7、5、3] nums2 =[3、5、4、2]の場合、ベクトルは[7、7、3、3]のようになるため、出力は109になります。 、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の場合、
    • 挿入|count2-count1| nums2の終わりに
    • nums2の最後にval2を挿入します
  • それ以外の場合、count1> count2の場合、
    • 挿入|count2-count1| nums1の終わりに
    • nums1の最後にval1を挿入します
• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

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