每日一题：36进制加法

2021年7月15日 下午

暂时只想到了暴力解决法，优化算法空了再思考思考。

"""

问题描述: 36进制由0-9，a-z，共36个字符表示, '0'-'9'对应十进制的0-9, 'a'-'z'对应十进制的10-35

例如: '1b' 换算成10进制等于 1 * 36^1 + 11 * 36^0 = 36 + 11 = 47

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

如: 按照加法规则，计算'1b' + '2x' = '48'

"""

"""
======================
-*- coding: utf-8 -*-
@author: Qiufen.Chen
@time: 2021/7/15:15:33
@email: [email protected]
@File: ascii_add.py
@Project: leetcode
======================
"""

def add_func(num1,num2):
    """
    :param num1: -->str
    :param num2: -->str
    :return: str(ans)
    """
    str_36 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b',
              'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
              'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    num1 = [x for x in reversed(list(num1))]
    num2 = [y for y in reversed(list(num2))]
    ans = 0
    sum_num1 = 0
    sum_num2 = 0
    for i in range(len(num1)):
        sum_num1 += str_36.index(num1[i])*(36**i)

    for j in range(len(num2)):
        sum_num2 += str_36.index(num2[j])*(36**j)

    ans = sum_num1 + sum_num2
    return str(ans)

num1 = '1bc'
num2 = '2x'
result = add_func(num1, num2)
print(result)
           

2021年7月15日 晚上 23:15

用上面的解法会产生越界的问题，比如一个很长的36进制数先转换成10进制的话，值特别大，所以为了避免这种问题，现在用按位相加的方法来做，和LeetCode第二题2. 两数相加 - 力扣（LeetCode） (leetcode-cn.com) 差不多。

def i2c(c):
    """
    :param c: 十进制的数
    :return: 返回36进制的数
    str_36 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b',
              'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
              'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    """
    return chr(c) if c < 10 else chr(ord('a') + c - 10)

def optimize_add_func(num1, num2):
    """
    :param num1: str
    :param num2: str
    :return: 36进制的ans
    """
    num1 = list(reversed(list(num1)))  # 反转num1
    num2 = list(reversed(list(num2)))  # 反转num2

    result = []  # 用来装每一次按位相加的结果
    tmp = 0   # 用tmp表示进位
    
    # zip_longest返回列表长度取决于最长的对象相同，缺失值的部分可以用fillvalue 参数来填充
    for i, j in itertools.zip_longest(range(len(num1)), range(len(num2)), fillvalue=-1):
        if i >= 0 and j >= 0: 
            cur_ans = int(num1[i], 36) + int(num2[j], 36) + tmp
        elif i >= 0:  # num1比num2长
            cur_ans = int(num1[i], 36)

        elif j >= 0:  # num2比num1长
            cur_ans = int(num2[j], 36)
        else:
            break

        result.append(i2c((cur_ans + tmp) % 36))  # 将余数存到result中
        tmp = (cur_ans + tmp) // 36  # 用商表示进位

    return "".join(list(reversed(result)))

a = 'abc'
b = 'bgf5'
print(optimize_add_func(a, b))