504.七进制数

LeetCode LeetCode 数学

发布时间 : 2000-01-10 05:00

字数:1.2k 阅读 :

评论:

504.七进制数

504.七进制数

504.1 题目

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

示例 1:

输入: num = 100
输出: "202"

示例 2:

输入: num = -7
输出: "-10"

提示：

-10^7 <= num <= 10^7

504.2 题解

方法一：递归法

思路

递归终止条件：当 num 的绝对值小于 7 时，直接返回其字符串形式。递归调用：将商部分递归转换为 7 进制，再拼接余数。负数处理：递归过程中使用 Math.Abs 处理余数。

核心思想：递归处理商，拼接余数。

具体步骤：

如果 |num| < 7：返回 num.ToString()
否则：返回 ConvertToBase7(num / 7) + |num % 7|

举例：对于 num = 100：

100 >= 7：递归 ConvertToBase7(14) + "2"
14 >= 7：递归 ConvertToBase7(2) + "0"
2 < 7：返回 "2"
回溯："2" + "0" = "20"，"20" + "2" = "202"
结果："202"

复杂度分析

时间复杂度：O(log₇|num|)，递归深度为转换后的位数。
空间复杂度：O(log₇|num|)，递归调用栈。

代码

// 方法一：递归法
// 取余再递归传入除7的值
static string ConvertToBase71(int num)
{
    // 递归基，当 num 的绝对值小于 7 时，返回其字符串形式
    if (Math.Abs(num) < 7)
    {
        return num.ToString();
    }

    // 递归调用，将商部分递归转化为 7 进制，并将余数添加到字符串中
    return ConvertToBase71(num / 7) + Math.Abs(num % 7).ToString();
}

方法二：迭代法

思路

特殊情况：num == 0 时直接返回 “0”。处理负数：记录符号，取绝对值处理。循环计算：每次取余数，插入到结果字符串开头，然后除以 7。最后添加负号（如果是负数）。

核心思想：循环取余，逆序拼接。

具体步骤：

如果 num == 0：返回 "0"
记录符号，取绝对值
循环：num > 0 时，取余数插入结果开头，num /= 7
如果是负数，添加负号

举例：对于 num = -7：

isNegative = true，num = 7
7 % 7 = 0，结果 "0"，num = 1
1 % 7 = 1，结果 "10"，num = 0
添加负号："-10"

复杂度分析

时间复杂度：O(log₇|num|)，循环次数为转换后的位数。
空间复杂度：O(log₇|num|)，存储结果字符串。

代码

// 方法二：迭代法
// 循环计算商和余数，将余数添加到 StringBuilder 中
static string ConvertToBase72(int num)
{
    // 处理特殊情况，当 num 为 0 时直接返回 "0"
    if (num == 0)
    {
        return "0";
    }

    // 使用 StringBuilder 存储结果
    System.Text.StringBuilder result = new System.Text.StringBuilder();

    // 处理负数情况，添加负号并取绝对值
    bool isNegative = num < 0;
    if (isNegative)
    {
        num = Math.Abs(num);
    }

    // 迭代计算商和余数，将余数添加到 StringBuilder 中
    while (num > 0)
    {
        int remainder = num % 7;
        result.Insert(0, remainder.ToString()); // 在 StringBuilder 的开头插入余数
        num /= 7;
    }

    // 如果是负数，插入负号
    if (isNegative)
    {
        result.Insert(0, "-");
    }

    return result.ToString();
}

504.3 代码

using System;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。
        // 示例 1:
        // 输入: num = 100
        // 输出: "202"
        // 示例 2:
        // 输入: num = -7
        // 输出: "-10"
        // 提示：-107 <= num <= 107

        #endregion

        #region 测试

        // 示例 1
        int num1 = 100;
        string result1_1 = ConvertToBase71(num1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        string result1_2 = ConvertToBase72(num1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int num2 = -7;
        string result2_1 = ConvertToBase71(num2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        string result2_2 = ConvertToBase72(num2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归法
    // 取余再递归传入除7的值
    static string ConvertToBase71(int num)
    {
        // 递归基，当 num 的绝对值小于 7 时，返回其字符串形式
        if (Math.Abs(num) < 7)
        {
            return num.ToString();
        }

        // 递归调用，将商部分递归转化为 7 进制，并将余数添加到字符串中
        return ConvertToBase71(num / 7) + Math.Abs(num % 7).ToString();
    }

    // 方法二：迭代法
    // 循环计算商和余数，将余数添加到 StringBuilder 中
    static string ConvertToBase72(int num)
    {
        // 处理特殊情况，当 num 为 0 时直接返回 "0"
        if (num == 0)
        {
            return "0";
        }

        // 使用 StringBuilder 存储结果
        System.Text.StringBuilder result = new System.Text.StringBuilder();

        // 处理负数情况，添加负号并取绝对值
        bool isNegative = num < 0;
        if (isNegative)
        {
            num = Math.Abs(num);
        }

        // 迭代计算商和余数，将余数添加到 StringBuilder 中
        while (num > 0)
        {
            int remainder = num % 7;
            result.Insert(0, remainder.ToString()); // 在 StringBuilder 的开头插入余数
            num /= 7;
        }

        // 如果是负数，插入负号
        if (isNegative)
        {
            result.Insert(0, "-");
        }

        return result.ToString();
    }

    #endregion
}

504.4 运行结果

示例1 方法1 输出：202
示例1 方法2 输出：202
示例2 方法1 输出：-10
示例2 方法2 输出：-10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com