文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 模擬超時
    • 2.2 優化

1. 題目

行程編碼（Run-length encoding）是一種壓縮算法，能讓一個含有許多段連續重復數字的整數類型數組 nums 以一個（通常更小的）二維數組 encoded 表示。

每個 encoded[i] = [vali, freqi] 表示 nums 中第 i 段重復數字，其中 vali 是該段重復數字，重復了 freqi 次。

例如， nums = [1,1,1,2,2,2,2,2] 可表示稱行程編碼數組 encoded = [[1,3],[2,5]] 。
對此數組的另一種讀法是“三個 1 ，后面有五個 2 ”。
兩個行程編碼數組 encoded1 和 encoded2 的積可以按下列步驟計算：

• 將 encoded1 和 encoded2 分別擴展成完整數組 nums1 和 nums2 。
• 創建一個新的數組 prodNums ，長度為 nums1.length 并設 prodNums[i] = nums1[i] * nums2[i] 。
• 將 prodNums 壓縮成一個行程編碼數組并返回之。

給定兩個行程編碼數組 encoded1 和 encoded2 ，分別表示完整數組 nums1 和 nums2 。
nums1 和 nums2 的長度相同。
每一個 encoded1[i] = [vali, freqi] 表示 nums1 中的第 i 段，每一個 encoded2[j] = [valj, freqj] 表示 nums2 中的第 j 段。

返回 encoded1 和 encoded2 的乘積。

注：行程編碼數組需壓縮成可能的最小長度。

示例 1: 輸入: encoded1 = [[1,3],[2,3]], encoded2 = [[6,3],[3,3]] 輸出: [[6,6]] 解釋n: encoded1 擴展為 [1,1,1,2,2,2] ，encoded2 擴展為 [6,6,6,3,3,3]。 prodNums = [6,6,6,6,6,6]，壓縮成行程編碼數組 [[6,6]]。示例 2: 輸入: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]] 輸出: [[2,3],[6,1],[9,2]] 解釋: encoded1 擴展為 [1,1,1,2,3,3] ，encoded2 擴展為 [2,2,2,3,3,3]。 prodNums = [2,2,2,6,9,9]，壓縮成行程編碼數組 [[2,3],[6,1],[9,2]]。 提示： 1 <= encoded1.length, encoded2.length <= 10^5 encoded1[i].length == 2 encoded2[j].length == 2 對于每一個 encoded1[i]， 1 <= vali, freqi <= 10^4 對于每一個 encoded2[j]， 1 <= valj, freqj <= 10^4 encoded1 和 encoded2 表示的完整數組長度相同。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/product-of-two-run-length-encoded-arrays
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

2.1 模擬超時

class Solution:def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:n = sum([x[1] for x in encoded1])arr1 = [0]*narr2 = [0]*ni, idx = 0, 0while i < len(encoded1):t = encoded1[i][1]num = encoded1[i][0]while t > 0:arr1[idx] = numidx += 1t -= 1i += 1i, idx = 0, 0while i < len(encoded2):t = encoded2[i][1]num = encoded2[i][0]while t > 0:arr2[idx] = numidx += 1t -= 1i += 1p = [arr1[i]*arr2[i] for i in range(len(arr1))]ans = []ct = 0for i in range(len(p)):if i==0 or (i>0 and p[i] != p[i-1]):if i > 0:ans.append([p[i-1], ct])ct = 1else:ct += 1ans.append([p[-1], ct])return ans

2.2 優化

• 一邊檢查，取出個數較少的，放入答案，同時檢查跟答案尾部的是否數值一樣，一樣的話進行合并

class Solution:def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:i, j = 0, 0ans = []while i < len(encoded1) and j < len(encoded2):num = encoded1[i][0]*encoded2[j][0]if encoded1[i][1] > encoded2[j][1]:encoded1[i][1] -= encoded2[j][1]ct = encoded2[j][1]j+=1elif encoded1[i][1] < encoded2[j][1]:encoded2[j][1] -= encoded1[i][1]ct = encoded1[i][1]i+=1else:ct = encoded1[i][1]i+=1j+=1if len(ans)>0 and ans[-1][0]==num: # 數值一樣，合并個數ans[-1][1] += ctelse:ans.append([num, ct])return ans

376 ms 62.9 MB Python3

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1868. 两个行程编码数组的积（双指针）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。