LeetCode 1868. 两个行程编码数组的积（双指针）
LeetCode 1868. 两个行程编码数组的积（双指针）
文章目录
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]*n
arr2 = [0]*n
i, idx = 0, 0
while i < len(encoded1):
t = encoded1[i][1]
num = encoded1[i][0]
while t > 0:
arr1[idx] = num
idx += 1
t -= 1
i += 1
i, idx = 0, 0
while i < len(encoded2):
t = encoded2[i][1]
num = encoded2[i][0]
while t > 0:
arr2[idx] = num
idx += 1
t -= 1
i += 1
p = [arr1[i]*arr2[i] for i in range(len(arr1))]
ans = []
ct = 0
for 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 = 1
else:
ct += 1
ans.append([p[-1], ct])
return ans2.2 优化
- 一边检查，取出个数较少的，放入答案，同时检查跟答案尾部的是否数值一样，一样的话进行合并
class Solution:
def findRLEArray(self, encoded1: List[List[int]], encoded2: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
ans = []
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+=1
elif encoded1[i][1] < encoded2[j][1]:
encoded2[j][1] -= encoded1[i][1]
ct = encoded1[i][1]
i+=1
else:
ct = encoded1[i][1]
i+=1
j+=1
if len(ans)>0 and ans[-1][0]==num: # 数值一样，合并个数
ans[-1][1] += ct
else:
ans.append([num, ct])
return ans376 ms 62.9 MB Python3
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
腾讯云开发者
