标签: 数学
难度: Easy
给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
示例 1:
输入: num = 100 输出: "202"
示例 2:
输入: num = -7 输出: "-10"
提示：
-107 <= num <= 107
Submission
运行时间: 18 ms
内存: 16.1 MB
class Solution:
def convertToBase7(self, num: int) -> str:
if num == 0:
return "0"
negative = num < 0
num = abs(num)
digits = []
while num:
digits.append(str(num % 7))
num //= 7
if negative:
digits.append('-')
return ''.join(reversed(digits))
Explain
这个题解使用了模拟七进制转换的方法。具体思路如下： 1. 如果输入的数是0，直接返回"0"字符串。 2. 判断输入的数是否为负数，如果是负数，记录下负号，并取数的绝对值。 3. 创建一个空列表digits，用于存储转换后的每一位数字。 4. 当num大于0时，循环执行以下操作： - 将num除以7的余数转换为字符串，添加到digits列表的末尾。 - 将num整除7，更新num的值。 5. 如果原始输入为负数，在digits列表的末尾添加负号'-'。 6. 将digits列表反转，然后拼接成一个字符串作为最终结果返回。
时间复杂度: O(log_7(n))
空间复杂度: O(log_7(n))
class Solution:
def convertToBase7(self, num: int) -> str:
if num == 0:
return "0"
negative = num < 0
num = abs(num)
digits = []
while num:
# 将num除以7的余数转换为字符串，添加到digits列表的末尾
digits.append(str(num % 7))
# 将num整除7，更新num的值
num //= 7
if negative:
# 如果原始输入为负数，在digits列表的末尾添加负号'-'
digits.append('-')
# 将digits列表反转，然后拼接成一个字符串作为最终结果返回
return ''.join(reversed(digits))
Explore
处理num的绝对值是为了简化七进制转换的过程。当直接处理负数时，计算余数和商可能会涉及到负数的处理，这会使算法更复杂，因为负数的余数可能引起混淆（比如Python中-1 % 7的结果是6）。使用绝对值可以保持所有操作在非负整数范围内，从而简化算法的逻辑。在转换完成后，可以根据原始数的正负来决定是否添加负号。
在算法中将余数转换为字符串后存储的主要原因是为了方便最后的输出格式。因为最终的输出需要是一个字符串形式的七进制数，如果在处理时就直接存储为字符串，那么在最后生成结果时只需对字符串列表进行反转和拼接即可，这样可以避免在输出阶段还需额外的类型转换步骤。
在循环中先计算数字的低位，因此digits列表实际上是数字从低位到高位的逆序。如果在列表构建过程中就将负号添加在开始，那么在最后反转列表时，负号会被移到末尾，不符合数的标准表达。因此，先将负号添加到digits列表的末尾，再进行整个列表的反转，这样可以确保负号正确地出现在最终字符串的首位。
虽然理论上可以在构造digits列表时直接以正确的顺序（从高位到低位）添加元素，但这通常需要每次插入时都将元素添加到列表的开始位置，这样的操作在列表中是效率较低的，因为每次插入都可能涉及到元素的移动。相比之下，将元素添加到列表末尾是一个时间复杂度为O(1)的操作，更加高效。因此，通常选择先以逆序添加元素，再进行一次列表反转，这样整体效率更高。