题目：
以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
数据范围：，字符串仅由’0’~‘9’构成
要求：时间复杂度
首先先想到的还是通过从右向左遍历一位一位相加，像是小学生手算一样计算进位最后得到结果：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
//溢出标记
int over = 0;
String result = "";
int index = 1;
int loopleft = Math.max(s.length(), t.length());
int[] s_array = s.chars().toArray();
int[] t_array = t.chars().toArray();
for(; loopleft > 0; loopleft--,index ++){
int a = s.length() >= index ? (s_array[s.length() - index] - '0'):0;
int b = t.length() >= index ? (t_array[t.length() - index] - '0'):0;
result = ((a+b+over)>0 ? (a+b+over) % 10 : 0) + result;
over = (a+b+over)>0 ? (a+b+over) / 10 : 0;
}
result = (over==0 ? "" : "1") + result;
return result;
}
}运行时间： 2001 ms 占用内存：9912K 状态：运行超时
超了近一倍的时间，显然不行，那么就要减少运算次数，我先想到的是转换函数paresInt和charAt，虽然是java内部实现的，但是因为是通用方法，会有很多冗余判断，比如下标长度之类的，因此我选择用switch直接比较来映射结果：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
//溢出标记
int over = 0;
long start = System.currentTimeMillis();
int SPLIT_LENGTH = 16;
String result = "", format = "";
for(int i = 0; i< SPLIT_LENGTH; i++){
format += "0";
}
long a,b;
int times = Math.max((s.length()-1)/SPLIT_LENGTH, (t.length()-1)/SPLIT_LENGTH);
int index = 0, sl = s.length(), tl = t.length();
boolean sOut = false, tOut = false;
int s_start, s_end, t_start, t_end;
for(;times >= 0; times--,index++){
if(sOut){
a = 0l;
}else if((index+1)*SPLIT_LENGTH >= sl-1){
System.out.println("s is out");
s_start = 0;
if(index == 0){
s_end = sl;
}else{
s_end = sl - index * SPLIT_LENGTH;
}
sOut = true;
a = Long.parseLong(s.substring(s_start, s_end));
}else{
s_start = sl - (index+1)*SPLIT_LENGTH;
s_end = sl - index * SPLIT_LENGTH;
a = Long.parseLong(s.substring(s_start, s_end));
}
if(tOut){
b = 0l;
}else if((index+1)*SPLIT_LENGTH >= tl-1){
System.out.println("t is out");
t_start = 0;
if(index == 0){
t_end = tl;
}else{
t_end = tl - index * SPLIT_LENGTH;
}
tOut = true;
b = Long.parseLong(t.substring(t_start, t_end));
}else{
t_start = tl - (index+1)*SPLIT_LENGTH;
t_end = tl - index * SPLIT_LENGTH;
b = Long.parseLong(t.substring(t_start, t_end));
}
System.out.println("a:" + a + " b:" + b + " over:" + over);
Long tmp = a + b + over;
if( sOut && tOut){
result = tmp + result;
}else{
if(tmp.toString().length() > SPLIT_LENGTH) over = 1; else over = 0;
result = (format + tmp).substring((""+tmp).length()) + result;
}
}
return result;
}
}
这次修改通过long形计算来提高算速，用一个SPLIT_LENGTH来控制分组大小，最终达到358ms通过了测试。
但是查看排名发现，最快的只需要53ms，使用的还是第一种思路，于是尝试优化第一种。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
//溢出标记
int over = 0;
int index = 1, sl=s.length(), tl=t.length();
char[] result = new char[Math.max(sl, tl)];
for(int loopleft = Math.max(sl, tl); loopleft >= index; index++){
if(sl >= index) over += s.charAt(sl - index)-'0';
if(tl >= index) over += t.charAt(tl - index)-'0';
result[loopleft - index] = (char)('0' + over % 10);
over = over / 10;
}
return (over==0?"":"1") + new String(result);
}
}最终51ms。
