Easy

题目描述

给你一个十进制数 n 和一个进制 k，请你将 n 从十进制转换为 k 进制，并求转换后各位数字的和。

转换后，每一位数字都应当视作十进制数字，求和结果也应当按十进制返回。

示例 1：

输入：n = 34, k = 6
输出：9
解释：34（十进制）在六进制下是 54。5 + 4 = 9

示例 2：

输入：n = 10, k = 10
输出：1
解释：n 本身就是十进制的。1 + 0 = 1

提示：

  • 1 <= n <= 100
  • 2 <= k <= 10

解题思路

解题思路

这道题要求我们将十进制数 n 转换为 k 进制，然后计算转换后各位数字的和。

核心思路：进制转换

要将十进制数转换为 k 进制，我们使用经典的取余法：

  1. 用 n 除以 k，得到商和余数
  2. 余数就是 k 进制表示中的最低位数字
  3. 用商替换 n，重复上述过程，直到 n 为 0
  4. 将得到的所有余数相加即为答案

算法步骤：

  1. 初始化结果 sum = 0
  2. 当 n > 0 时：
    • 计算 n % k，这是当前最低位的数字
    • 将该数字加到 sum 中
    • 更新 n = n / k（整除）
  3. 返回 sum

这种方法的优势在于我们不需要真正构造出 k 进制的字符串表示，而是直接在转换过程中累加各位数字，既节省空间又简化逻辑。

时间复杂度为 O(log_k n)，因为需要 log_k n 次除法操作。空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int sumBase(int n, int k) {
        int sum = 0;
        while (n > 0) {
            sum += n % k;
            n /= k;
        }
        return sum;
    }
};

class Solution:
    def sumBase(self, n: int, k: int) -> int:
        sum_digits = 0
        while n > 0:
            sum_digits += n % k
            n //= k
        return sum_digits

public class Solution {
    public int SumBase(int n, int k) {
        int sum = 0;
        while (n > 0) {
            sum += n % k;
            n /= k;
        }
        return sum;
    }
}

var sumBase = function(n, k) {
    let sum = 0;
    while (n > 0) {
        sum += n % k;
        n = Math.floor(n / k);
    }
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log_k n)需要进行 log_k n 次除法运算
空间复杂度O(1)只使用常数额外空间

相关题目