题目描述
给你一个非负整数 num
,返回它的 加密字符串。
加密的过程是把一个整数用某个未知函数进行转化,你需要从下表推测出该转化函数:
样例
输入:num = 23
输出:"1000"
输入:num = 107
输出:"101100"
限制
0 <= num <= 10^9
算法
(找规律) $O(\log n)$
- 可以很容易发现,编码的字符串在每个长度 $l$ 内都是按 0 到 $2^l-1$ 的方式排列的。
- 首先寻找最终编码字符串的长度,寻找长度的过程中,让目标值减去当前长度能编码字符串的数量。
时间复杂度
- 寻找长度的时间复杂度为 $O(\log n)$,构造答案的时间复杂度为 $O(\log n)$。
- 故最终时间复杂度为 $O(\log n)$。
空间复杂度
- 需要额外 $O(\log n)$ 的空间存储答案。
C++ 代码
class Solution {
public:
string encode(int num) {
int len = 0;
while (num >= (1 << len)) {
num -= (1 << len);
len++;
}
string ans;
for (int i = 0; i < len; i++, num >>= 1)
if (num & 1)
ans += '1';
else
ans += '0';
reverse(ans.begin(), ans.end());
return ans;
}
};