Leetcode 504.七进制数

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

示例 1:

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

示例 2:

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

我的答案：

一、信息

1.目的实现十进制向其他进制的转换。

2.原理：公式

3.一段运算过程

4.根据后面的一段话不难看出根据作者的意思就是用栈的数据结构来存储每次辗转相除后的余数然后输出

二、分析

问题出现

问题1：如何实现栈的构造。

问题2：然后如何把余数压入栈

问题3：如何把余数放出栈

我的答案：

为了实现这个功能，我们可以使用栈数据结构来帮助我们进行进制转换。以下是我们的思考和分析过程：

1. 检查特殊情况： 如果 num 是 0, 我们可以直接返回 "0"。
2. 处理符号： 如果 num 是负数，我们记下这个信息，并将 num 转化为正数进行处理。
3. 数字转换： 不断将 num 除以 7，并将余数放入栈中，直到 num 为 0。
4. 构建结果字符串： 然后我们可以从栈中取出元素（这将给我们一个反向的 7 进制表示）并构建结果字符串。如果最初的 num 是负数，我们在结果字符串前加上负号。

流程图： 

源代码：

C语言：

#include 
#include 
 
char* convertToBase7(int num) {
    if (num == 0) return "0";
 
    char *result = (char *)malloc(12); // sufficient size to store the result as string
    int index = 0;
    int is_negative = 0;
    if (num < 0) {
        is_negative = 1;
        num = -num;
    }
 
    int stack[10]; // stack to hold the digits
    int top = -1;
 
    while (num > 0) {
        stack[++top] = num % 7;
        num /= 7;
    }
 
    if (is_negative) {
        result[index++] = '-';
    }
 
    while (top >= 0) {
        result[index++] = '0' + stack[top--];
    }
 
    result[index] = '\0';
 
    return result;
}
 
int main() {
    printf("%s\n", convertToBase7(100)); // Output: "202"
    printf("%s\n", convertToBase7(-7));  // Output: "-10"
    return 0;
}

C++：

#include 
#include 
#include 
 
std::string convertToBase7(int num) {
    if (num == 0) return "0";
 
    std::stack<int> s;
    std::string result;
    bool is_negative = false;
 
    if (num < 0) {
        is_negative = true;
        num = -num;
    }
 
    while (num > 0) {
        s.push(num % 7);
        num /= 7;
    }
 
    if (is_negative) {
        result += '-';
    }
 
    while (!s.empty()) {
        result += '0' + s.top();
        s.pop();
    }
 
    return result;
}
 
int main() {
    std::cout << convertToBase7(100) << std::endl; // Output: "202"
    std::cout << convertToBase7(-7) << std::endl;  // Output: "-10"
    return 0;
}

 JAVA：

import java.util.Stack;
 
public class Main {
    public static String convertToBase7(int num) {
        if (num == 0) return "0";
 
        Stack stack = new Stack<>();
        StringBuilder result = new StringBuilder();
        boolean isNegative = false;
 
        if (num < 0) {
            isNegative = true;
            num = -num;
        }
 
        while (num > 0) {
            stack.push(num % 7);
            num /= 7;
        }
 
        if (isNegative) {
            result.append('-');
        }
 
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
 
        return result.toString();
    }
 
    public static void main(String[] args) {
        System.out.println(convertToBase7(100)); // Output: "202"
        System.out.println(convertToBase7(-7));  // Output: "-10"
    }
}

三者的区别： 

虽然这三种实现都使用了栈数据结构来实现整数到7进制的转换，但它们之间还是存在一些差别：

1. **语言特性和语法**：
   - **C**：需要手动管理内存分配和释放，并且使用字符数组来构建结果字符串。
   - **C++**：可以利用 STL 中的栈和字符串，它们有助于简化代码和减少错误。
   - **Java**：利用了 Java 的 Stack 类和 StringBuilder 类，Java 为内存管理提供了自动垃圾回收。

2. **内存分配**：
   - **C**：在堆上分配内存来存储结果字符串，并在最后添加了空字符（'\0'）来标记字符串的结束。
   - **C++**：使用了 std::string 类，它内部管理内存分配和释放。
   - **Java**：StringBuilder 类用来动态构建字符串，Java 虚拟机负责管理内存。

3. **错误处理和特殊情况的处理**：
   - 所有三种实现都检查了 `num` 是否为0的特殊情况，并对负数进行了处理。

4. **栈的使用**：
   - 在所有的实现中，我们都使用栈来存储7进制的数字，这样可以确保在构建结果字符串时，我们能够从最高位开始（因为栈是先入后出的数据结构）。

5. **代码的可读性和维护性**：
   - **C**：需要更多的代码来管理内存和数组索引。
   - **C++**：由于使用了 STL，代码比 C 更简洁和易读。
   - **Java**：由于使用了类和对象，代码是高度结构化和模块化的，易于读取和维护。

综上所述，虽然核心逻辑是相似的，但由于语言的特性和差异，每种实现都有其独特的方面和处理方式。

解决问题：

英雄师傅的答案：

英雄师傅的思路：

源代码：

