以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
数据范围： 读入的数字大小满足 
要求：空间复杂度 )
，时间复杂度 )
（假设m是n的长度）
[编程题]大数乘法
public String solve (String s, String t) {
// write code here
StringBuilder res=new StringBuilder();
int ls=s.length() ,lt=t.length();
int[] nums=new int[ls+lt-1];// 代表后面几个0，m+n最多m+n-2个0，但是还有0个0
for(int i=0;i<ls;i++){
for(int j=0;j<lt;j++){
nums[i+j]+=(s.charAt(i)-'0')*(t.charAt(j)-'0'); // 注意是+=
}
}
int sum=0;
for(int i=nums.length-1;i>=0;i--){
sum+=nums[i];
res.append(sum%10);
sum/=10;
}
while(sum>0){
res.append(sum%10);
sum/=10;
}
return res.charAt(0)=='0'?"0":res.reverse().toString();
}
编辑于 2024-03-10 12:57:17
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
String result = "";
for (int idx = 0; idx < t.length(); idx++) {
char ch = t.charAt(t.length() - 1 - idx);
int val = Integer.valueOf(ch + "");
String str = multiply(s, val, idx);
result = add(str, result);
}
return result;
}
public String multiply(String s, int t, int pow) {
StringBuffer strBuf = new StringBuffer();
int[] carry = new int[s.length() + 2];
for (int idx = 0; idx < s.length(); idx++) {
char ch = s.charAt(s.length() - 1 - idx);
int val = Integer.valueOf(ch + "");
int res = t * val;
res += carry[s.length() - idx - 1];
if (res < 10) {
strBuf.append(res);
} else {
carry[s.length() - idx] = res / 10;
strBuf.append(res % 10);
}
}
String result = strBuf.reverse().toString();
for (int idx = 0; idx < pow; idx++) {
result += "0";
}
return result;
}
public String add(String self, String other) {
StringBuffer strBuf = new StringBuffer();
int[] carry = new int[Math.max(self.length(), other.length()) + 1];
int min = Math.min(self.length(), other.length());
for (int idx = 0; idx < min; idx++) {
char chSelf = self.substring(self.length() - min).charAt(min - 1 - idx);
char chOther = other.substring(other.length() - min).charAt(min - 1 - idx);
int valSelf = Integer.valueOf(chSelf + "");
int valOther = Integer.valueOf(chOther + "");
int res = valSelf + valOther;
res += carry[idx];
if (res < 10) {
strBuf.append(res);
} else {
carry[idx + 1] = res / 10;
strBuf.append(res % 10);
}
}
if (self.length() > other.length()) {
for (int idx = min; idx < self.length(); idx++) {
char chSelf = self.charAt(self.length() - 1 - idx);
int valSelf = Integer.valueOf(chSelf + "");
int res = valSelf;
res += carry[idx];
if (res < 10) {
strBuf.append(res);
} else {
carry[idx + 1] = res / 10;
strBuf.append(res % 10);
}
}
if (carry[self.length()] > 0) {
strBuf.append(carry[self.length()]);
}
} else {
for (int idx = min; idx < other.length(); idx++) {
char chOther = other.charAt(other.length() - 1 - idx);
int valOther = Integer.valueOf(chOther + "");
int res = valOther;
res += carry[idx];
if (res < 10) {
strBuf.append(res);
} else {
carry[idx + 1] = res / 10;
strBuf.append(res % 10);
}
}
if (carry[other.length()] > 0) {
strBuf.append(carry[other.length()]);
}
}
String result = strBuf.reverse().toString();
return result;
}
}
发表于 2023-05-08 11:14:37
回复(0)
import java.util.*;
import java.math.BigDecimal;
public class Solution {
public String solve (String s, String t) {
BigDecimal numS = new BigDecimal(s);
BigDecimal numT = new BigDecimal(t);
BigDecimal res = numS.multiply(numT);
return res.toString();
}
}
为啥老喜欢考数学？
为啥老喜欢考数学？
有意思吗？
发表于 2023-04-25 10:25:55
回复(0)
模拟乘法流程，先一位位相乘，再相加
public String solve (String s, String t) {
// write code here
if(s.equals("0") || t.equals("0")) return "0";
List<String> list = new ArrayList<>();
for(int i=t.length() - 1;i >= 0;i--){
String tmp = mul(t.charAt(i),s);
for(int j=t.length() - 1;j > i;j--){
tmp += "0";
}
list.add(tmp);
}
String res = "";
for(String k : list){
res = add(res,k);
}
return res;
}
public String mul(char ch,String s){
StringBuilder sb = new StringBuilder();
int c = 0;
for(int i = s.length()-1 ; i >= 0;i --){
char t = s.charAt(i);
int res = (t - '0') * (ch - '0') + c;
c = res / 10;
char a = (char)(res % 10 + '0');
sb.append(a);
}
if(c != 0) sb.append((char)(c+'0'));
return sb.reverse().toString();
}
public String add(String a,String b){
int c = 0;
int i = a.length() - 1;
int j = b.length() - 1;
StringBuilder sb = new StringBuilder();
while(i >= 0 || j >=0){
int av = i < 0 ? 0 : a.charAt(i) - '0';
int bv = j < 0 ? 0 : b.charAt(j) - '0';
int res = av + bv + c;
c = res / 10;
char t = (char)(res % 10 + '0');
sb.append(t);
i --;
j --;
}
if(c != 0){
sb.append((char)(c + '0'));
}
return sb.reverse().toString();
}
发表于 2023-03-14 17:39:41
回复(0)
暴力的做法
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
if(t.equals("0")||s.equals("0"))return "0";
char[] s2c = s.toCharArray();
char[] t2c = t.toCharArray();
if (s2c.length > t2c.length) {
return multiply(s2c, t2c);
} else {
return multiply(t2c, s2c);
}
}
public String add(char[] s, char[] t) {
StringBuilder sb = new StringBuilder();
int index = 0;
int l = s.length - 1, r = t.length - 1;
while (index != 0 || l >= 0 || r >= 0) {
int t1 = l >= 0 ? s[l--] - '0' : 0;
int t2 = r >= 0 ? t[r--] - '0' : 0;
sb.append((t1 + t2 + index) % 10);
index = (t1 + t2 + index) / 10;
}
return sb.reverse().toString();
}
public String multiply(char[] s, char t, int i) {
int r1 = t - '0';
int index = 0;
int l = s.length - 1;
StringBuilder sb = new StringBuilder();
while (l >= 0 || index != 0) {
int t1 = l >= 0 ? s[l--] - '0':0;
int t2 = t1 * r1 + index;
sb.append(t2 % 10);
index = t2 / 10;
}
sb = sb.reverse();
int temp = i;
for (int j = 0; j < i; j++)sb.append('0');
return sb.toString();
}
public String multiply(char[] s, char[] t) {
String res = "0";
for (int j = 0; j < t.length; j++) {
String temp = multiply(s, t[t.length - 1 - j], j);
res = add(res.toCharArray(), temp.toCharArray());
}
return res;
}
}
发表于 2022-07-25 22:43:34
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
if("0".equals(s)||"0".equals(t)) return "0";
// write code here
int len1 = s.length();
int len2 = t.length();
//s乘t结果长度不超过s.len+t.len
int[] ans = new int[len1+len2+1];
int pre = 0;
//从s低位开始遍历，分别与t各个位置相乘，将各个位置相乘的结果加入ans当中
for(int i = len1-1;i>=0;i--){
int l = Integer.parseInt(s.charAt(i)+"");
//从小遍历t当中各个位置的数字与s相应位置相乘，填入ans对应位置
for(int j = len2-1;j>=0;j--){
int r = Integer.parseInt(t.charAt(j)+"");
int num = l*r+pre+ans[len1-1-i+len2-1-j];
//当前位置的值加上乘积在当前位置的值
ans[len1-1-i+len2-1-j] = num%10;
//当前位置的进位
pre = num/10;
}
//可能当前s的i位置乘完t后有进位，继续向后加
int index = 0;
while(pre!=0){
int tt = ans[len1-1-i+len2+index];
ans[len1-1-i+len2+index] = (tt+pre)%10;
pre = (tt+pre)/10;
index++;
}
}
//ans数组当中右边为高位，避免高位出现0所以找出高位非0的位置
int pos = len1+len2;
while(pos>=0&&ans[pos--]==0){}
StringBuilder sb = new StringBuilder();
//返回左边为高位的答案
for(int i = pos+1;i>=0;i--){
sb.append(ans[i]);
}
return sb.toString();
}
}
发表于 2022-07-15 13:25:22
回复(0)
public String solve (String s, String t) {
// write code here
if(s.equals("0") || t.equals("0"))
return "0";
int list[] = new int[s.length() + t.length() - 1];
for(int i = s.length() - 1; i >= 0; i--) {
for(int j = t.length() - 1; j >= 0; j--) {
int cur = (s.charAt(i) - '0') * (t.charAt(j) - '0');
list[i + j] += cur;
}
}
int res = 0;
StringBuilder ans = new StringBuilder();
for(int i = list.length - 1; i >= 0; i--) {
int cur = list[i] + res;
res = cur / 10;
ans.append(String.valueOf(cur % 10));
}
if (res > 0) {
ans.append(String.valueOf(res));
}
return ans.reverse().toString();
}
发表于 2022-02-06 09:06:53
回复(0)
先将所有位置的值算出来，不考虑进位，最后统一进位
public String solve (String s, String t) {
if (s.equals("0") || t.equals("0")) {return "0";}
int[] res = new int[s.length() + t.length()];
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = t.length() - 1; j >= 0; j--) {
res[i + j +1] += (s.charAt(i) - '0') * (t.charAt(j) - '0');
}
}
String[] test = new String[s.length() + t.length()];
int jin = 0;
for (int i = res.length -1; i >= 0; i--) {
int temp = res[i] + jin;
jin = temp / 10;
test[i] = "" + temp % 10;
}
String result = "";
if (jin != 0 ) {
result += jin;
}
if (!test[0].equals("0")) {
result += test[0];
}
for (int i = 1; i < test.length; i++) {
result += test[i];
}
return result;
}
发表于 2022-01-23 00:25:24
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
int lenS = s.length(), lenT = t.length();
if (lenS == 0 || lenT == 0) return null;
// 将字符串转为整数数组
int[] arrS = new int[lenS], arrT = new int[lenT];
for (int i = 0; i < lenS; ++ i) arrS[i] = (s.charAt(i) - '0');
for (int i = 0; i < lenT; ++ i) arrT[i] = (t.charAt(i) - '0');
// 计算每位乘积的结果，存入数组
int[] arr = new int[lenS + lenT];
for (int i = 0; i < lenS; ++ i){
for (int j = 0; j < lenT; ++ j){
arr[i + j + 1] += arrS[i] * arrT[j];
}
}
// 得出最终的结果，从后向前处理每位的结果
StringBuffer res = new StringBuffer();
int carry = 0;
for (int i = lenS + lenT - 1; i > 0; -- i){
int num = arr[i] + carry;
res.insert(0,num % 10);
carry = num / 10;
}
if (carry > 0) res.insert(0, carry);
return res.toString();
}
}
// 方法一：不转为整数，直接处理字符串
public String solve (String s, String t) {
// 计算2个整数的乘积
int n1 = s.length(), n2 = t.length();
if (n1 == 0 || n2 == 0) return null;
String[] arr = new String[n2];
// 进位
int count = 0;
// 计算每位相乘的结果，翻转后，放入数组中
for (int i = 0; i < n2; ++ i){
StringBuffer sb = new StringBuffer();
int num = t.charAt(n2-1-i) - '0';
for (int j = n1-1; j >= 0; -- j){
int temp = num * (s.charAt(j) - '0') + count;
sb.append(temp % 10);
count = temp / 10;
}
if (count > 0) sb.append(count);
count = 0;
// 放入数组之前，先左移 i位
int k = i;
while (k > 0) {
sb.insert(0, '0');
-- k;
}
arr[i] = sb.toString();
}
// 将数组中，每位相乘的结果相加，得出最终结果
StringBuffer res = new StringBuffer();
int n = arr.length;
int m = arr[n-1].length();
count = 0;
for (int i = 0; i < m; ++ i){
int num = 0;
for (int j = 0; j < n; ++ j){
if (i >= arr[j].length()) continue;
num += arr[j].charAt(i) - '0';
}
num += count;
res.insert(0,num % 10);
count = num / 10;
}
if (count > 0) res.append(count);
return res.toString();
}
发表于 2021-12-17 16:46:35
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public static String solve(String s, String t) {
int sl = s.length();
int tl = t.length();
int[] ints = new int[sl + tl];
ArrayList<Integer> res = new ArrayList<>();
int k = 0;
for (int i = sl - 1; i >= 0; i--) {
k = sl - i - 1;
for (int j = tl - 1; j >= 0; j--) {
ints[k] += (s.charAt(i) - '0') * (t.charAt(j) - '0');
k++;
}
}
for (int i = 0; i < ints.length; i++) {
if (ints[i] > 9) {
ints[i + 1] += (ints[i] / 10);
ints[i] = ints[i] % 10;
}
}
String result = "";
for (int i = ints.length - 1; i >= 0; i--) {
result += ints[i];
}
String substring = "0";
for (int j = 0; j < result.length(); j++) {
if (result.charAt(j) != '0') {
substring = result.substring(j, result.length());
break;
}
}
return substring;
}
}
发表于 2021-12-13 10:57:09
回复(0)
超过了0.29%的人。。。我还是我
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
public String solve (String s, String t) {
// write code here
if(s.equals("0") || t.equals("0")) return "0";
int carry = 0;
int index = 0; // 记录计算乘法时，层数
Deque<String> cache = new ArrayDeque<String>();
for(int i=s.length()-1;i>=0;i--){
int a = s.charAt(i)-'0';
String temp = "";
for(int j=t.length()-1;j>=0;j--){
int b = t.charAt(j)-'0';
temp = (a*b+carry)%10+temp;
carry = (a*b+carry)/10;
}
int zeroNum = index;
while(zeroNum-- > 0){
temp += "0";
}
temp = carry!=0?carry + temp : temp;
carry = 0;
cache.offer(temp);
index++;
}
// 将cache中的所有数加起来，按照大数加法的方式
return BigNumberAdd(cache);
}
public String BigNumberAdd(Deque<String> numbers){
while(numbers.size()>1){
String first = numbers.poll();
String second = numbers.poll();
String ans = GetNumber(first, second);
numbers.offer(ans);
}
return numbers.poll();
}
public String GetNumber(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算完以后的答案需要翻转过来
ans.reverse();
return ans.toString();
}
}
发表于 2021-11-22 10:48:07
回复(0)
public class Solution {
public String solve (String s, String t) {
// write code here
ArrayList<String> list = new ArrayList<>();
for(int i = s.length()-1; i >= 0; i--){
list.add(muti(s.charAt(i),t,s.length()-1-i));
}
return add(list);
}
public String muti(char c,String str,int zeros){
int num1 = c-'0';
int remain = 0;
StringBuffer res = new StringBuffer();
while(zeros-- > 0){
res.append("0");
}
for(int i = str.length()-1; i >= 0; i--){
int num2 = str.charAt(i)-'0';
res.append(String.valueOf((num1*num2+remain)%10));
remain = (num1*num2+remain)/10;
}
if(remain != 0){
res.append(String.valueOf(remain));
}
return res.toString();
}
public String add(ArrayList<String> list){
int index = 0;
int remain = 0;
StringBuffer res = new StringBuffer();
while(index < list.get(list.size()-1).length() || remain != 0){
int sum = 0;
for(int i = 0;i < list.size(); i++){
if(index < list.get(i).length()){
sum = sum + list.get(i).charAt(index) - '0';
}else{
continue;
}
}
res.append(String.valueOf((sum+remain)%10));
remain = (sum+remain)/10;
index++;
}
return res.reverse().toString();
}
}
public String solve (String s, String t) {
// write code here
ArrayList<String> list = new ArrayList<>();
for(int i = s.length()-1; i >= 0; i--){
list.add(muti(s.charAt(i),t,s.length()-1-i));
}
return add(list);
}
public String muti(char c,String str,int zeros){
int num1 = c-'0';
int remain = 0;
StringBuffer res = new StringBuffer();
while(zeros-- > 0){
res.append("0");
}
for(int i = str.length()-1; i >= 0; i--){
int num2 = str.charAt(i)-'0';
res.append(String.valueOf((num1*num2+remain)%10));
remain = (num1*num2+remain)/10;
}
if(remain != 0){
res.append(String.valueOf(remain));
}
return res.toString();
}
public String add(ArrayList<String> list){
int index = 0;
int remain = 0;
StringBuffer res = new StringBuffer();
while(index < list.get(list.size()-1).length() || remain != 0){
int sum = 0;
for(int i = 0;i < list.size(); i++){
if(index < list.get(i).length()){
sum = sum + list.get(i).charAt(index) - '0';
}else{
continue;
}
}
res.append(String.valueOf((sum+remain)%10));
remain = (sum+remain)/10;
index++;
}
return res.reverse().toString();
}
}
发表于 2021-08-22 21:33:42
回复(0)
利用乘法性质+归并。不过时间复杂度真的高。。。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
* 思路：一个作为乘数，一个作为被乘数，然后从最后一位
*/
public String solve (String s, String t) {
// write code here
// 使用乘法法则，得到t的每一位乘以s得到的数字字符串
List<String> res = new ArrayList<>();
int cur = 0;
int carry = 0;
for(int i=t.length()-1;i>=0;i--){
StringBuilder sb = new StringBuilder();
int numA = t.charAt(i)-'0';
for(int j=s.length()-1;j>=0;j--){
int numB = s.charAt(j)-'0';
int sum = numA*numB+carry;
cur = sum%10;
carry = sum/10;
sb.append(cur);
}
if(carry!=0){
sb.append(carry);
}
sb = sb.reverse();
// 拼接0
for(int k=0;k<t.length()-1-i;k++){
sb.append(0);
}
// 添加进入列表
res.add(sb.toString());
// cur,carray设置为初始值
cur = 0;
carry = 0;
}
// 归并排序，进行数字的两两相加
return divide(res,0,res.size()-1);
}
public String divide(List<String> res,int left,int right){
if(left == right){
return res.get(left);
}
int mid = (left+right)/2;
String s1 = divide(res,left,mid);
String s2 = divide(res,mid+1,right);
return mergeInto(s1,s2);
}
public String mergeInto(String s1,String s2){
int cur = 0;
int carry = 0;
int i = s1.length()-1;
int j = s2.length()-1;
StringBuilder sb = new StringBuilder();
while(i>=0 || j>=0){
int numA = i>=0?s1.charAt(i)-'0':0;
int numB = j>=0?s2.charAt(j)-'0':0;
int sum = numA+numB+carry;
cur = sum%10;
carry = sum/10;
sb.append(cur);
i--;
j--;
}
if(carry!=0){
sb.append(carry);
}
return sb.reverse().toString();
}
}
发表于 2021-07-16 00:20:37
回复(0)
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();
}
}
发表于 2021-04-14 22:32:45
回复(0)
import java.util.*;
public class Solution {
public String solve(String s, String t) {
// write code here
int index = s.length() + t.length();
int[] res = new int[index + 1];
for(int i = s.length() - 1; i >= 0; i--){
int tempS = s.charAt(i) - '0'; // 获取每一位
int in = 0;
for(int j = t.length() - 1; j >= 0; j--){
int tempT = t.charAt(j) - '0';
res[index - in++] += tempS * tempT; // 临时保存每一位相乘的结果
}
index--;
}
for(int i = s.length() + t.length(); i > 0; i--){ // 处理每一位中大于个位数的情况
int temp = res[i] / 10;
res[i] %= 10;
res[i - 1] += temp;
}
boolean start = false;
StringBuilder resStr = new StringBuilder();
for(int i = 0; i <= s.length() + t.length(); i++){ // 拼接，处理前导0
if(start || res[i] != 0){
start = true;
resStr.append(res[i]);
}
}
return resStr.length() > 0 ? resStr.toString() : "0";
}
}
编辑于 2021-04-08 15:51:01
回复(0)
问题信息
难度：
22条回答
438收藏
11714浏览
通过挑战的用户
查看代码-
2023-01-29 17:51:16
-
2022-10-13 11:31:59
-
2022-09-16 17:25:51
-
2022-09-16 10:43:13
-
2022-09-15 21:32:29
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
