题目:https://leetcode-cn.com/problems/multiply-strings/
代码:
class Solution { public String multiply(String num1, String num2) { //因为num1和num2最长为110,所以他们的乘积最大为110*2,预留110*2个数组空间 int[] res = new int[110*2]; //遍历第一个数 for (int i = 0; i < num1.length(); i++) { //k的作用充当res结果的游标 int k = i; int n1 = charToInt(num1.charAt(num1.length() - i - 1)); //遍历第二个数 for (int j = 0; j < num2.length(); j++) { int n2 = charToInt(num2.charAt(num2.length() - j - 1)); //n1*n2的结果加到k位置的值上 res[k] = res[k] + (n1 * n2); //因为会存在进位的情况,所以k+1位置的值要加上k位置的十位值,加完之后k位置的值要修正为k位置的个位值 res[k + 1] = res[k + 1]+res[k] / 10; res[k] = res[k] % 10; k++; } } //因为算出来的res数组的结果是逆序的,且包含一堆0开头,所以这里是反转显示结果 StringBuilder sb = new StringBuilder(); boolean tag = false; for (int i = res.length - 1; i >= 0; i--) { if (tag || res[i] != 0) { sb.append(res[i]); tag = true; } } return sb.length()==0?"0":sb.toString(); } /** * char类型转int值 * @param c * @return */ private int charToInt(char c) { return c - '0'; } }
解题思路:
因为题目要求不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理(要不然这个题目也没啥意义了)。所以我一开始考虑的是自己实现解析函数,即将字符串解析成int类型(自己实现Integer.parseInt()方法)然后直接两个int值相乘得到结果。但是提交代码之后发现,int类型长度不够,改成long也不够,因为num1和num2的长度最长可以为110,这啥类型肯定都不够长的。
没办法,只能自己实现乘法,采用的当然是从小就开始学的竖式,原理图如下:
具体的操作参考代码及注释,原理基本就是把数字拆开,2个数2个数相乘(九九乘法表),使用一个int数组来保存每次相乘的结果,需要考虑大于10的情况下要进位,最后输出结果即可。