Easy

题目描述

给定一个整数 num，返回其七进制数字符串表示。

示例 1:

输入: num = 100
输出: "202"

示例 2:

输入: num = -7
输出: "-10"

提示:

  • -10^7 <= num <= 10^7

解题思路

解题思路

这是一个经典的进制转换问题。我们需要将十进制数转换为七进制数。

方法一：除法取余法（推荐）

核心思想是不断除以7并记录余数，然后将余数倒序组合：

  1. 特殊处理：如果 num 为 0，直接返回 “0”
  2. 记录符号：如果 num 为负数，先记录负号，然后取绝对值处理
  3. 循环处理：不断除以 7，将余数加到结果字符串的前面
  4. 返回结果：如果原数为负，在结果前加上负号

方法二：递归法

也可以用递归的方式实现，但空间复杂度会稍高一些。

方法三：利用内置函数

某些语言提供了进制转换的内置函数，但为了展示算法思路，这里主要实现手动转换。

时间复杂度为 O(log₇n)，因为需要进行 log₇n 次除法运算。空间复杂度为 O(log₇n)，用于存储结果字符串。

代码实现

class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) return "0";
        
        bool negative = num < 0;
        if (negative) num = -num;
        
        string result = "";
        while (num > 0) {
            result = to_string(num % 7) + result;
            num /= 7;
        }
        
        return negative ? "-" + result : result;
    }
};

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"
        
        negative = num < 0
        if negative:
            num = -num
        
        result = ""
        while num > 0:
            result = str(num % 7) + result
            num //= 7
        
        return "-" + result if negative else result

public class Solution {
    public string ConvertToBase7(int num) {
        if (num == 0) return "0";
        
        bool negative = num < 0;
        if (negative) num = -num;
        
        string result = "";
        while (num > 0) {
            result = (num % 7).ToString() + result;
            num /= 7;
        }
        
        return negative ? "-" + result : result;
    }
}

var convertToBase7 = function(num) {
    if (num === 0) return "0";
    
    let isNegative = num < 0;
    num = Math.abs(num);
    
    let result = "";
    while (num > 0) {
        result = (num % 7) + result;
        num = Math.floor(num / 7);
    }
    
    return isNegative ? "-" + result : result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(log₇n)
空间复杂度O(log₇n)