前言

大家好，我是 PakJeon.

这次看看某厂前端面试的一道算法题，实现一个 62 进制加法。

什么是进制

1. 进制： 进制是一种表示数字的方式，它是一个基数系统。我们常用的是十进制，但还有其他进制，比如二进制、八进制、十六进制等。进制的概念是基于不同的基数，表示数字的方法也不同。
2. 十进制： 十进制是我们平时使用的数字系统，它是基于10的进制。它包括0、1、2、3、4、5、6、7、8、9这十个数字。例如，数字 356 表示为：3×10²+5×10¹+6×10º。
3. 二进制： 二进制是一种基于2的进制，它只包括两个数字：0和1。在二进制中，每一位的权重是2的幂次方。例如，数字 101 表示为：1×2²+0×2¹+1×2º=5。
4. 62进制： 62进制是一种基于62的进制，它使用0-9、a-z、A-Z这62个字符来表示数字。在62进制中，每一位的权重是62的幂次方。例如，数字 "b3" 表示为：11×62¹+3×62º=731。

十进制相加

先看一个基础版的题目。

给定两个字符串形式的非负整数 `num1` 和`num2` ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 `BigInteger`）， 也不能直接将输入的字符串转换为整数形式。

示例 1：
输入： num1 = "11", num2 = "123"
输出： "134"

示例 2：
输入： num1 = "456", num2 = "77"
输出： "533"

示例 3：
输入： num1 = "0", num2 = "0"
输出： "0"

思路：模拟计算

1. 设定i，j两指针分别指向num1，num2尾部，模拟人工加法；
2. 设定carry变量保存上一位计算的进位；
3. 从尾部开始遍历到头部，指针溢出时替换成0，并每次更新carry和结果字符串

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function(num1, num2) {
    var i = num1.length - 1;
    var j = num2.length - 1;
    var carry = 0;  // 保存进位
    var res = '';  // 保存结果
    while (i >= 0 || j >= 0 || carry) { // 注意：循环条件多加一个是否有进位的判断，方便最后一位进位后的处理
        // 取出每位数字，索引溢出时赋值 0
        var x = i >= 0 ? nums[i] - '0' : 0;
        var y = j >= 0 ? nums[j] - '0' : 0;
        // 计算每位相加结果，注意要加上进位
        var sum = x + y + carry;
        // 更新结果
        res = `${sum % 10}${res}`
        // 更新进位
        carry = Math.floor(sum / 10);
        // 指针前移
        i--;
        j--;
    }
    return res;
};
    

62进制相加

有了上述基础版的框架，这个62进制相加就只是多了一个进制转换的过程。来看题目。

62进制由0-9，a-z，A-Z 共62个字符表示。

要求按照加法规则计算出任意两个62进制正整数的和

示例 1：
输入： num1 = "1A", num2 = "2"
输出： "1C"

示例 2：
输入： num1 = "1A", num2 = "b2"
输出： "cC"

方法一：利用 ASCII 码作转换

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addBase62 = function(num1, num2) {
    var i = num1.length - 1;
    var j = num2.length - 1;
    var carry = 0;
    var res = '';

    // 从右往左逐位相加
    while (i >= 0 || j >= 0 || carry) {
        var ci = i >= 0 ? num1.charCodeAt(i) : '0'.charCodeAt(0);
        var cj = j >= 0 ? num2.charCodeAt(j) : '0'.charCodeAt(0);
        
        // 将 ASCII 值转换为十进制值
        ci = ci - '0'.charCodeAt(0);
        cj = cj - '0'.charCodeAt(0);

        // 计算每位相加结果，注意要加上进位
        var sum = ci + cj + carry;

        // 更新进位
        carry = Math.floor(sum / 62);

        // 更新结果字符串(String.fromCharCode 把 ASCII 码值转成对应字符)
        res = String.fromCharCode('0'.charCodeAt(0) + sum % 62) + res;
        i--;
        j--;
    }
    return res;
};

// 示例
const result = addBase62("1A", "2");
console.log(result);  // 输出："1C"

方法二：巧用字符串下标做转换 😅

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addBase62 = function(num1, num2) {
    var i = num1.length - 1;
    var j = num2.length - 1;
    var carry = 0;
    var res = '';
    // 😅😅😅
    const characters = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const base = characters.length;

    // 从右往左逐位相加
    while (i >= 0 || j >= 0 || carry) {
        var ci = i >= 0 ? characters.indexOf(num1[i]) : 0;
        var cj = j >= 0 ? characters.indexOf(num2[j]) : 0;
        var sum = ci + cj + carry;

        // 更新进位
        carry = Math.floor(sum / base);

        // 更新结果字符串
        res = `${characters[sum % base]}${res}`;
        i--;
        j--;
    }
    return res;
};

// 示例
const result = addBase62("1A", "b2");
console.log(result);  // 输出："cC"

小结

先掌握十进制字符串相加的模拟加法框架，再应对诸如36进制相加、62进制相加时便能在既有框架下实现。

扩展：62进制的使用场景

URL短缩服务： 类似于短链接生成，一些URL短缩服务可以使用62进制来生成短链接，以便更好地处理大量的唯一标识符。

更多文章