LeetCode题练习与总结：数字转换为十六进制数--405

一、题目描述

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

答案字符串中的所有字母都应该是小写字符，并且除了 0 本身之外，答案中不应该有任何前置零。

注意: 不允许使用任何由库提供的将数字直接转换或格式化为十六进制的方法来解决这个问题。

示例 1：

输入：num = 26
输出："1a"

示例 2：

输入：num = -1
输出："ffffffff"

提示：

• -2^31 <= num <= 2^31 - 1

二、解题思路

1. 对于非负整数，我们可以通过不断对16取余，然后将余数转换为十六进制字符，直到商为0为止。在这个过程中，将得到的十六进制字符倒序排列，即可得到该整数的十六进制表示。

2. 对于负整数，我们可以利用Java中int类型是32位的特性，将其视为一个32位的二进制数。对于负整数，我们可以通过将其与0xFFFFFFFF进行按位与操作，得到其补码表示。然后，按照非负整数的方法将其转换为十六进制数。

3. 在转换过程中，需要注意将余数0-15转换为对应的十六进制字符，可以使用一个字符数组来映射。

三、具体代码

class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }
        char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 8; i++) {
            // 取num的最低4位，并找到对应的十六进制字符
            sb.append(hex[num & 0xF]);
            // 将num右移4位
            num >>= 4;
        }
        // 去掉结果字符串的前置零，并反转字符串
        return sb.reverse().toString().replaceAll("^0+", "");
    }
}

以上代码中，我们使用了一个长度为8的循环，每次循环处理num的最低4位，并将其转换为对应的十六进制字符。最后，我们将得到的字符串反转，并去掉前置零。这样，对于正数，循环会在num变为0时停止；对于负数，由于我们使用了按位与操作，循环会在8次后停止，从而得到32位的补码表示。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 在给定的代码中，有一个固定长度为8的循环。无论输入的整数num是什么，循环都会执行8次。这是因为我们正在处理一个32位的整数，每次循环处理4位。

• 在循环内部，每次迭代执行的操作是常数时间的操作：取最低4位、查找对应的十六进制字符、以及将整数右移4位。

因此，循环的时间复杂度是O(1)，因为它执行的迭代次数是固定的，不依赖于输入num的大小。

• 在循环之后，StringBuilder对象的reverse()方法的时间复杂度也是O(1)，因为它反转的是一个固定长度的字符串（最多8个字符）。

• toString()方法的时间复杂度也是O(1)，因为它将StringBuilder对象转换为字符串，这是一个固定长度的操作。

• replaceAll()方法的时间复杂度也是O(1)，因为它处理的是一个固定长度的字符串，并且正则表达式"^0+"匹配的是字符串开头的一个或多个’0’，这在最坏的情况下也不会超过8个字符。

综上所述，整个toHex方法的时间复杂度是O(1)。

2. 空间复杂度

• 字符数组hex的空间复杂度是O(1)，因为它的大小是固定的16个元素。

• StringBuilder对象sb的空间复杂度是O(1)，因为它最多只能存储8个十六进制字符。

• 在方法中没有使用额外的数据结构，如数组、列表或映射，来存储与输入大小成比例的数据。

因此，整个toHex方法的空间复杂度是O(1)。

五、总结知识点

• 基础数据类型：使用了Java的基础数据类型int来表示整数。

• 字符数组：使用字符数组hex来存储十六进制的字符映射。

• 位操作：

  • &（按位与操作）：用于取出整数的最低4位。
  • >>（右移操作）：用于将整数的位向右移动，每次移动4位。

• 循环结构：使用了一个for循环来重复执行操作，直到完成32位整数的转换。

• 条件语句：使用if语句来检查特殊情况，即当num为0时，直接返回字符串"0"。

• StringBuilder类：

  • 用于构建字符串，允许动态地添加字符。
  • append()方法：用于向StringBuilder对象中添加字符。
  • reverse()方法：用于反转StringBuilder中的字符顺序。

• String类：

  • toString()方法：将StringBuilder对象转换为String对象。
  • replaceAll()方法：用于替换字符串中匹配正则表达式的部分。

• 正则表达式：在replaceAll()方法中使用"^0+"正则表达式来匹配字符串开头的所有’0’字符。

• 算法逻辑：代码实现了将整数转换为十六进制表示的逻辑，特别处理了负数的情况，通过将整数与0xFFFFFFFF（即32个1的二进制表示）进行按位与操作，来获取其补码形式。

• 处理边界情况：代码中处理了num为0的边界情况，直接返回"0"。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。