重复向量压缩与点积：按两侧run交叠长度乘加

题目重点：RLE保留位置顺序，单纯统计全局值频率无法计算点积。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

每向量以连续run(value,count)列表表示，count正整数、两向量总长度相等。
相同值非连续出现不能合成一个run；dot按相同位置逐项相乘求和。

解题路线

两指针记录当前run剩余次数。交叠长度=min(remA,remB)，贡献take×valueA×valueB。
减去take，某run耗尽则推进该侧；每步至少推进一个run，保证工作按run数量而非展开长度。
稀疏向量适用于大量零但非连续重复；按index存非零再交集乘加。压缩选择必须与重复形态匹配，而非见重复就删除位置。

手动走一遍

A=[(2,3),(1,2)]，B=[(4,1),(0,2),(3,2)]：贡献2×4×1+2×0×2+1×3×2=14。A=[1,2]、B=[2,1]点积4；只存各有一个1一个2会丢掉位置信息。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def dot_rle(a,b):
    if any(type(count) is not int or count<=0 for value,count in a+b):raise ValueError("positive run counts required")
    if sum(c for v,c in a)!=sum(c for v,c in b):raise ValueError("different vector lengths")
    i=j=answer=0
    ca=a[0][1] if a else 0;cb=b[0][1] if b else 0
    while i<len(a) and j<len(b):
        take=min(ca,cb);answer+=take*a[i][0]*b[j][0];ca-=take;cb-=take
        if not ca:
            i+=1
            if i<len(a):ca=a[i][1]
        if not cb:
            j+=1
            if j<len(b):cb=b[j][1]
    return answer

复杂度

ra/rb个run，O(ra+rb)时间，除输入O(1)指针状态。Python整数乘法位成本另计；输入校验也按run数扫描。

易错点与追问

容易失分的边界

长度不等不应静默在较短侧耗尽时截断。
浮点向量压缩不能直接用近似相等合run而不说明误差。

继续深挖

RLE与稀疏格式混合时怎样跳过零段？
需要随机点访问/区间和时，run累计端点索引如何改变空间与查询成本？