LeetCode Weekly Contest 25 之 537.Complex Number Multiplication
LeetCode Weekly Contest 25 之 537.Complex Number Multiplication
LeetCode Weekly Contest 25
赛题
本次周赛主要分为以下4道题：
- 507 Perfect Number (3分)
- 537 Complex Number Multiplication (6分)
- 545 boundary of Binary Tree (8分)
- 546 Remove Boxes (9分)
537 Complex Number Multiplication
Problem:
Given two strings representing two complex numbers. You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:
Input: “1+1i”, “1+1i” Output: “0+2i” Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
Input: “1+-1i”, “1+-1i” Output: “0+-2i” Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note
- The input strings will not have extra blank.
- The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.
依旧没有难度，这道题考的是对字符串的处理，但我又把它想复杂了，浪费了大量时间在解析上，就针对我的解题思路，来慢慢优化。
My first solution(6ms)
public String complexNumberMultiply(String a, String b) {
int a1 = 0;
int a2 = 0;
StringBuilder a1Builder = new StringBuilder();
StringBuilder a2Builder = new StringBuilder();
for(int i = 0; i < a.length(); i++){
if(a.charAt(i) != '+')
a1Builder.append(a.charAt(i));
if(a.charAt(i) == '+'){
a2Builder.append(a.substring(i+1,a.length()-1));
break;
}
}
a1 = Integer.parseInt(a1Builder.toString());
a2 = Integer.parseInt(a2Builder.toString());
int b1 = 0;
int b2 = 0;
StringBuilder b1Builder = new StringBuilder();
StringBuilder b2Builder = new StringBuilder();
for(int i = 0; i < b.length(); i++){
if(b.charAt(i) != '+')
b1Builder.append(b.charAt(i));
if(b.charAt(i) == '+'){
b2Builder.append(b.substring(i+1,b.length()-1));
break;
}
}
b1 = Integer.parseInt(b1Builder.toString());
b2 = Integer.parseInt(b2Builder.toString());
StringBuilder res = new StringBuilder();
int c1 = a1*b1 - a2*b2;
int c2 = a1 * b2 + a2 * b1;
res.append(String.valueOf(c1));
res.append("+");
res.append(String.valueOf(c2));
res.append("i");
return res.toString();
}上述代码有个细节，刚开始我在code时，还区分了负号，但String.valueOf()是支持对负号提取的，所以无须多此一举。
该代码有大量重复的内容，如for循环，对“+”号的分解。这一操作用java的split方法就可以轻松实现了。其实核心思想个是加法的二元操作。一次split，就能区分加法的左和右，所以完善后的代码为：
My second solution(12ms)
public String complexNumberMultiply(String a, String b) {
int a1 = Integer.parseInt(a.split("\\+|i")[0]);
int a2 = Integer.parseInt(a.split("\\+|i")[1]);
int b1 = Integer.parseInt(b.split("\\+|i")[0]);
int b2 = Integer.parseInt(b.split("\\+|i")[1]);
String res = "";
int c1 = a1 * b1 - a2 * b2;
int c2 = a1 * b2 + a2 * b1;
res = String.valueOf(c1)+"+"+String.valueOf(c2)+"i";
return res;
}代码简洁很多，用到了split方法和正则表达式，其中加号的描述需要转义，且在解析虚数位置时，要去除符号i。实际的运行效率比较低，且并不知道是如何对字符串做分解的，所以我们用一种更加效率的拆分，来实现它。
My third solution(5ms)
public String complexNumberMultiply(String a, String b) {
int[] aa = parseComplex(a);
int[] bb = parseComplex(b);
int c1 = aa[0] * bb[0] - aa[1] * bb[1];
int c2 = aa[0] * bb[1] + aa[1] * bb[0];
return String.valueOf(c1)+"+"+String.valueOf(c2)+"i";
}
private int[] parseComplex(String complex){
int[] res = new int[2];
int i = 0;
for(; complex.charAt(i) != '+'; i++);
res[0] = Integer.parseInt(complex.substring(0,i));
res[1] = Integer.parseInt(complex.substring(i+1,complex.length()-1));
return res;
}这种查找加法的方式，的确头一次见，但很管用，i必须是个全局变量，它的思路很简单，找到“+”号所在的位置，有了i，就能对字符串做切割了，不需要向我第一种解决方案，那么复杂，还得append左半部分。哇，啥时候能写出如此优美的代码啊！