题目重点：按长重复段和八值原样块选择编码，明确标签、短尾段与损坏输入。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 题目给出重复至少8时RLE、其他用bin packing并解释为原样copy，末尾不足8优先RLE；未给真实wire header、整数范围或bit width。练习用R(count,value)/B(eight values)标签，B为literal copy而非擅自发明位压缩。
- 为允许R块前有短literal缓冲，训练选择将该缓冲按短重复段发R；最终短尾同样处理。这一边界政策没有明确披露，需面试时确认。
解题路线
- 先找到最大同值run。长度≥8用RLE；较短run依次进literal缓冲，凑足8输出B块。遇长run前先处理残余缓冲，再输出长run，确保输入顺序保持。
- 编码不变式：已经输出token解码后加当前buffer，恰好等于已处理前缀。长run前flush不能与后run换序，短尾不能静默丢弃。
- 解码先检查tag及形状，R必须正整数count，B必须恰8值；再按标签展开。本例只返回内存列表，生产格式还需长度上限、防恶意count放大及校验。
- 编码格式要显式标识类型/长度，不能仅看到重复值便猜RLE，否则literal里的重复与header可能有歧义。实际压缩比依赖header和value位宽，这份tuple格式用于证明语义，不证明节省字节。
手动走一遍
[7]*8→R(8,7)；[0,1,2,3,4,5,6,7,8]→B(0..7),R(1,8)。[1,1]+[2]*8按训练边界生成R(2,1),R(8,2)，不能把短1段合到2的run。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def encode(values):
"""Tagged training format: R(count,value) or B(eight literal values).
R for >=8 runs; short final literal tail is emitted as its short runs.
'B' is literal copy, no invented bit-width packing.
"""
tokens=[];buffer=[]
def flush_tail():
i=0
while i<len(buffer):
j=i+1
while j<len(buffer) and buffer[j]==buffer[i]:j+=1
tokens.append(('R',j-i,buffer[i]));i=j
buffer.clear()
i=0
while i<len(values):
j=i+1
while j<len(values) and values[j]==values[i]:j+=1
if j-i>=8:
flush_tail();tokens.append(('R',j-i,values[i]))
else:
for v in values[i:j]:
buffer.append(v)
if len(buffer)==8:tokens.append(('B',tuple(buffer)));buffer.clear()
i=j
flush_tail()
return tokens
def decode(tokens):
result=[]
for token in tokens:
if token[0]=='R' and len(token)==3 and isinstance(token[1],int) and token[1]>0:
result.extend([token[2]]*token[1])
elif token[0]=='B' and len(token)==2 and len(token[1])==8:
result.extend(token[1])
else:raise ValueError('invalid token')
return result
复杂度
编码O(N)时间、O(N)token输出，literal缓冲至多8。解码时间/空间O(展开长度)，不是O(token数)；长R记录可使展开量远大于压缩输入。未定义header和bit width，不能给精确字节压缩比。
易错点与追问
容易失分的边界
- 把bin packing误解成未经定义的bit-width打包。
- 长R之前丢残余literal缓冲。
- 解码无count预算，少量输入生成巨大输出。
继续深挖
- 若规定literal必须完整8值，长run之前不足8应如何表示？
- 如果改成真实bit-packing，负数范围、bit width和跨字节顺序如何定义？
