0504. Base 7

题目信息

题号:

0504

难度:

Easy

主题:

整数表示、七进制、负号、字符串输出

原题:

LeetCode 0504

重点:

返回十进制整数的七进制字符串、负数保留负号、零单独表示、结果无前导零

题目重述

给定一个十进制整数 num,返回它的七进制字符串表示。正数和零按普通进制转换;负数的结果以 - 开头,其余部分表示绝对值。

num 位于 [-10^7, 10^7]。零必须返回 "0";其他结果除负号外不能包含前导零,数字字符只能来自 0 到 6。

自建示例

正数包含多个七进制位:

输入:num = 100
输出:"202"
解释:100 = 2 * 49 + 0 * 7 + 2,因此七进制表示为 202。

负数保留符号:

输入:num = -49
输出:"-100"
解释:49 等于 7 的平方,绝对值的七进制表示为 100,再在前面添加负号。

反复取七进制最低位

除以 7 的余数是当前最低位,商继续提供更高位;反复执行直到商为 0,再把得到的余数序列反转。负数先记录符号并对绝对值进行转换,最后把负号加回;使用 long long 取得绝对值时不会触及有符号最小值的边界。

C++ 实现

class Solution {
public:
    std::string convertToBase7(int num) {
        if (num == 0) return "0";
        bool negative = num < 0;
        long long value = std::llabs(static_cast<long long>(num));
        std::string result;
        while (value > 0) {
            result.push_back(static_cast<char>('0' + value % 7));
            value /= 7;
        }
        if (negative) result.push_back('-');
        std::reverse(result.begin(), result.end());
        return result;
    }
};

代码分析

每次除法都确定一个不会再变化的低位,反转后得到从高位到低位的标准表示;零单独返回避免产生空字符串。设结果有 d 位,时间复杂度为 O(d),额外空间复杂度为 ``O(d)``(不计返回字符串)。