LeetCode 补充题 9. 36进制加法

Categories:

题目描述
思路分析
1. 解法一：模拟逐位相加（推荐）
相似题目

题目描述

✅ 补充题 9. 36进制加法

给定两个用 36 进制表示的非负整数字符串 num1 和 num2，返回它们之和的 36 进制字符串表示。

36 进制使用字符 '0'-'9' 表示数字 0–9，使用字符 'a'-'z' 表示数字 10–35。

思路分析

解法一：模拟逐位相加（推荐）

核心思路：

类比十进制字符串相加，从最低位（字符串末尾）向最高位逐位相加，维护进位 carry。

字符转数字：'0'-'9' 映射到 0–9，'a'-'z' 映射到 10–35。

数字转字符：0–9 映射回 '0'-'9'，10–35 映射回 'a'-'z'。

每一位的结果为 (d1 + d2 + carry) % 36，新进位为 (d1 + d2 + carry) / 36。

双指针分别从两个字符串末尾向前移动，结果逆序构建，最后翻转输出。

复杂度分析：

时间复杂度：O(max(m, n))，其中 m、n 分别为两个字符串的长度，需遍历所有位。

空间复杂度：O(max(m, n))，用于存储结果字符串。

class Solution {
    public String add36Strings(String num1, String num2) {
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry != 0) {
            // 取当前位的数值，指针已越界则取 0
            int d1 = i >= 0 ? charToDigit(num1.charAt(i--)) : 0;
            int d2 = j >= 0 ? charToDigit(num2.charAt(j--)) : 0;

            // 计算当前位之和
            int sum = d1 + d2 + carry;
            carry = sum / 36;

            // 将当前位转换为字符并追加到结果
            sb.append(digitToChar(sum % 36));
        }

        // 逆序得到最终结果
        return sb.reverse().toString();
    }

    /** 将 36 进制字符转换为对应整数值 */
    private int charToDigit(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        }
        return c - 'a' + 10;
    }

    /** 将整数值转换为对应的 36 进制字符 */
    private char digitToChar(int d) {
        if (d < 10) {
            return (char) ('0' + d);
        }
        return (char) ('a' + d - 10);
    }
}

func add36Strings(num1 string, num2 string) string {
    i, j := len(num1)-1, len(num2)-1
    carry := 0
    result := []byte{}

    for i >= 0 || j >= 0 || carry != 0 {
        d1, d2 := 0, 0

        // 取当前位的数值，指针已越界则取 0
        if i >= 0 {
            d1 = charToDigit(num1[i])
            i--
        }
        if j >= 0 {
            d2 = charToDigit(num2[j])
            j--
        }

        // 计算当前位之和
        sum := d1 + d2 + carry
        carry = sum / 36

        // 将当前位转换为字符并追加到结果
        result = append(result, digitToChar(sum%36))
    }

    // 逆序得到最终结果
    for lo, hi := 0, len(result)-1; lo < hi; lo, hi = lo+1, hi-1 {
        result[lo], result[hi] = result[hi], result[lo]
    }

    return string(result)
}

// charToDigit 将 36 进制字符转换为对应整数值
func charToDigit(c byte) int {
    if c >= '0' && c <= '9' {
        return int(c - '0')
    }
    return int(c-'a') + 10
}

// digitToChar 将整数值转换为对应的 36 进制字符
func digitToChar(d int) byte {
    if d < 10 {
        return byte('0' + d)
    }
    return byte('a' + d - 10)
}

相似题目

题目	难度	考察点
415. 字符串相加	简单	字符串 / 进位处理
67. 二进制求和	简单	字符串 / 二进制加法
2. 两数相加	中等	链表 / 进位处理
445. 两数相加 II	中等	链表 / 栈 + 进位
43. 字符串相乘	中等	字符串 / 逐位相乘
989. 数组形式的整数加法	简单	数组 / 进位处理

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/70208463