資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝學
法學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 次瀏覽
廣告