Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
以下文字描述来自这里:
- 直接乘会溢出,所以每次都要两个single digit相乘,最大81,不会溢出。
- 比如385 * 97, 就是个位=5 * 7,十位=8 * 7 + 5 * 9 ,百位=3 * 7 + 8 * 9 …可以每一位用一个int表示,存在一个int[]里面。
- 这个数组最大长度是num1.len + num2.len,比如99 * 99,最大不会超过10000,所以4位就够了。
- 这种个位在后面的,不好做(10的0次方,可惜对应位的数组index不是0而是n-1),所以干脆先把string reverse了代码就清晰好多。
- 最后结果前面的0要清掉。
// 2 3 4 // × 5 6 7 //------------------------ // 14 21 28 // 12 18 24 // + 10 15 20 //------------------------ // 10 27 52 45 28 //------------------------ // 1 3 2 6 7 8 public String multiply(String num1, String num2) { String n1 = new StringBuilder(num1).reverse().toString(); String n2 = new StringBuilder(num2).reverse().toString(); int[] m = new int[n1.length()+n2.length()]; for(int i=0; i<n1.length(); i++) { int a = n1.charAt(i)-'0'; for(int j=0; j<n2.length(); j++) { m[i+j] += a*(n2.charAt(j)-'0'); } } int carry = 0; StringBuilder sb = new StringBuilder(); for(int i=0; i<m.length; i++) { int sum = m[i]+carry; carry = sum / 10; int digit = sum % 10; sb.append(digit); } for(int i=sb.length()-1; i>0; i--) { if(sb.charAt(i) == '0') { sb.deleteCharAt(i); } else { break; } } return sb.reverse().toString(); }
另外一种写法,这种更好理解:
public String multiply(String num1, String num2) { int[] A = toDigits(num1); int[] B = toDigits(num2); int m = A.length, n = B.length; int[] C = new int[m+n]; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { C[i+j] += A[i] * B[j]; } } int carry = 0; int nonZeroIdx = 0; //最后一个非零元素的下标,也就是最高位的索引 for(int i=0; i<C.length; i++) { int sum = C[i] + carry; carry = sum / 10; C[i] = sum % 10; if(C[i] != 0) { nonZeroIdx = i; } } StringBuilder sb = new StringBuilder(); for(int i=nonZeroIdx; i>=0; i--) { sb.append(C[i]); } return sb.toString(); } private int[] toDigits(String num) { int n = num.length(); int[] digits = new int[n]; for(int i=0; i<n; i++) { digits[i] = num.charAt(n-i-1) - '0'; } return digits; }
相关推荐
c语言入门 C语言_leetcode题解之43-multiply-strings.c
js js_leetcode题解之43-multiply-strings.js
java java_leetcode题解之Multiply Strings.java
- Multiply Strings: 给定两个非负整数字符串形式的数,要求进行乘法运算。 - Wildcard Matching: 实现支持'?'和'*'的通配符匹配。 - Jump Game / Jump Game II: 第一个问题要求判断是否能到达数组的最后一个位置,...
leetcode卡 LeetCode LeetCode题解 目录 字符串问题 ID Title C++ 难度 备注 0008 String to Integer(atoi) :star: :star: :star: ...Multiply Strings :star: :star: 大数相乘 0044 Wild Card Matchi
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Multiply Strings 066 Add Binary Linked-list 002 Add Two Numbers Stack 020 Valid Parenthesis Hash Table 001 TwoSum Reference 完整的学习流程 How to be a softwair engineer: 其他人详解 Python的各式演算法
第43题:字符串相乘(Multiply Strings) 题目描述: 给定两个非负整数num1和num2,它们的长度相同,用字符串形式表示。你的任务是计算它们的乘积,并返回结果字符串。例如,"2" 和 "3" 相乘等于 "6"。 解决方案:...
在本压缩包中,主题聚焦于使用Python解决LeetCode第43题——“字符串相乘”(Multiply Strings)。这是一道常见的编程面试题,旨在测试应聘者的字符串处理和算法设计能力。下面将详细探讨该题目的背景、解题思路、...
22. **Multiply Strings**:两个字符串表示的数相乘。同样模拟笔算乘法,使用二维数组存储中间结果。 23. **Rotate Array**:将数组顺时针旋转指定步数。可以先反转整个数组,再反转前半部分和后半部分。 24. **...