LeetCode算法题-Base 7（Java实现）

印度阿三17 2019-02-12

展开全文

这是悦乐书的第247次更新，第260篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第114题（顺位题号是504）。给定一个整数，返回其基数为7的字符串表示。例如：

输入：100

输出：“202”

输入：-7

输出：“-10”

注意：输入范围为[-1e7,1e7]。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

直接使用包装类Integer的toString(arg, arg2)方法，将arg转为对应arg2进制的字符串。

public String convertToBase7(int num) {
    return Integer.toString(num, 7);
}

03 第二种解法

利用迭代的思路来正常解。

特殊情况：当num为0的时候，直接返回字符串0。

正常情况：如果num为负数，先将其转为正数，并做一个标记。为了将num转为7进制的字符串，肯定离不开取余和除法。

我们先来看看题目所给示例100，其7进制数为202，可以将其拆分为2x7x7 0x7 2，从后往前看，最后一位是将100对7取余，余数为2，再将其除以7，因为已经计算了一位，得到14，14再对7取余，余数为0，再将其除以7，得到商为2，2再对7取余，余数为2,2再除以7，商为0，循环结束。

所以，思路就是取余后，再除以7，直到num等于0，如果有负号，最后在补上去。

public String convertToBase7_2(int num) {
    if (num == 0) {
        return "0";
    }
    StringBuilder sb = new StringBuilder();
    boolean flag = false;
    if (num < 0) {
        flag = true;
    }
    num = Math.abs(num);
    while (num != 0) {
        sb.append(num%7);
        num /= 7;
    }
    if (flag) {
        sb.append("-");
    }
    return sb.reverse().toString();
}

04 第三种解法

利用递归的思路。

第二种解法是利用迭代，我们也可以利用递归的方法。如果num为负数，先将其转为正数再参与计算，如果num小于7，直接返回以num为值的字符串，然后调用自身，新参数为num除以7，并且要连接上num对7取余的余数。

public String convertToBase7_3(int num) {
    if (num < 0) {
        return "-"   convertToBase7_3(-num);
    }
    if (num < 7) {
        return num   "";
    }
    return convertToBase7_3(num/7)   num%7;
}