0504. 七进制数

题目地址(504. 七进制数)

https://leetcode-cn.com/problems/base-7/

题目描述

1
给定一个整数,将其转化为7进制,并以字符串形式输出。
2
3
示例 1:
4
5
输入: 100
6
输出: "202"
7
8
9
示例 2:
10
11
输入: -7
12
输出: "-10"
13
14
15
注意: 输入范围是 [-1e7, 1e7] 。
Copied!

前置知识

公司

  • 暂无

思路

这道题很经典也很重要。 如果你把这道题搞懂了,那么所有的进制转化题目对你来说都不是问题。 另外有的题目虽然不是直接让你进制转化,不过使用进制转化却实实在在可以优化代码。
10 进制转化任意进制的思路都是除 x 取余,其中 x 为进制数,比如 2 进制就是 除 2 取余,7 进制就是除 7 取余。这个大家可能都知道,这里再带大家回顾一下。
比如一个数 4321 ,需要转化为 7 进制。那么可以:
  • 先将 4321 除以 7,其中余数为 0 , 除数为 616
  • 继续将 616 采用同样的方法直到小于 7
将此过冲的余数反序就是答案了。图解:
(图片来自网络)
如图,4312 的 7 进制就是 15400。

关键点

  • 除 x 取余,并逆序输出

代码

  • 语言支持:Python3
Python3 Code:
递归:
1
class Solution:
2
def convertToBase7(self, num: int) -> str:
3
if num < 0:
4
return "-" + self.convertToBase7(-num)
5
if num < 7:
6
return str(num)
7
return self.convertToBase7(num // 7) + str(num % 7)
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(h)$,其中 h 为递归栈的深度。
迭代:
1
class Solution:
2
def convertToBase7(self, num: int) -> str:
3
if num == 0:
4
return "0"
5
ans = []
6
is_negative = num < 0
7
num = abs(num)
8
while num > 0:
9
num, remain = num // 7, num % 7
10
ans.append(str(remain))
11
12
return "-" + "".join(ans[::-1]) if is_negative else "".join(ans[::-1])
Copied!
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。