LeetCode题练习与总结：复数乘法--537

一、题目描述

复数 可以用字符串表示，遵循 "实部+虚部i" 的形式，并满足下述条件：

• 实部 是一个整数，取值范围是 [-100, 100]
• 虚部 也是一个整数，取值范围是 [-100, 100]
• i^2 == -1

给你两个字符串表示的复数 num1 和 num2 ，请你遵循复数表示形式，返回表示它们乘积的字符串。

示例 1：

输入：num1 = "1+1i", num2 = "1+1i"
输出："0+2i"
解释：(1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。

示例 2：

输入：num1 = "1+-1i", num2 = "1+-1i"
输出："0+-2i"
解释：(1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。 

提示：

• num1 和 num2 都是有效的复数表示。

二、解题思路

1. 首先，我们需要解析两个输入字符串 num1 和 num2，提取出它们的实部和虚部。这可以通过查找 + 和 i 的位置来实现。

2. 然后，根据复数乘法的规则，计算两个复数乘积的实部和虚部。复数乘法的规则是：(a + bi) * (c + di) = (ac - bd) + (ad + bc)i，其中 a 和 b 是第一个复数的实部和虚部，c 和 d 是第二个复数的实部和虚部。

3. 最后，将计算得到的实部和虚部格式化为字符串，按照题目要求的格式返回。

三、具体代码

class Solution {
    public String complexNumberMultiply(String num1, String num2) {
        // 解析第一个复数的实部和虚部
        int plusIndex1 = num1.indexOf('+');
        int real1 = Integer.parseInt(num1.substring(0, plusIndex1));
        int imaginary1 = Integer.parseInt(num1.substring(plusIndex1 + 1, num1.length() - 1));
        
        // 解析第二个复数的实部和虚部
        int plusIndex2 = num2.indexOf('+');
        int real2 = Integer.parseInt(num2.substring(0, plusIndex2));
        int imaginary2 = Integer.parseInt(num2.substring(plusIndex2 + 1, num2.length() - 1));
        
        // 计算乘积的实部和虚部
        int real = real1 * real2 - imaginary1 * imaginary2;
        int imaginary = real1 * imaginary2 + real2 * imaginary1;
        
        // 格式化并返回结果
        return real + "+" + imaginary + "i";
    }
}

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

1. 时间复杂度

• 解析第一个复数的实部和虚部：

  • indexOf 方法的时间复杂度是 O(n)，其中 n 是字符串的长度。
  • substring 方法的时间复杂度是 O(m)，其中 m 是提取的子字符串的长度。
  • parseInt 方法的时间复杂度是 O(m)，因为需要遍历整个子字符串。
  • 对于第一个复数，这些操作总共的时间复杂度是 O(n + m + m) = O(n + 2m)。

• 解析第二个复数的实部和虚部：

  • 与第一个复数相同，时间复杂度也是 O(n + 2m)。

• 计算乘积的实部和虚部：

  • 只涉及到几个基本的算术操作，时间复杂度是 O(1)。

• 格式化并返回结果：

  • 字符串连接操作的时间复杂度是 O(n)，其中 n 是最终字符串的长度。

因此，总的时间复杂度是 O(n + 2m) + O(n + 2m) + O(1) + O(n) = O(2n + 4m + n) = O(3n + 4m)。由于 n 和 m 都是输入字符串的长度，我们可以认为它们是相等的，所以时间复杂度可以简化为 O(n)。

2. 空间复杂度

• 解析复数时使用的变量 real1, imaginary1, real2, imaginary2 都是基本数据类型，占用常数空间，空间复杂度是 O(1)。

• 计算乘积的实部和虚部使用的变量 real 和 imaginary 也是基本数据类型，占用常数空间，空间复杂度是 O(1)。

• 格式化并返回结果时，创建了一个新的字符串，其长度与输入字符串的长度成线性关系，空间复杂度是 O(n)。

因此，总的空间复杂度是 O(1) + O(1) + O(n) = O(n)。由于 n 是输入字符串的长度，所以空间复杂度是 O(n)。

五、总结知识点

• 字符串操作：

  • indexOf：用于查找字符串中特定字符或子字符串的位置。
  • substring：用于提取字符串的子字符串。
  • length()：用于获取字符串的长度。

• 整数解析：

  • Integer.parseInt：用于将字符串解析为整数。

• 算术运算：

  • 加法（+）、减法（-）、乘法（*）：用于执行基本的算术运算。

• 字符串连接：

  • 使用 + 运算符将字符串和整数拼接起来，以构建最终的复数字符串表示。

• Java基本数据类型：

  • int：用于存储整数。

• 算法逻辑：

  • 复数乘法的数学规则：(a + bi) * (c + di) = (ac - bd) + (ad + bc)i。

• 代码结构：

  • 方法定义：public String complexNumberMultiply(String num1, String num2) 定义了一个公共方法，接受两个字符串参数并返回一个字符串。
  • 变量声明和初始化：在方法内部声明并初始化所需的变量。

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