char *convertToBase7(int num) {
    char *ret = (char *)malloc(sizeof(char) * 100); // 分配一个足够大的字符数组来存储结果
    int size = 0; // 用于跟踪结果字符串的当前长度
    int stk[50], top = 0; // 用于将数字的7进制表示反向存储在栈中
 
    if (num < 0) { // 如果输入的数字为负数
        num = -num; // 取其绝对值
        ret[size++] = '-'; // 在结果字符串中加入负号
    }
 
    if (num == 0) { // 如果输入的数字为0
        ret[size++] = '0'; // 直接将字符'0'存储在结果字符串中
    }
 
    while (num) { // 将数字的7进制表示逆序存储在栈中
        stk[top++] = num % 7; // 取余数并存储在栈中
        num /= 7; // 将数字除以7，以进行下一位的计算
    }
 
    while (top) { // 从栈中取出数字的7进制表示，并存储在结果字符串中
        ret[size++] = stk[--top] + '0'; // 逆序取出并转换为字符
    }
 
    ret[size] = '\0'; // 在结果字符串的最后添加终止符，以表示字符串的结束
 
    return ret; // 返回存储7进制表示的字符串
}

Leetcode题解：

C语言： 

char * convertToBase7(int num){
    if (num == 0) {
        return "0";
    }
    bool negative = num < 0;
    num = abs(num);
    char * digits = (char *)malloc(sizeof(char) * 32);
    int pos = 0;
    while (num > 0) {
        digits[pos++] = num % 7 + '0';
        num /= 7;
    }
    if (negative) {
        digits[pos++] = '-';
    }
    for (int l = 0, r = pos - 1; l < r; l++, r--) {
        char c = digits[l];
        digits[l] = digits[r];
        digits[r] = c;
    }
    digits[pos] = '\0';
    return digits;
}
 

C++：

class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        bool negative = num < 0;
        num = abs(num);
        string digits;
        while (num > 0) {
            digits.push_back(num % 7 + '0');
            num /= 7;
        }
        if (negative) {
            digits.push_back('-');
        }
        reverse(digits.begin(), digits.end());
        return digits;
    }
};
 

JAVA：

class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean negative = num < 0;
        num = Math.abs(num);
        StringBuffer digits = new StringBuffer();
        while (num > 0) {
            digits.append(num % 7);
            num /= 7;
        }
        if (negative) {
            digits.append('-');
        }
        return digits.reverse().toString();
    }
}
 

总结：

两种方式的比较：

使用栈存储和Leetcode提供的方法（字符串拼接+反转）在实现上有一些区别。让我们逐一探讨这两种方法的优缺点：

### 1. 使用栈存储方法

#### 优点：
1. **自然的顺序**：栈是一种后进先出（LIFO）的数据结构，它可以自然地按照从高位到低位的顺序存储七进制的数字。
2. **无需字符串反转**：由于栈的性质，我们可以按照高位到低位的顺序提取数字，避免了字符串反转这一步骤。
3. **代码可读性**：使用栈可以使代码具有更好的结构和可读性，特别是对于初学者来说，可以更清晰地展示算法的逻辑。

#### 缺点：
1. **额外的空间**：使用栈意味着我们需要额外的空间来存储数据。
2. **可能的额外时间开销**：栈操作（压栈和弹栈）可能会增加一些时间开销。

### 2. Leetcode提供的方法（字符串拼接+反转）

#### 优点：
1. **空间效率**：直接使用字符串进行操作，避免了使用额外数据结构导致的空间开销。
2. **简洁性**：代码相对简洁，尤其是在处理字符串拼接和反转的编程语言中。

#### 缺点：
1. **需要字符串反转**：由于从低位开始构建结果字符串，因此需要在最后执行一次字符串反转操作，增加了一些时间复杂度。
2. **代码可读性**：虽然代码较为简洁，但对于初学者来说，理解代码的逻辑可能需要更多时间。

### 总结：
- **栈存储方法**更适用于想要清晰展示算法逻辑的场合，它可以更自然地表达算法中的步骤，但可能会带来一些额外的时间和空间开销。
- **Leetcode的方法**则更为简洁和高效，尤其是在字符串操作相对便捷的编程语言中，但可能需要更多的时间来理解和分析代码的逻辑。

从这道题目中我们能学到什么？

这道题目可以帮助我们学到以下几点：

1. **基本数学知识**：它强调了我们对数字进制转换的理解，特别是如何从十进制转换为其他进制。这是计算机科学中一个非常基本但重要的概念。

2. **算法设计和实现**：通过设计算法来解决这个问题，我们可以学习如何将抽象的数学问题转化为具体的算法和代码实现。

3. **条件处理**：本题目涉及正数和负数的处理，这能帮助我们理解如何在算法中处理不同的条件和边界情况。

4. **数据结构的应用**：如果我们选择用栈来解决这个问题，我们可以学到如何在实际问题中使用栈这一数据结构。同时，通过比较栈和字符串拼接方法，我们可以学习如何根据特定问题选择合适的数据结构。

5. **代码优化**：通过比较不同的解决方案（如使用栈与直接使用字符串），我们可以学习如何分析和比较不同方法的时间和空间复杂度，从而进行代码优化。

6. **问题分析和解决策略**：我们可以学习如何分析问题，确定解决策略，然后逐步实现。例如，在这个问题中，我们首先需要分析如何从数学的角度解决问题，然后再将解决方案转换为代码。

7. **代码的可读性和简洁性**：我们可以学习如何编写简洁而可读的代码，以便于其他人（或未来的我们）理解和维护代码。

8. **实际应用**：在计算机科学中，进制转换是一个常见的操作。通过学习如何实现这样的转换，我们可以更好地理解和应用这一概念于实际情境中。

总的来说，这道题目可以作为一个很好的练习来提升我们的编程技能和算法设计能力。