【LeetCode题解】字符串乘法、加法

字符串乘法

方法一

思路

模拟乘法的过程,将s2字符串从右到左,逐个位置与s1相乘,将每一位相乘的结果进行相加。

  1. 从右到左遍历s2得到字符char1
  2. 将char1与s1相乘,得到结果result1
    2.1 根据char1的下标需要补零
    2.2 使用StringBuilder将结果缓存,最后将结果反转
  3. 将result1相加得到最终结果result

代码

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        StringBuilder result = new StringBuilder();
        for (int i = num2.length() - 1; i >= 0; i--) {
            String multiplyByOne = multiplyByOne(num1, num2, i);
            result = addString(multiplyByOne, result.toString());
        }

        return result.toString();
    }
        public StringBuilder addString(String s1, String s2) {
        StringBuilder result = new StringBuilder();
        int bit = 0;
        int n = 0;
        int i = s1.length() - 1;
        int j = s2.length() - 1;
        while (i >= 0 || j >= 0) {
            int x = i >= 0 ? s1.charAt(i) - '0' : 0;// 不存在赋值为0,省略多次判断
            int y = j >= 0 ? s2.charAt(j) - '0' : 0;
            int m = x + y + bit;
            bit = m / 10;
            n = m % 10;
            result.append(n);
            i--;
            j--;
        }
        // 细节
        if (bit > 0) {
            result.append(bit);
        }
        return result.reverse();
    }

    public String multiplyByOne(String num1, String num2, int index) {
        int bit = 0; // 进位
        int n = 0; // 个位
        int x = num2.charAt(index) - '0';
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < num2.length() - index - 1; i++) {
            stringBuilder.append("0");
        }
        for (int i = num1.length() - 1; i >= 0; i--) {
            int y = num1.charAt(i) - '0';
            int m = x * y + bit;
            bit = m / 10;
            n = m % 10;
            stringBuilder.append(n);
        }
        // 细节
        if (bit > 0) {
            stringBuilder.append(bit);
        }
        return stringBuilder.reverse().toString();
    }
}

方法二

思路

两个指针 i,jnum1num2 上游走,计算乘积,同时将乘积叠加到 res 的正确位置**
num1[i]num2[j] 的乘积对应的就是 res[i+j]res[i+j+1] 这两个位置
假设num1[i]num2[j]相乘得到multify,其中,res[i+j+1]属于multify的个位,res[i+j]属于multify的进位

代码

    public String multiply2(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int[] res = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int n2 = num2.charAt(j) - '0';
                int sum = (res[i + j + 1] + n1 * n2);
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            result.append(res[i]);
        }
        return result.toString();
    }
上一篇:管道取珠[NOIP2009]


下一篇:利用jieba库,提取关键词