题目内容
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
分析过程
- 题目归类:
数学题目。 -
题目分析:
两个数相乘的得到的新书不会超过两个数的位数之和。
string 相乘,由于不能转变成int所以就只能考虑乘法的规则1 2 3 j x 2 1 i ----- 1 2 3 2 4 6 ------- 2 5 8 3 每一个nums[i] * nums[j] 都会保存到 nums[i+j]和nums[i+j+1]中 所以我们根据乘法表把数据都保存到相应的地方。
- 边界分析:
- 空值分析
- 循环边界分析
从左到右必须要控制起始不能为0.
- 方法分析:
- 数据结构分析
- 状态机
- 状态转移方程
- 最优解
测试用例构建
代码实现
class Solution {
public String multiply(String num1, String num2) {
int num1Length = num1.length();
int num2Length = num2.length();
int nums[] = new int[num1Length+num2Length];
for(int i = num1Length - 1 ; i >= 0 ; i--){
for(int j = num2Length - 1; j >= 0 ; j--){
int p1 = i + j, p2 =i + j + 1, sum = nums[p2] + (num1.charAt(i)-'0') * (num2.charAt(j) - '0');
nums[p1] += sum /10;
nums[p2] = sum % 10;
}
}
StringBuilder stringBuilder = new StringBuilder();
int flag =0;
for(int i = 0; i < num1Length+num2Length; i++ ) {
if(nums[i] != 0){
flag =1;
}
if(flag ==1)
stringBuilder.append(nums[i]+"");
}
if(stringBuilder.length()==0)
stringBuilder.append(0+"");
return stringBuilder.toString();
}
}