LeetCode504-Base 7

题目

Given an integer, return its base 7 string representation.

Example1:

Input: 100
Output: "202"

Example2:

Input: -7
Output: "-10"

分析

题意很明确,就是求一个10进制数的7进制表示,只不过需要注意最后返回的是字符串,且数字可能是负数(如果是负数,先将其取相反数变为正数,然后强制在字符串首部添加’ – ‘即可)。解法是典型的教科书方法:模7取余,最先得到的余数位于7进制串最低位。只不过在实现的时候我们可以采用两种解法完成,一种是递推方法,一种是递归方法。

解法一:递推法

利用while循环递推地求得下一轮的被除数和余数,余数同步追加到结果字符串首部,直到被除数为0时停止计算。

解法二:递归法

从递推解法其实都可以看出递归的痕迹,最初的复杂问题,其实是被一层一层地化为简单的子问题解决的:即convertToBase7(num)是求解出num的7进制串,那么我只需设法求出convertToBase7(num / 7)的7进制串以后再在尾部追加一个前面求到的余数,即可递归表示出上一步的大问题的解,而递归需要出口,什么时候停止?那就是在被除数为0的时候亦即num < 7的时候停止。

代码

解法一

public class Solution {
    public String convertToBase7(int num) {

        if (num == 0) return "0";

        String res = "";
        int bedivided = num < 0 ? -num : num;
        int left = 0;
        while (bedivided != 0) {
            left = bedivided % 7;
            bedivided /= 7;
            res = Integer.toString(left) + res;
        }
        
        return num < 0 ? "-" + res : res;
    }
}

解法二

public class Solution {
    public String convertToBase7(int num) {

        if (num < 0)
            return '-' + convertToBase7(-num);
        if (num < 7)
            return num + "";
        
        return convertToBase7(num / 7) + num % 7;
    }
}

Leave a Comment.