LeetCode Convert a Number to Hexadecimal Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used. Note:
- All letters in hexadecimal (
a-f) must be in lowercase. - The hexadecimal string must not contain extra leading
0s. If the number is zero, it is represented by a single zero character'0'; otherwise, the first character in the hexadecimal string will not be the zero character. - The given number is guaranteed to fit within the range of a 32-bit signed integer.
- You must not use any method provided by the library which converts/formats the number to hex directly.
Input: 26 Output: "1a"Example 2:
Input: -1 Output: "ffffffff"
题意：把一个十进制数转换为十六进制数。如果是负数，则用补码的二进制转换为十六进制。简单题，因为计算机内存存储的就是补码，所以我们只需要取出每4bit，转换为十六进制就好。4bit对应的十六进制字符，可以提前用一个字典（或数组）存储好。 完整代码如下： [cpp] class Solution { public: string toHex(int num) { if (num == 0)return "0"; vector<string> dict = { "0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f" }; int mask = 0xf; string ans = ""; for (int i = 0; i < 8; ++i) { if (num == 0)break; ans = dict[num&mask] + ans; num >>= 4; } return ans; } }; [/cpp] 本代码提交AC，用时3MS。]]>
观察的时候需要分组观察，比如[0,1]的结果为0,1，[2,3]的结果为1,2，也就是在[0,1]的结果上加了1；[4,7]的结果为1,2,2,3，也就是在[0,3]的结果上加了1；[8,15]的结果为1,2,2,3,2,3,3,4，也就是在[0,7]的结果上加了1。
所以重复的周期是以2的幂递增的，初始的时候，我们可以在ans数组中只存[0,1]的结果，然后每次添加2的幂个结果进ans，直到ans的大小大于num为止。
完整代码如下：
[cpp]
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans = { 0,1 };
while (ans.size() <= num) {
int old_size = ans.size();
for (int i = 0; i < old_size; ++i) {
ans.push_back(ans[i] + 1);
}
}
return vector<int>(ans.begin(), ans.begin() + num + 1);
}
};
[/cpp]
本代码提交AC，用时73MS。
]]>