ConvertANumberToHexadecimal [source code]

public class ConvertANumberToHexadecimal {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] digits = Integer.toBinaryString(num).toCharArray();
        int len = digits.length;
        char[] res = new char[len % 4 == 0 ? len / 4 : (len / 4 + 1)];
        int power = 1;
        int hexDigit = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (power > 8) {
                res[res.length - (len - 1 - i) / 4] = (hexDigit > 9) ? (char)('a' + hexDigit - 10) : (char)('0' + hexDigit);
                power = 2;
                hexDigit = digits[i] - '0';
            } else {
                hexDigit += (digits[i] - '0') * power;
                power *= 2;
            }            
        }
        res[0] = (hexDigit > 9) ? (char)('a' + hexDigit - 10) : (char)('0' + hexDigit);
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        ConvertANumberToHexadecimal tester = new ConvertANumberToHexadecimal();
        int input1 = -100001;
        System.out.println(Integer.toHexString(input1));
        System.out.println(tester.toHex(input1));
    }
}

看起来很简单的一个题目, 结果写了很长时间. 这个题目的思路其实是很简单的, 直接就是先表示成 binary, 然后分段转换就行了. 难点就在于这个循环本身的细节的写法.

首先, 分段问题这里不是第一次碰到了. 前面有一次用段落的 index 来 iterate, 当时的效果不太好, 所以这一次尝试直接用 element 的 index 来 iterate. 写起来其实还不算复杂. 不过这样的 iteartor, 就带来你必须要积极处理段落结束的问题和判断. 这一题段落结束我使用 power 来进行判断, 这个属于常规. 一个比较tricky 的地方在于当段落结束的那个 i 的位置, 你怎么更新 power 和 hexDigit. 不能想着直接归零, 这样就出问题了.

这题花了这么多时间的另外一个原因是因为 char 跟 int 之间的互相转换也不熟悉. 其实这个问题在 JAVA 里面都属于是比较简单的了.

另外注意 JAVA 本身的Integer.toBinaryString函数返回的这个 string, 是自动把所有的leading 0s都 trim 掉的. 我刚开始还想着自己先扫一遍找到第一个非零位置.

另外注意这一题应该从右往左扫, 这样好处理一些, 往 res 里面扔结果的时候也是从右往左方便一些.

在计算一个段落内的四位的数值的时候, 这里用sum += 2 * sum + digit的递归思路并不好用,因为 again, 我们这里是从右到左, 这个递归计算方式比较适合从左到右(从高位到低位). 从低位到高位, 就直接按位加和就行了.

这里的一个小优化就是每一位的值不用Math.pow来计算, 而是通过一直维护 power (每一位的 weight) 来进行计算. 这样做还有一个好处就是被维护的 power 正好可以用来作为判断段落结束的工具.

总体来说这个真的是一个很简单的题目,结果花了这么多时间只能说基本功的短板太多, 被这个问题暴露了.

最后的速度只有8(48), 比较 mediocre.

Problem Description

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.
Example 1:

Input:
26

Output:
"1a"
Example 2:

Input:
-1

Output:
"ffffffff"
Difficulty:Easy
Category:Algorithms
Acceptance:40.99%
Contributor: LeetCode
Related Topics
bit manipulation