Leetcode 43. Multiply Strings （python+cpp）

题目

解法：

class Solution:def multiply(self, num1: str, num2: str) -> str:if num1 == '0' or num2 == '0':return '0'# initialize the product as a list, the length of the product of these two num won't exceed the sum of length of num1 and num2product = [0] * (len(num1) + len(num2))# initialize the operation position, starting from the end of the product listpos = len(product) - 1for n1 in reversed(num1):# store the position for multiplying a single char in num1 with the entire num2curr_pos = posfor n2 in reversed(num2):# add the results at corresponding positionproduct[curr_pos] += (ord(n1) - ord('0')) * (ord(n2) - ord('0'))# take care of the carryproduct[curr_pos - 1] += product[curr_pos] // 10product[curr_pos] %= 10curr_pos -= 1pos -= 1ans = ''# removed the starting 0si = 0while i < len(product):if product[i] != 0:breaki += 1while i < len(product):ans = ans + str(product[i])i += 1return ans

解法2: 利用两个数字的当前位置找到乘积的正确位置

class Solution:def multiply(self, num1: str, num2: str) -> str:    if num1 == '0' or num2 == '0':return '0'product = [0] * (len(num1) + len(num2))for i in range(len(num1)-1,-1,-1):for j in range(len(num2)-1,-1,-1):# compute multiplication of current two positionres = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))# use i,j to find the correct position and take care of the carryproduct[i + j + 1] += resproduct[i + j] += product[i + j + 1] // 10product[i + j + 1] %= 10ans = ''while i < len(product):if product[i] != 0:breaki += 1while i < len(product):ans = ans + str(product[i])i += 1return ans

follow up:关于string的加减乘看这两篇：链接1 链接2

二刷

二刷写了一种更加符合逻辑的方法，跟我们人计算乘积比较一致，而且没有参杂整数和字符之间的相互转换。上面两种解法最后还是加了证书到字符的转换的

class Solution {
    
public:string singleMul(string num1,char d){
    string ans = "";int carry = 0;for(int i=num1.size()-1;i>=0;i--){
    auto c = num1[i];int res = (c-'0') * (d-'0') + carry;// cout << res << endl;carry = res / 10;ans = char((res%10) + '0') + ans;}if(carry) ans = char((carry+'0')) + ans;return ans;}string add(string num1,string num2){
    string ans = "";int carry = 0;int p1 = num1.size()-1;int p2 = num2.size()-1;while(p1 >= 0 || p2 >= 0){
    // cout << p1 << p2 << endl;int v1 = p1 >= 0 ? num1[p1] - '0' : 0;int v2 = p2 >= 0 ? num2[p2] - '0' : 0;ans = char((v1 + v2 + carry) % 10 + '0') + ans;// cout << ans << endl;carry = (v1 + v2 + carry) / 10;p1--;p2--;}if(carry) ans = char((carry+'0')) + ans;return ans;}string multiply(string num1, string num2) {
    // cout << singleMul("123",'5') << endl;if(num1 == "0" || num2 == "0") return "0";if(num2.size() == 1) return singleMul(num1,num2[0]);string ans = "0";for(int i = num2.size()-1;i>=0;i--){
    string tmp = singleMul(num1,num2[i]);for(int j=1;j<num2.size()-i;j++){
    tmp += "0";}// cout << tmp << endl;ans = add(ans,tmp);// cout << ans << endl;}return ans;// return "";}
};