每天一道算法题之字符串相乘

字符串相乘

题目描述:

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式1

• 例如:

  输入: num1 = “2”, num2 = “3”

  输出: “6”

• 题目解析:字符串求和的进阶版
  • 非负整数是以字符串的形式进行表示,那么计算的时候应该从低位开始(从右向左遍历).

  • 与求和不同,两数相乘需要知道较低位的运算结果:

    ​ 比如 23 * 62 先计算 2*23,在计算 6*23时,更新最后结果是要用到2*23的结果

    因此,需要一种数据结果来存储,较低位的运算结果,采用数组进行存储

  • 计算依然分为三部分
  • 在计算时,除了要加进位外,还需要加上当前位置较低位的运算结果.

代码部分:

public String multiply(String num1, String num2) {

    if(num1.length() == 0 || num2.length() == 0) return "";
    if(num1.equals("0")|| num2.equals("0")) return "0";

    int len1 = num1.length();
    int len2 = num2.length();
    
    //两数相乘的位数是这两个位数的和,res存储较低位的运算结果
    int[] res = new int[len1+len2];
    int index = res.length-1;
    
    int idx2 = len2-1;
    int array = 0;//保存进位
    
    while(idx2>=0){
        
    	int j = num2.charAt(idx2) - '0';
        int tempIdx = index;
        
        for(int idx1 = len1-1;idx1>=0;idx1--){
            
        	int i = num1.charAt(idx1) - '0';
            int temp = i*j+array + res[tempIdx];//(res[tempIdx] 当前位置较低位的运算结果)
            res[tempIdx] = temp%10;
            array = temp/10;
            tempIdx--;
            
        }
        idx2--;
        index--;
        
        //处理每一次乘法后的进位
        if(array != 0) res[tempIdx] = array;
        array = 0;
        
    }
    
    StringBuilder sb = new StringBuilder();
    for(int i = 0;i< res.length;i++){
        if(!(res[i] == 0 && sb.length() == 0)) sb.append(res[i]);
    }
    return sb.toString();
}
           

1. https://leetcode-cn.com/problems/multiply-strings/ ↩︎