中级农民
- 积分
- 100
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-6-19
- 最后登录
- 1970-1-1
|
自己写了一下
public class Solution{
public String pow(int x,int y){
//1<=x<=9 1<=y<=99
if(x==0) return "1";
return helper(String.valueOf(x),String.valueOf(y));
}
public String helper(String x, String y){
//int m=Integer.parseInt(x);
int n=Integer.parseInt(y);
if(n==0) return "1";
if(n==1) return x;
String half=helper(x,String.valueOf(n/2));
if(n%2==0)
return multiply(half,half);
else
return multiply(x,multiply(half,half));
}
public String multiply(String x, String y){
int m=x.length();
int n=y.length();
int[] res=new int[n+m];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
res[m+n-1-i-j]+=(x.charAt(m-1-i)-'0')*(y.charAt(n-1-j)-'0');
}
}
int carry=0;
for(int i=n+m-1;i>-1;i--){
int val=res[i]+carry;
res[i]=val%10;
carry=val/10;
}
StringBuilder sb=new StringBuilder();
boolean flg=false;
for(int i=0;i<n+m;i++){
if(!flg&&res[i]!=0)
flg=true;
if(flg)
sb.append(res[i]);
}
if(!flg)
return "0";
else
return sb.toString();
}
} |
|