LeetCode 504. 七进制数，进制转换题解。

题目

504. 七进制数

https://leetcode.cn/problems/base-7/

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

迭代

思路

运用了我中学时候学过的进制转换过程：

  • 每次用num除以7
  • 保留余数、商
  • 商继续第一步的过程
  • 余数则后缀拼接为答案

需要对0、负数、前缀做判断。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

static class Traversal {
    /*
        * 执行用时：
        * 1 ms
        * , 在所有 Java 提交中击败了
        * 74.64%
        * 的用户
        * 内存消耗：
        * 39.2 MB
        * , 在所有 Java 提交中击败了
        * 20.46%
        * 的用户
        * 通过测试用例：
        * 241 / 241
        */
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }

        boolean positive = num > 0;

        StringBuilder ans = new StringBuilder();
        while (num != 0) {
            int quotient = num / 7;
            int remainder = num % 7;

            ans.insert(0, positive ? remainder : -remainder);
            num = quotient;
        }
        return positive ? ans.toString() : "-" + ans;
    }
}

复杂度分析

时间

最多迭代对数次：复杂度O(log∣num∣)。

空间

空间占用为字符数组长度，与迭代次数相同，空间复杂度大致为O(log∣num∣)。

递归

思路

递归效率较低。特判操作比较低效。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

static class Recursion {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean positive = num > 0;
        int quotient = num / 7;
        int remainder = num % 7;
        String ans = convertToBase7(quotient) + (positive ? remainder : -remainder);
        ans = ans.startsWith("0") ? ans.substring(1) : ans;
        ans = ans.startsWith("-") ? ans.substring(1) : ans;
        return positive ? ans : "-" + ans;
    }
}

复杂度分析

同解法1。