P2534. TLV编码

解题思路

又是一道比较难读懂的题目，需要一些前置知识的理解。

大端序和小端序

这道题涉及一个前置知识，大端序和小端序。 这两种排序都是字节序，表示的是数据字节在内存中的存储方式。

• 大端序（Big-Endian） 指的是数据的低位字节存放在内存的高位地址，高位字节存放在内存的低位地址。这种排列方式与数据用字节表示时的书写顺序一致，符合人类的阅读习惯。
• 小端序（Little-Endian） 指的是数据的低位字节存放在内存的低位地址，高位字节存放在高位地址。小端序与人类的阅读习惯相反，但更符合计算机读取内存的方式，因为 CPU 读取内存中的数据时，是从低地址向高地址方向进行读取的。

看起来有点拗口，但只需要记住：大端序从左到右排列符合人类阅读习惯，小端序从右到左排列不符合人类阅读习惯即可。

TLV 码流的解码过程

下图显示了示例的码流的解码过程： 蓝、绿、红构成的一整段内容表示一个信元，其中：

• 蓝色表示信元的唯一标识 tag
• 绿色表示信元的 value 的长度
• 红色表示信元的 value 的内容

我们要做的事情，就是找到 tag 为第一行输入的 target_tag 的那个信元，所对应的 value 的内容。

模拟过程

本题剩余内容，只需要按照题目要求进行模拟即可。

我们可以构建一个 help 辅助函数，用于一个特定信元的解码。 其中，传入的参数 stream 为输入码流数组，idx 为当前信元标识在数组中的索引。容易得到代码：

在这个函数外部，由于 idx 增加的幅度是根据每次解码后得到的信元内容的长度 length 决定的，并不是一个固定值，我们需要在 while 循环中进行遍历。

循环条件为，idx 在 stream 中对应的字符串不是目标信元 target_tag。 在循环中，我们调用 help 函数，得到当前信元的标识 cur_tag 和长度 cur_length。

信元标识和长度一共占 3 位，信元中的信息占 cur_length 位，因此下一个信元的标识 tag 的位置位于 stream 数组中的 idx + 3 + cur_length 处。综上可以得到代码：

退出 while 循环后，idx 所在的位置即为目标信元 target_tag 的标识。 再一次调用 help 函数，进行信元解码，得到目标信元的长度 cur_length。 此时 stream 中，从索引 idx+3 到 idx+3+cur_length 位置的切片，就是目标信元的内容，将其输出即为最终的答案。

复杂度分析 设 n 为码流中的字节数（即 stream 数组的长度）。主体是一个 while 循环，从 idx = 0 出发，每轮调用一次 help 函数：help 只做「取 tag、按小端序把两个长度字节拼成十六进制串、转成十进制」这几步常数操作，是 O(1)；随后 idx 直接跳到下一个信元的 tag 位置（idx += 3 + cur_length）。也就是说循环不是逐字节挪动，而是以信元为单位向前跳，每个信元最多被访问一次，所有跳跃加起来最多覆盖整条码流，因此查找目标 tag 的过程是 O(n)。找到后再做一次 O(1) 的解码，并取出长度为 cur_length 的切片拼接输出，这一步最多 O(n)。所以总时间复杂度为 O(n)，瓶颈是按信元跳跃扫过码流这一遍。空间上，stream 数组本身占 O(n)，解析过程只用了 idx、cur_tag、cur_length 几个变量，除输入和输出切片外的额外空间为 O(1)。