java - 不使用 Integer.toHexString() 将 int 转换为十六进制字符串；

Question

以下是来自的问题陈述 LeetCode .

Given an integer, write an algorithm to convert it to hexadecimal. Fornegative 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 bethe 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.

这是我的解决方案:

public class Solution {
    private static final String characters = "0123456789abcdef";
    private static final char[] digits = characters.toCharArray(); 
    
    private Stack<Integer> stack = new Stack<>();
    public String toHex(int num) {
        if (num == 0) return "0";
        
        stack.clear();
        while (num != 0) {
            stack.push(getDigit(num));
            num = num >>> 4;
            System.out.println(num);
            if (stack.size() > 8) break;
        }
        
        StringBuilder buffer = new StringBuilder();
        while (!stack.empty()) {
            buffer.append(digits[stack.pop()]);
        }
        
        return buffer.toString();
    }
    
    private int getDigit(int num) {
        int result = num & 0xF;
        return result;
    }
}

问题是该解决方案有效，但性能不佳——我在该解决方案的运行时间中处于底部 1%。我想知道我对 Stack 对象或 StringBuilder 的使用是否让我感到悲伤。

也完全有可能大量提交忽略限制并无论如何都使用 Java API。 :) 但我想我会在这里发帖并学习如何提高效率。

Answer 1

我只对您的代码进行了一些调整，就实现了一个小改进。

我将运行时间缩短了 8 毫秒，超过了 51.90% 的其他解决方案。

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    private Stack<Integer> stack = new Stack<>();
    public String toHex(int num) {
        if (num == 0) return "0";

        stack.clear();
        while (num != 0) {
            stack.push(num & 0xF);
            num = num >>> 4;
            if (stack.size() > 8) break;
        }

        StringBuilder buffer = new StringBuilder();
        while (!stack.empty()) {
            buffer.append(digits[stack.pop()]);
        }

        return buffer.toString();
    }
}

首先，我改变了 digits 数组的构造方式，将原来的两行压缩为一行。

我还删除了 System.out.println 调用。

最后，我用主代码中内联的内容替换了对 getDigit() 方法的调用。

* 更新 *

这也是一个更简洁的选项，将循环数减少为一个并消除了使用 Stack 的需要。

public class Solution {
    private static final char[] digits = "0123456789abcdef".toCharArray(); 

    public String toHex(int num) {
        if (num == 0) return "0";

        StringBuilder buffer = new StringBuilder();
        while (num != 0) {
            buffer.append(digits[num & 0xF]);
            num = num >>> 4;
        }
        return buffer.reverse().toString();
    }
}

注意:这个性能似乎在 7 毫秒和 8 毫秒之间波动。