以字符串的形式读入两个数字,编写一个函数计算它们的乘积,以字符串形式返回。
数据范围: 读入的数字大小满足
要求:空间复杂度
,时间复杂度
(假设m是n的长度)
class Solution
{
public:
// 实现s*t
string mul(string s, char t)
{
int num = t - '0', len = s.length(), carry = 0;
string ans = "";
for (int i = len - 1; i >= 0; --i)
{
// 乘法的结果
int a = s[i] - '0';
int b = a * num;
// 求和
int c = b + carry;
// 进位
carry = c / 10;
// 余数
c %= 10;
// 添加结果
ans = ans + to_string(c);
}
// 如果余数不为零
if (carry != 0)
{
ans = ans + to_string(carry);
}
// 字符串逆转
reverse(ans.begin(), ans.end());
return ans;
}
// 实现s+num*t,即在t后面补num个零
string add(string s, string t, int num)
{
for (int i = 0; i < num; ++i)
{
t = t + "0";
}
// s+t
string ans = "";
// 进位
int carry = 0;
int s_len = s.length(), t_len = t.length();
// 双指针
int i = s_len - 1, j = t_len - 1;
// 遍历
while (i >= 0 || j >= 0)
{
int a = (i < 0) ? 0 : s[i] - '0';
int b = (j < 0) ? 0 : t[j] - '0';
// 向前移动,负数也没有关系
--i;
--j;
// 和
int sum = a + b + carry;
// 进位
carry = sum / 10;
// 余数
sum %= 10;
// 添加结果
ans = ans + to_string(sum);
}
// 如果还有进位
if (carry != 0)
{
ans = ans + to_string(carry);
}
// 字符串逆转
reverse(ans.begin(), ans.end());
return ans;
}
string solve(string s, string t)
{
if (s == "0" || t == "0")
{
return "0";
}
string ans = "";
int len = t.length();
// 用s去乘以t的每一位
for (int i = len - 1; i >= 0; --i)
{
// 使用s乘以t的第i位
string temp_mul = mul(s, t[i]);
// 累加
ans = add(ans, temp_mul, len - i - 1);
}
return ans;
}
};
运行时间超过百分之零点几,空间超过个位数,大佬们提下改进意见呗,谢谢了。
import java.util.*;
public class Solution {
/**
描述
以字符串的形式读入两个数字,编写一个函数计算它们的乘积,以字符串形式返回。
(字符串长度不大于10000,保证字符串仅由'0'~'9'这10种字符组成)
示例1
输入:
"11","99"
复制
返回值:
"1089"
复制
说明:
11*99=1089
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve(String s, String t) {
if ("".equals(s) && "".equals(t)) {
return "0";
}
String result = "0";
int otherZero = 0;
for (int j = t.length() - 1; j >= 0; j--) {
String toAdd = muti(s, t.charAt(j) - '0', otherZero);
result = add(result, toAdd);
otherZero++;
}
return result;
}
public String add(String s, String t) {
if ("0".equals(t)) {
return "0";
} else if ("1".equals(t)) {
return s;
}
int inc = 0;
StringBuilder sb = new StringBuilder("");
int i = s.length() - 1;
int j = t.length() - 1;
while (i >= 0 || j >= 0 || inc == 1) {
int left = i >= 0 ? s.charAt(i) - '0' : 0;
int right = j >= 0 ? t.charAt(j) - '0' : 0;
int sum = left + right;
if (inc == 1) {
sum += 1;
inc = 0;
}
if (sum >= 10) {
sum = sum % 10;
inc = 1;
}
i--;
j--;
sb.append(sum);
}
sb.reverse();
return sb.toString();
}
public String muti(String str, int muti, int lastZero) {
if (muti == 0) {
return "";
}
StringBuilder result = new StringBuilder(str);
for (int i = 0; i < muti - 1; i++) {
result = new StringBuilder(add(result.toString(), str));
}
for (int i = 0; i < lastZero; i++) {
result.append("0");
}
return result.toString();
}
} import java.util.*;
public class Solution {
public String solve (String s, String t) {
//将字符串转化为数组形式
int len1=s.length(),len2=t.length();
int[] a1=new int[len1];
for(int i=0;i<len1;i++)a1[i]=s.charAt(i)-'0';
int[] a2=new int[len2];
for(int i=0;i<len2;i++)a2[i]=t.charAt(i)-'0';
// 开辟结果数组,结果长度至多为 lenOne + lenTwo
int[] tmp=new int[len1+len2];
// 开始计算,先不考虑进位,每次结果存在result[i + j + 1]位置
// 为什么是i + j + 1?
// 因为结果数组计算处理高位在数组左,低位在数组右。
//i+j+1实际上是往低位存,这样后面进位处理才正确
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
tmp[i+j+1]+=a1[i]*a2[j];
}
}
//进位
int carry=0;
for(int i=len1+len2-1;i>=0;i--){
tmp[i]=tmp[i]+carry;
carry=tmp[i]/10;
tmp[i]=tmp[i]%10;
}
// 转为String,需要无视前置0
StringBuilder res=new StringBuilder();
int cur=0;
while(cur<len1+len2&&tmp[cur]==0)cur++;
//添加
for(int i=cur;i<len1+len2;i++)res.append(tmp[i]);
//如果最终res长度为0,则代表输入类似"0" "0"的用例,结果应该输出“0”
return res.length()==0?"0":res.toString();
}
} class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
string curZero="";
int lenT=t.size();
string res="";
for(int i=lenT-1;i>=0;i--) {
string cur=(getMul(s,t[i]-'0')+curZero);
Add(res,cur);
curZero+="0";
}
return res;
}
void Add(string &res,string x) {
//将res和x表示的数字相加,返回结果的字符串形式
string s="";
int len1=res.size()-1;
int len2=x.size()-1;
int ex=0;
while(len1>=0 || len2>=0) {
int num=ex;
if(len1<0) {
num+=(x[len2]-'0');
len2--;
} else if(len2<0) {
num+=(res[len1]-'0');
len1--;
} else{
num+=(res[len1]-'0');
num+=(x[len2]-'0');
len2--;
len1--;
}
s+=('0'+num%10);
ex=num/=10;
}
if(ex!=0) {
s+=('0'+ex);
}
reverse(s);
res="";
//去掉前置0
int i=0;
while(i<s.size() && s[i]=='0')
i++;
if(i==s.size()) {
res="0";
} else{
while(i<s.size()) {
res+=s[i];
i++;
}
}
}
void reverse(string &m) {
for(int i=0,j=m.size()-1;i<j;i++,j--) {
char ch=m[i];
m[i]=m[j];
m[j]=ch;
}
}
string getMul(string s,int x) {
string m="";
int len=s.size();
int ex=0;//进位
for(int i=len-1;i>=0;i--) {
int cur=s[i]-'0';
int mul=cur*x+ex;
m+=((mul%10)+'0');
ex=mul/10;
}
if(ex!=0) {
m+=(ex+'0');
}
reverse(m);
return m;
}
}; //参考其他大佬的思路写的
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
// write code here
if(s=="0"||t=="0") return "0";
string res(s.size()+t.size(),'0');
int jinwei;
for(int i=s.size()-1;i>=0;--i){
jinwei=0;
for(int j=t.size()-1;j>=0;--j){
int tmp=(s[i]-'0')*(t[j]-'0')+res[i+j+1]-'0'+jinwei;
jinwei=tmp/10;
res[i+j+1]=tmp%10+'0';
}
if(jinwei) res[i]=jinwei+'0';
}
int i=0;
while(i<res.size()&&res[i]=='0') ++i;
return res.substr(i);
}
}; class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
// write code here
if(s.empty()||t.empty()) return "0";
int m = s.size(), n=t.size();
string res(m+n,'0');
for(int i=m-1;i>=0;--i){
for(int j=n-1;j>=0;--j){
int temp = (s[i]-'0')*(t[j]-'0') + res[i+j+1]-'0';
res[i+j+1] = temp%10 +'0';
int add = temp/10;
int k = 0;
while(add!=0 && i+j-k>=0){
int temp2 = res[i+j-k]-'0'+add;
res[i+j-k] = temp2 %10 +'0';
add = temp2/10;
++k;
}
}
}
for(int i=0;i<m+n;++i){
if(res[i]!='0')
return res.substr(i,m+n-i+1);
}
return "0";
}
}; class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
// write code here
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
vector<int> num1, num2;
for (const auto& c : s) num1.push_back(c - '0');
for (const auto& c : t) num2.push_back(c - '0');
vector<int> ans(num1.size() + num2.size() + 1, 0);
for (int i = 0; i < num1.size(); i++) {
for (int j = 0; j < num2.size(); j++) {
ans[i + j] += num1[i] * num2[j];
}
}
string ret;
for (int i = 0; i < num1.size() + num2.size(); i++) {
if (ans[i] <= 0) break;
if (ans[i] > 10) {
ans[i + 1] += ans[i] / 10;
ans[i] = ans[i] % 10;
}
ret.push_back(ans[i] + '0');
}
reverse(ret.begin(), ret.end());
if (ret.empty()) return "0";
return ret;
}
};
来看看我丑陋的代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
private static final int MAXN = 20010;
private Complex[] x1 = new Complex[MAXN];
private Complex[] x2 = new Complex[MAXN];
private int[] sum = new int[MAXN];
StringBuffer sb = new StringBuffer();
private static final double pi = Math.acos(-1.0);
private static class Complex{
private double x;
private double y;
public Complex(double x,double y){
this.x = x;
this.y = y;
}
public Complex add(Complex o1,Complex o2){
return new Complex(o1.x+o2.x,o1.y+o2.y);
}
public Complex subtract(Complex o1,Complex o2){
return new Complex(o1.x-o2.x,o1.y-o2.y);
}
public Complex multiply(Complex o1,Complex o2){
return new Complex(o1.x*o2.x-o1.y*o2.y,o1.y*o2.x+o1.x*o2.y);
}
}
public void change(Complex[] y,int len){
int i,j,k;
for(i=1,j=len/2;i<len-1;i++){
if(i<j){
Complex tem =y[i];
y[i] = y[j];
y[j] = tem;
}
k = len/2;
while (j>=k){
j-=k;
k/=2;
}
if(j<k) j+=k;
}
}
public void fft(Complex[] y,int len,int on){
change(y,len);
for(int h=2;h<=len;h<<=1){
Complex wn = new Complex(Math.cos(-on*2*pi/h),Math.sin(-on*2*pi/h));
for(int j=0;j<len;j+=h){
Complex w = new Complex(1,0);
for(int k=j;k<j+h/2;k++){
Complex u = y[k];
Complex t = w.multiply(w,y[k+h/2]);
y[k] = u.add(u,t);
y[k+h/2] = u.subtract(u,t);
w = w.multiply(w,wn);
}
}
}
if(on==-1){
for(int i=0;i<len;i++)
y[i].x/=len;
}
}
public String solve (String s, String t) {
int len1 = s.length();
int len2 = t.length();
int len=1;
while (len<len1*2||len<len2*2)
len<<=1;
for(int i=0;i<len1;i++)
x1[i] = new Complex(s.charAt(len1-i-1)-'0',0);
for(int i=len1;i<len;i++)
x1[i] = new Complex(0,0);
for(int i=0;i<len2;i++)
x2[i] = new Complex(t.charAt(len2-i-1)-'0',0);
for(int i=len2;i<len;i++)
x2[i] = new Complex(0,0);
fft(x1,len,1);
fft(x2,len,1);
for(int i=0;i<len;i++)
x1[i] = x1[i].multiply(x1[i],x2[i]);
fft(x1,len,-1);
for(int i=0;i<len;i++)
sum[i] = (int)(x1[i].x+0.5);
for(int i=0;i<len;i++){
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
len = len1+len2-1;
while (sum[len]<=0&&len>0)
len--;
for(int i=len;i>=0;i--)
sb.append(sum[i]);
return sb.toString();
}
} import java.util.*;
public class Solution {
public static String solve (String s, String t) {
// 数字数组,高位在数组左,低位在数组右,处理时需注意
int[] arrOne = new int[s.length()];
for(int i = 0 ; i < s.length() ; i++){
arrOne[i] = s.charAt(i) - '0';
}
int[] arrTwo = new int[t.length()];
for(int i = 0 ; i < t.length() ; i++){
arrTwo[i] = t.charAt(i) - '0';
}
return getRes(arrOne,arrTwo);
}
public static String getRes(int[] arrOne,int[] arrTwo){
int lenOne = arrOne.length;
int lenTwo = arrTwo.length;
// 开辟结果数组,结果长度至多为 lenOne + lenTwo
int[] result = new int[lenOne + lenTwo];
// 开始计算,先不考虑进位,每次结果存在result[i + j + 1]位置
// 为什么是i + j + 1?
// 因为结果数组计算处理高位在数组左,低位在数组右。i+j+1实际上是往低位存,这样后面进位处理才正确
for(int i = 0; i< lenOne ; i++){
for(int j = 0 ; j < lenTwo ; j++){
// !!!这里是i + j + 1这样最后的进位才能正确计算
result[i + j + 1] += arrOne[i] * arrTwo[j];
}
}
// 计算该位进位和结果数,从最低位(数组末尾)开始向前计算
int carry = 0;
for(int i = result.length - 1 ; i >= 0 ; i--){
int sum = carry + result[i];
result[i] = sum % 10;
carry = sum / 10;
}
// 转为String,需要无视前置0,如果最终builder长度为0,则代表输入类似"0" "0"的用例,结果应该输出“0”
StringBuilder builder = new StringBuilder();
int curPos = 0;
while(curPos < result.length && result[curPos] == 0){
curPos++;
}
for(int i = curPos ; i < result.length ; i++){
builder.append(result[i]);
}
return builder.length() != 0 ? builder.toString() : "0";
}
} import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// 如果有一个数为0,乘积就是0
if (s.equals("0") || t.equals("0")) {
return "0";
}
int m = s.length();
int n = t.length();
// 用于存储乘积的结果
int[] result = new int[m + n];
// 从最低位到最高位逐位相乘
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (s.charAt(i) - '0') * (t.charAt(j) - '0');
int p1 = i + j;
int p2 = i + j + 1;
int sum = mul + result[p2];
result[p2] = sum % 10;
result[p1] += sum / 10;
}
}
// 将结果数组转换为字符串
StringBuilder sb = new StringBuilder();
for (int num : result) {
// 跳过前导零
if (!(sb.length() == 0 && num == 0)) {
sb.append(num);
}
}
return sb.length() == 0 ? "0" : sb.toString();
}
} class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
if(s=="0" || t=="0"){
return "0";
}
string ans(s.length()+t.length(), '0');
int carry=0;
for(int i=0;i<s.length();i++){
for(int j=0;j<t.length();j++){
char tmp = ans[ans.length()-1-j-i];
ans[ans.length()-1-i-j] = ((s[s.length()-1-i]-'0')*(t[t.length()-1-j]-'0')+tmp-'0'+carry)%10+'0';
carry = ((s[s.length()-1-i]-'0')*(t[t.length()-1-j]-'0')+tmp-'0'+carry)/10;
}
ans[ans.length()-1-i-t.length()] = carry+'0';
carry = 0;
}
int mark = 0;
while(mark<ans.length()-1 && ans[mark]=='0'){
mark++;
}
return ans.substr(mark);
}
}; class Solution: def solve(self , s , t ): # write code here def multiply(a, b): b = int(b) res, carry = "", 0 for c in a: tmp = int(c) * b + carry res += str(tmp % 10) carry = tmp // 10 if carry: res += str(carry) return res s, t = s[::-1], t[::-1] if len(s) < len(t): n1, n2 = t, s else: n1, n2 = s, t res = [] for c in n2: tmp = multiply(n1, c) res.append(int(tmp[::-1])) ans = 0 for num in res[::-1]: ans = 10*ans + num return str(ans)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
string solve(string s, string t) {
// write code here
int n1=s.size();int n2=t.size();
string res(n1+n2,'0');
for(int i=n1-1;i>=0;i--)
{
for(int j=n2-1;j>=0;j--)
{
int temp=res[i+j+1]-'0'+(s[i]-'0')*(t[j]-'0');
res[i+j+1]=temp%10+'0';
res[i+j]+=temp/10;
}
}
for(int i=0;i<n1+n2;i++)
{
if(res[i]!='0')
return res.substr(i);
}
return "0";
}
}; class Solution: def solve(self , s: str, t: str) -> str: # write code here s_val = eval(s) t_val = eval(t) result = s_val*t_val return str(result)eval可以返回真实值,比使用int更好
import java.util.*;
import java.math.BigDecimal;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
return new BigDecimal(t).multiply(new BigDecimal(s)).toPlainString();
}
}