LeetCode题练习与总结：字符串相乘

一、题目

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

• 1 = 0; i--) { if (sb.length() > 0 || result[i] != 0) { sb.append(result[i]); } } // 如果结果为0，直接返回 "0" return sb.toString(); } }

  四、时间复杂度和空间复杂度

  1. 时间复杂度

  • 代码中有两个嵌套的循环。外层循环遍历 num2 的每一位，这有 O(n) 的时间复杂度，其中 n 是 num2 的长度。
  • 内层循环遍历 num1 的每一位，这有 O(m) 的时间复杂度，其中 m 是 num1 的长度。
  • 因此，嵌套循环的总时间复杂度是 O(n * m)。

    2. 空间复杂度

    • 我们使用了一个长度为 num1.length() + num2.length() 的数组 result 来存储中间结果。
    • 在最坏的情况下，这将是两个字符串长度之和，即 O(n + m)。
    • 我们还使用了一个 StringBuilder 来构造最终的结果字符串，其空间复杂度为 O(1)，因为它的大小只与结果字符串的长度有关，而不依赖于输入字符串的长度。
    • 综上所述，这段代码的空间复杂度是 O(n + m)。

      五、总结知识点

      1. 字符串操作：

      • 使用 StringBuilder 类来反转字符串。StringBuilder 提供了 reverse() 方法，可以反转字符串中的字符顺序。
      • 通过 charAt(index) 方法访问字符串中的特定字符。
      • 使用 toString() 方法将 StringBuilder 对象转换为字符串。

        2. 数组操作：

        • 初始化一个整数数组 result，用于存储乘法操作的中间结果。
        • 在数组中进行基本的算术操作，包括加法和整除，以及取余操作来处理乘法中的进位。

          3. 循环结构：

          • 使用嵌套的 for 循环来遍历两个字符串的每一位，并执行逐位相乘的操作。
          • 外层循环遍历 num2 的每一位，内层循环遍历 num1 的每一位。

            4. 进位处理：

            • 在每次乘法操作后，检查结果是否大于或等于 10，如果是，则需要进行进位处理。
            • 通过整除 10 来获取进位值，并将其加到数组的下一位上。

              5. 结果构造：

              • 使用 StringBuilder 来构造最终的结果字符串，从数组的最低位开始遍历，直到最高位。
              • 在遍历过程中，只有当 result 数组中的值不为 0 或者 StringBuilder 已经包含字符时，才将该位的值添加到结果字符串中。

                6. 边界条件处理：

                • 代码中检查了如果 num1 或 num2 中有一个为 "0"，则直接返回 "0"，这是处理乘法中特殊情况的一种简便方法。

                  以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。