leetcode43：字符串相乘

思路：显然，并不能进行return str(int(num1)*int(num2))这样的sao操作。
可以模拟乘法的运算过程，即写竖式
对于num1某下标i的数和num2下标为j的数，他们俩相乘的结果对乘积的i+j和i+j+1两个位置（从乘积的高位起为0），例子如下：


从图中可以看出，num1第1位置的2和num2第0位置的4相乘为08.，影响最终结果的第1和第2位，则把结果累加到这两位即可。注意累加的时候，低位加余数，高位加模（如3*5=15，则高位加1，低位加5）。最后再考虑是否进位，并剔除高位的0。
代码如下：

class Solution:
    def multiply(self, num1, num2):
        # num1 = int(num1)
        # num2 = int(num2)
        # return str(num1*num2)
        if num1 == '0' or num2 == '0':
            return '0'
        res = [0 for i in range(len(num1)+len(num2))]         #初始化一个与结果等长的数组，数组中的每个元素都为0
        for i in range(len(num1)-1,-1,-1):
            for j in range(len(num2)-1,-1,-1):
                tmp = (ord(num1[i])-ord('0')) * (ord(num2[j])-ord('0'))      #两数组任意两元素相乘
                res[i+j] += int(tmp / 10)        #高位加模
                res[i+j+1] += tmp % 10           #低位加余数
        for i in range(len(res)-1,0,-1):
            carry = res[i]//10           #判断是否需要进位
            if carry > 0:
                res[i] = res[i]%10       #if需要进位，则本位取余数，高位加上进位数
                res[i-1] += carry
        res = ''.join(str(x) for x in res).lstrip('0')        #剔除高位的0
        return res