leetcode 43. Multiply Strings

题目内容

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();
    }
}

效率提高

拓展问题

上一篇:3.3 GO字符串处理


下一篇:HJ14