【华为OD-E卷 - 整数编码 100分（python、java、c++、js、c）】

【华为OD-E卷 - 整数编码 100分（python、java、c++、js、c）】

题目

实现一种整数编码方法，使得待编码的数字越小，编码后所占用的字节数越小。
编码规则如下:
编码时7位一组，每个字节的低7位用于存储待编码数字的补码 字节的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。 采用小端序编码，低位和低字节放在低地址上。 编码结果按16进制数的字符格式输出，小写字母需转换为大写字母

输入描述

• 输入的为一个字符串表示的非负整数

输出描述

• 输出一个字符串，表示整数编码的16进制码流

备注

• 待编码的数字取值范围为[0，1<<64 - 1]

用例

用例一：

输入：

0

输出：

00

用例二：

输入：

100

输出：

64

用例三：

输入：

1000

输出：

E807

说明 1000的二进制表示为0011 1110 1000，至少需要两个字节进行编码;

第一个字节最高位置1，剩余的7位存储数字1000的第一个低7位 (1101000)，所以第一个字节的二进制为1110 1000，即E8;

第二个字节最高位置0，剩余的7位存储数字1000的第二个低7位 (0000111)，所以第一个字节的二进制为0000 0111，即07;

采用小端序编码，所以低字节E8输出在前，高字节07输出在后。

python解法

• 解题思路：
• 该问题是将一个整数编码为变长的字节序列，其中每个字节的最高位是一个标志位，表示后续字节是否存在。具体来说，使用7位来表示数值，剩余的1位用作标志位来表示是否还有后续字节。每次编码后，若数值还大于等于128（即7位无法完全表示），则需要继续编码。最终返回的结果是这些字节的十六进制表示。

对于每个数值，取低7位作为当前字节的值（通过与0x7F按位与操作获得），然后将这个字节的最高位设为1（通过按位或操作），表示后续还有字节。
当数值变小到小于128时，停止编码，将其直接以十六进制格式返回

def encode_number(num):res = []  # 用于保存每个编码后的字节while num >= 128:  # 当数字大于等于128时，需要继续编码# 通过num & 0x7F 获取低7位，0x80表示设置字节的最高位为1res.append(f"{(num & 0x7F) | 0x80:02X}")  # 格式化为2位的十六进制数，添加到结果列表num >>= 7  # 将num右移7位，为编码下一段数值做准备# 最后一个字节，直接以低7位表示，无需设置最高位res.append(f"{num:02X}")  # 格式化为2位的十六进制数，添加到结果列表return "".join(res)  # 将所有字节拼接成一个字符串并返回# 输入整数，进行编码并输出结果
num = int(input())  # 从用户输入读取一个整数
print(encode_number(num))  # 调用encode_number函数进行编码，并打印结果

java解法

• 解题思路
• 该问题是将一个 long 类型的整数编码为变长的字节序列，其中每个字节的最高位是一个标志位，用来表示是否还有后续字节。每个字节的低7位用来表示数值的部分。根据编码规则，处理的过程如下：

每个字节的构成：
对于一个整数，将其分解为多个字节。每个字节表示 7 位数值，最高位（即第8位）用作标志位，表示后续是否还有字节。如果某个字节的最高位是 1，说明后面还有字节。如果是 0，表示这是最后一个字节。

过程：

将整数按 7 位拆分。
对于每个拆分出来的部分，设置其最高位为 1（表示后面还有字节）直到没有更多的数值需要编码。
当数值小于 128 时，设置该字节的最高位为 0，表示这是最后一个字节。
通过按位操作，逐步提取每个字节，并拼接结果。
编码输出：
编码后的结果是一个十六进制的字符串，表示每个字节

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);  // 创建Scanner对象用于读取输入long val = in.nextLong();  // 读取一个long类型的数值Encoder enc = new Encoder();  // 创建Encoder对象System.out.println(enc.encode(val));  // 调用Encoder的encode方法，输出编码结果}
}class Encoder {// 编码方法：将long类型的val编码为变长字节序列public String encode(long val) {StringBuilder sb = new StringBuilder();  // 用于构建编码后的字符串boolean cont = true;  // 标志位，表示是否还需要继续编码// 当还需要继续编码时while (cont) {// 获取val的低7位，使用int类型保存，低7位用来表示字节的内容int num = (int) (val & 0x7F);val >>>= 7;  // 无符号右移7位，为下一次编码做准备// 如果val还有剩余的数值，则设置当前字节的最高位为1if (val != 0) {num |= 0x80;  // 设置最高位为1，表示后续还有字节} else {cont = false;  // 如果val已经处理完，停止编码}// 将当前字节num以2位大写十六进制格式添加到StringBuilder中sb.append(String.format("%02X", num));}return sb.toString();  // 返回编码后的十六进制字符串}
}

