504. 七进制数

题目描述

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

示例 1:

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

示例 2:

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

提示：

-10⁷ <= num <= 10⁷

解法

方法一：模拟

思考

七进制转换就是反复除 \(7\) 取余。负数可先转绝对值再补符号；\(0\) 单独返回。余数序列是低位在前，拼接前需要反转。

除法次数与位数成正比，位数为 \(O(\log |num|)\)，远小于任何更重的字符串模拟。

我们不妨假设 num 大于等于 \(0\)，那么，如果 num 等于 \(0\)，只需要返回 \(0\) 即可。否则，我们将 \(num\) 模 \(7\) 的结果保存起来，最后逆序拼接成字符串即可。

时间复杂度 \(O(\log n)\)，忽略答案的空间消耗，空间复杂度 \(O(1)\)。其中 \(n\) 是 num 的绝对值大小。

Python3JavaC++GoTypeScriptRust

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return '0'
        if num < 0:
            return '-' + self.convertToBase7(-num)
        ans = []
        while num:
            ans.append(str(num % 7))
            num //= 7
        return ''.join(ans[::-1])

class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        if (num < 0) {
            return "-" + convertToBase7(-num);
        }
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(num % 7);
            num /= 7;
        }
        return sb.reverse().toString();
    }
}

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

func convertToBase7(num int) string {
    if num == 0 {
        return "0"
    }
    if num < 0 {
        return "-" + convertToBase7(-num)
    }
    ans := []byte{}
    for num != 0 {
        ans = append([]byte{'0' + byte(num%7)}, ans...)
        num /= 7
    }
    return string(ans)
}

function convertToBase7(num: number): string {
    if (num == 0) {
        return '0';
    }
    let res = '';
    const isMinus = num < 0;
    if (isMinus) {
        num = -num;
    }
    while (num != 0) {
        const r = num % 7;
        res = r + res;
        num = (num - r) / 7;
    }
    return isMinus ? '-' + res : res;
}

impl Solution {
    pub fn convert_to_base7(mut num: i32) -> String {
        if num == 0 {
            return String::from("0");
        }
        let mut res = String::new();
        let is_minus = num < 0;
        if is_minus {
            num = -num;
        }
        while num != 0 {
            res.push_str((num % 7).to_string().as_str());
            num /= 7;
        }
        if is_minus {
            res.push('-');
        }
        res.chars().rev().collect()
    }
}

504. 七进制数

题目描述

解法

方法一：模拟

评论