题目地址

5738. K 进制表示下的各位数字总和

题目描述

给你一个整数 n（10 进制）和一个基数 k ，请你将 n 从 10 进制表示转换为 k 进制表示，计算并返回转换后各位数字的 总和 。

转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 · 进制表示返回。

  • 示例 1： 
输入：n = 34, k = 6
输出：9
解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
  • 示例 2： 
输入：n = 10, k = 10
输出：1
解释：n 本身就是 10 进制。 1 + 0 = 1 。

提示：

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

思路

  1. 先将非负的十进制整数转换成k进制数，且返回类型为String；

由于十六进制会带ABCDEF等后缀，故返回的是String类型

  1. 进制转换常用的是除二取余法，

  2. 将String类型的k进制数转成字符数组，再进行累加计算（需要-48）即可；

注意的是，这里字符数组中的数字是以ASCII的形式进行存储，例如0的ASCII值是48，1的ASCII值是49……因此在每次计算时都需要-48。当然有其他方法均可。

关键点

  • 十进制转换成k进制：除二取余法
  • 这里使用递归的方式来实现，递归公式如下：

image.png

  • 递归栈，如下图：

image.png

代码

image.png

class Solution {
    /**
     * 计算每个数字，各个数位的求和
     * @param n 非负十进制整数
     * @param k 进制
     * @return sum 各个数位的求和
     */
    public static int sumBase(int n, int k) {
        int sum = 0;
        // int ik =  Integer.valueOf(binary(n, k));
        // System.out.println(binary(n, k));
        char[] chs = binary(n, k).toCharArray();
        for (int i = 0; i < chs.length; i++) {
            // System.out.println(Integer.valueOf(chs[i])-48);
            sum += Integer.valueOf(chs[i]-48); //0的ASCII值是48
        }
        return sum;
    }

    /**
     * 除二取余法
     * 非负十进制整数n转换成k进制，其中2<=k<=16
     * 递归：
     * fun(n) = n, n<=k
     *           = n%k + fun(n/k), k<n<=16
     * @param n 非负十进制整数
     * @param k 进制
     * @return String 由于像16进制会带ABCDEF等后缀
     */
    public static String binary(int n,int k) {
        if(n<k) {
            if(n<10)    return String.valueOf(n);    
            else if(10==n)    return "A";
            else if(11==n)    return "B";
            else if(12==n)    return "C";
            else if(13==n)    return "D";
            else if(14==n)    return "E";
            else    return "F";    
        } else {
            if((n%k)<10)
                return binary(n/k,k).concat(String.valueOf(n%k));
            if((n%k)==10)
                return binary(n/k,k).concat("A");
            else if((n%k)==11)
                return binary(n/k,k).concat("B");
            else if((n%k)==12)
                return binary(n/k,k).concat("C");
            else if((n%k)==13)
                return binary(n/k,k).concat("D");
            else if((n%k)==14)
                return binary(n/k,k).concat("E");
            else 
                return binary(n/k,k).concat("F");
        }
    }

    public static void main(String[] args) {
        System.out.println(sumBase(34, 6));
    }
}