C++解法

• 解题思路
• 该问题的目标是将一个给定的 long long 类型整数编码成一个变长字节流，每个字节由7位数据和1位标志位组成。具体规则是：

字节格式：每个字节的最低7位用来存储数据，而最高1位用来作为标志位，表示是否还有后续字节。如果最高位为 1，表示还有更多字节；如果为 0，表示没有后续字节。
拆分流程：
将整数转换为二进制字符串。
按照每7位一组将其拆分。
对每一组数据，若不为最后一组，则设置最高位为 1，表示后续还有字节；否则，设置为 0，表示结束。
结果表示：将每个字节转为十六进制字符串，并拼接成最终的编码结果

#include <iostream>
#include <string>
#include <bitset>
#include <sstream>
#include <iomanip>using namespace std;// 将二进制字符串转换为十六进制字符串
string getHexString(const string &binStr) {int hexValue = stoi(binStr, nullptr, 2);  // 将二进制字符串转换为十进制整数stringstream ss;  // 创建字符串流// 将整数输出为十六进制格式，宽度为2，若不足两位前补零，且使用大写字母ss << hex << uppercase << setw(2) << setfill('0') << hexValue;return ss.str();  // 返回转换后的十六进制字符串
}// 获取结果，将long long类型的num转换为变长编码的十六进制字符串
string getResult(long long num) {// 将num转换为64位的二进制字符串string bin = bitset<64>(num).to_string();// 去掉二进制字符串前面的0，保留有效的二进制部分bin = bin.substr(bin.find('1')); stringstream ans;  // 用于保存编码后的十六进制结果int end = bin.length();  // 获取二进制字符串的长度// 按7位一组地处理二进制字符串while (end - 7 > 0) {// 获取当前的7位数据，并在其前面加上1，表示后面还有数据ans << getHexString("1" + bin.substr(end - 7, 7));  end -= 7;  // 更新剩余处理的二进制数据长度}// 处理最后不足7位的二进制数据if (end > 0) {ans << getHexString(bin.substr(0, end));  // 最后一个字节无需添加最高位的1}return ans.str();  // 返回编码后的十六进制字符串
}int main() {long long num;  // 定义long long类型的输入cin >> num;  // 读取输入的数字cout << getResult(num) << endl;  // 调用getResult函数并输出结果return 0;
}

C解法

• 解题思路

更新中

JS解法

• 解题思路

• 这个问题是将一个大整数（通过字符串输入）编码为变长字节流，并返回其十六进制表示。每个字节包含7位数据和1位标志位。每个字节的标志位（最高位）用来指示是否还有后续字节，规则如下：

字节构成：

每个字节包含 7 位数据（低7位）和 1 位标志位（最高位）。
若当前字节的标志位为 1，表示后续还有字节需要编码；若为 0，表示当前字节是最后一个字节。
编码过程：

将输入的整数转为 BigInt 类型（处理大整数）。
使用 while 循环按 7 位拆分整数，并为每个字节设置标志位。
将所有字节转换为十六进制，并拼接成最终的结果。
输出：

返回变长编码的十六进制字符串，确保每个字节都以两位十六进制表示（不足两位前补零）

const readline = require("readline");  // 引入 readline 模块用于读取标准输入// 创建 readline 接口
const rl = readline.createInterface({input: process.stdin,  // 从标准输入读取output: process.stdout,  // 输出到标准输出
});// 监听每一行输入
rl.on("line", (line) => {console.log(encodeNumber(line));  // 每输入一行，调用encodeNumber进行编码并打印输出
});// 编码函数：将输入的数字（字符串形式）编码为变长字节流的十六进制字符串
function encodeNumber(numStr) {let num = BigInt(numStr);  // 将输入的字符串转为 BigInt 类型，支持大整数const result = [];  // 用于存储每个字节（编码后的字节）// 循环处理每个字节while (num > 0) {let byte = Number(num & 0x7Fn);  // 获取 num 的最低7位（即低7位），并将其转换为普通数字num >>= 7n;  // 将 num 右移 7 位，准备处理下一部分数据if (num > 0) {byte |= 0x80;  // 如果 num 仍然大于 0，说明后续还有字节，设置当前字节的最高位为1}result.push(byte);  // 将当前字节加入结果数组}// 处理 num 为 0 的情况if (result.length === 0) {result.push(0);  // 如果输入是0，结果数组中应该只有一个字节，值为0}// 将每个字节转换为十六进制字符串，并拼接成最终的结果return result.map(byte => byte.toString(16).padStart(2, '0').toUpperCase()).join("");
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