讨论/技术交流/分享|力扣找不到的字节面试题——36进制加法/
分享|力扣找不到的字节面试题——36进制加法

前言

今天为大家补充的是36进制加法,这也是一道力扣找不到的题目。

先引用几篇面经原文

实现36进制加法0-9,a-z,例如1+a=b,1z+1=20 ——字节跳动-后端-3面
36位加法——字节跳动-教育-后端-三面
36进制加法——抖音-客户端-三面

这道题常出现在字节跳动的三面,涉及教育,抖音等部门!

不过,在其他部门的面试也曾出现过,如data数据平台一面,教育前端二面

话不多说,我们赶紧一起学习一下这道题吧~

题目描述

36进制由0-9,a-z,共36个字符表示。

要求按照加法规则计算出任意两个36进制正整数的和,如1b + 2x = 48 (解释:47+105=152)

要求:不允许使用先将36进制数字整体转为10进制,相加后再转回为36进制的做法

题目分析

此题难度倒不是很大,实际上是415. 字符串相加的扩展。

LC415是十进制的大数相加,而本题是36进制的大数相加。

顺便提一嘴,我强烈推荐415题使用以下代码的写法,优雅简洁,不容易出Bug。

string addStrings(string num1, string num2)
{
    int carry = 0;
    int i = num1.size() - 1, j = num2.size() - 1;
    string res;
    while (i >= 0 || j >= 0 || carry)
    {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        int temp = x + y + carry;
        res += '0' + temp % 10;
        carry = temp / 10;
        i--, j--;
    }
    reverse(res.begin(), res.end());
    return res;
}

若掌握了415,那本题只需要注意将10变成36,以及36进制字符与数值的转换。这里,我使用了getChar(int n)getInt(char ch)两个辅助函数来完成36进制字符与数值的转换。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
    char getChar(int n) {
        if(n <= 9) return n + '0';
        else return n - 10 + 'a'; 
    }
    int getInt(char ch) {
        if('0' <= ch && ch <='9') return ch - '0';
        else return ch - 'a' + 10;
    }
    string add36Strings(string num1, string num2) {
        int carry = 0;
        int i = num1.size()-1, j = num2.size()-1;
        string res;
        while(i >= 0 || j >= 0 || carry) {
            int x = i >= 0 ? getInt(num1[i]) : 0;
            int y = j >= 0 ? getInt(num2[j]) : 0;
            int temp = x + y + carry;
            res += getChar(temp % 36);
            carry = temp / 36;
            i -- , j --;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

int main() {
    Solution s;
    string a = "1b", b = "2x", c;
    c = s.add36Strings(a,b);
    cout << c << endl;
}
37
共 4 个回复

ASCII码的差值。'a'~'z'通过计算ch - 'a' + 10便对应10~35

1

感谢分享

1

ch - 'a' 是什么意思呢? 是指 a 到另外一个字母的距离吗?

感谢