LeetCode OJ：Multiply Strings (字符串乘法)

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

给出两个字符串，返回对应数字想乘后的字符串，由于这个字符串可能很大，所以不能采用一般的乘法，这里用的方法是模拟手工的乘法运算，算法

本身很简单，就是当时写的时候有些很小的细节搞错了，找了很久的错。啊啊啊啊啊，要细心啊。代码如下，没什么好说的：

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {
 4         if(num1 == "0" || num2 == "0") return "0";
 5         int steps = 0;
 6         int pos = 0;
 7         int flag = 0;
 8         int val = 0;
 9         string result = "";
10         reverse(num1.begin(), num1.end());
11         reverse(num2.begin(), num2.end());
12         int len1 = num1.length();
13         int len2 = num2.length();
14         for(int i = 0; i < len1; ++i){
15               pos = steps;
16             for(int j = 0; j < len2; ++j){
17                 val = (num1[i] - '0')*(num2[j] - '0') + flag;
18                 if(result.size() <= pos){
19                     result.append(1, val%10 + '0');
20                 }else{
21                     val += (result[pos] - '0');
22                     result[pos] = val%10 + '0';
23                 }
24                 flag = val/10;
25                 pos++;  
26             }
27             if(flag > 0)
28                 result.append(1, flag + '0');
29             flag = 0;
30             steps++;
31         }
32         reverse(result.begin(), result.end());
33         return result;
34     }
35 };

java的api真是恶心，处理字符串处理了半天，最后debug通过，往上一贴竟然是TLE的代码，代码在下面，应该是我对字符串的处理比较耗时间了，其实最好的应该是先讲String转换成List，List里面相对的API的函数多一点，String里面连最普通的reverse函数都没有。先马一下这种做法，有时间了再来写。下面的这个道理上应该没有任何问题，就是字符串处理的太慢了。

 1 public class Solution {
 2     public String multiply(String num1, String num2) {
 3         if(num1.equals("0") || num2.equals("0"))
 4             return (new String("0"));
 5         int step = 0;
 6         int pos = 0;
 7         int carry = 0;
 8         int val = 0;
 9         String result = new String("");
10         num1 = ReverseStr(num1);
11         num2 = ReverseStr(num2);
12         for(int i = 0; i < num1.length(); ++i){ //java的api好乱啊,一会是length一会有是size()
13             pos = step;
14             for(int j = 0; j < num2.length(); ++j){
15                 val = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') + carry;
16                 if(pos >= result.length())
17                     result += (char)(val%10 + '0');
18                 else{
19                     val += (result.charAt(pos)-'0');
20                     result = (new StringBuffer(result)).replace(pos, pos + 1, "" + (char)(val%10+'0')).toString();
21                 }
22                 carry = val/10;
23                 pos++;
24             }
25             if(carry != 0)
26                 result += (char)(carry +'0');
27             carry = 0;
28             step++;
29         }
30         return ReverseStr(result);
31         
32     }
33 
34     public String ReverseStr(String str){
35         return (new StringBuffer(str)).reverse().toString();
36     }
37     
38 }