华为OD机考算法题：TLV解码

目录

题目部分

解析与思路

代码实现

---

题目部分

---

解析与思路

题目解读：

题目中，有两行输入。其中第二行是 TLV 信息流。TLV 信息流由多个信元组成，每个信元又由 Tag、Length、Value 组成；第一行是 Tag，即一个 TLV 信元的 Tag。

题目要求从第二行的多个信元中，找到第一行的 Tag 所对应的信元。然后输出此信元的 Value。

在输入示例中，第一行指定了信元的 Tag 是31，第二行输入的信息流包含了 5个 信元，依次为32、90、30、31、33。我们找到 Tag 为 31 的信元，它为 31 02 00 32 33，其中 31 是 Tag，02 00（即2）是长度，那么其紧跟的 2 个字节 32 33 为 Value，所以最终的结果输出为 32 33。

分析与思路：

此题根据指定的 Tag，从信息流中找到对应的信息员，输出其 Value即可，并不涉及太复杂的逻辑算法。实现如下：

1. 记录第一行输入的数字，设为变量 Tag。
2. 逐一遍历第二行输入的信息流。遍历时，先判断第一个输入是否等于tag：

• 如果等于 Tag，则继续遍历接下来的 2 个字节，（根据小端序）计算长度，设为变量 length，然后输出接下来的 length 个字节，即为最终输出。输出后退出程序。
• 如果不等于 Tag，则继续遍历接下来的2个字节，计算长度，设为变量 length，然后跳过接下来的 length 个字节，然后继续步骤 2。

此算法只需要遍历一次第二行的输入，时间复杂度为 O(n)，只需要2个额外的辅助变量，空间复杂度为 O(1)。

---

代码实现

Java代码

import java.util.Scanner;
 
/**
 * TLV解码
 * @since 2023.09.04
 * @version 0.2
 * @author Frank
 *
 */
public class LTV_Solution {
	public static void main(String[] args) {		
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {			
			// 第一行输入的tag
			String tag = sc.nextLine();
			
			// 第二行输入的TLV数据流
			String stream = sc.nextLine();
			String[] tlvStream = stream.split(" ");
			processLTVSolution( tag, tlvStream );
		}
	}
	
	private static void processLTVSolution( String tag, String tlvStream[] )
	{
		int i = 0;
		while (i < tlvStream.length) {
			String tagTmp = tlvStream[i];
 
			String lengthStr = tlvStream[i + 2] + tlvStream[i + 1];
			int length = Integer.parseInt(lengthStr, 16);
 
			// 已找到，输出
			if ( !tagTmp.equals( tag )) {
				// 没有找到Tag，略过，寻找下一个
				i += ( 3 + length);
				continue;
			}
			StringBuilder outputSB = new StringBuilder();
			for (int j = 0; j < length; j++) {
				outputSB.append(tlvStream[i + j + 3]);
				if (j != length - 1) {
					outputSB.append(" ");
				}
			}
			System.out.println(outputSB.toString());
			return;
		}
	}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        // 第一行数据
        var tag = line;        
        // 第二行数据转换成数组
        line = await readline();
        var ltvs = line.split(" ");
        processLTVSolution(tag, ltvs);
    }
 
}();
 
function processLTVSolution(tag, ltvs) {
    var i = 0;
    while (i < ltvs.length) {
        var tagTmp = ltvs[i];
        var lengthStr = ltvs[i + 2] + ltvs[i + 1];
        var length = parseInt(lengthStr, 16);
 
        // 没有找到Tag，略过，寻找下一个
        if (tagTmp != tag) {            
            i += (3 + length);
            continue;
        }
 
        // 已找到，输出
        var output = "";
        for (var j = 0; j < length; j++) {
            output += (ltvs[i + j + 3]);
            if (j != length - 1) {
                output += " ";
            }
        }
        console.log(output);
        return;
    }
}

(完)