[Leetcode] Multiply String and Big Interger 大数乘法加法减法

news/2024/2/29 2:32:17

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.

模拟乘法

复杂度

时间 O(NM) 空间 O(N+M)

思路

这题的技巧在于复用同一个结果数组存放上次的计算结果。因为被乘数每一位数字和乘数相乘的结果是依次错开的,所以就没问题。

注意

  • 转换回String前要先把前面的0去掉,但第一位的0不去掉

代码

public class Solution {public String multiply(String num1, String num2) {if(num1 == null || num2 == null) return null;int len1 = num1.length(), len2 = num2.length();// 结果的位数最多可能是两个乘数位数之和int len3 = len1 + len2;int[] res = new int[len3];int carry = 0, i = 0, j = 0;for(i = len1 - 1; i >= 0; i--){// 先置carry位为0carry = 0;for(j = len2 - 1; j >= 0; j--){// 每一位的乘积,等于之前这一位的结果,加上carry,再加上这一位和乘数的乘积int product = carry + res[i + j + 1] + (num1.charAt(i) - '0')*(num2.charAt(j) - '0');res[i + j + 1] = product % 10;carry = product / 10;}// 把最后的carry位加上res[i + j + 1] = carry;}StringBuilder resstr = new StringBuilder();i = 0;// 跳过前面无用的0while(i < len3 - 1 && res[i] == 0){i++;}for(; i < len3; i++){resstr.append(res[i]);}return resstr.toString();}
}

Add Two Strings

模拟加法

复杂度

时间 O(N) 空间 O(N)

思路

从后向前模拟加法

代码

private String addString(String num1, String num2){int i = num1.length() - 1, j = num2.length() - 1;int k = Math.max(i, j);int[] num3 = new int[k + 1];int sum = 0, carry = 0;while(i >= 0 || j >= 0){// 加数的位int d1 = i >= 0 ? (num1.charAt(i) - '0') : 0; // 被加数的位int d2 = j >= 0 ? (num2.charAt(j) - '0') : 0;sum = d1 + d2 + carry;num3[k] = sum % 10;carry = sum / 10;k--;i--;j--;}StringBuilder sb = new StringBuilder();// 如果最后还有进位要加上if(carry != 0) sb.append(carry);for(int digit : num3){sb.append(digit);}return sb.toString();
}

有符号加法

思路

有符号的话,就要根据符合判断具体的操作

  • 如果都是负数,则结果是两个绝对值相加再取负

  • 如果一个是负数一个正数,则结果是(正数)减去(负数的绝对值),这里要用到减法

  • 如果都是正数则直接相加

代码

private static String addSignedString(String num1, String num2){int sign1 = 1, sign2 = 1;if(num1.charAt(0) == '-'){sign1 = -1;num1 = num1.substring(1);}if(num2.charAt(0) == '-'){sign2 = -1;num2 = num2.substring(1);}if(sign1 == sign2){String res = addString(num1, num2);return sign1 == -1 ? "-" + res : res;} else {if(sign1 == 1){return subString(num1, num2);} else {return subString(num2, num1);}}
}

Substract Two Strings

模拟减法

复杂度

时间 O(N) 空间 O(N)

思路

从后向前模拟减法,计算每一位的值时,用减数的位减去被减数,再加上10,再减去借位,结果模上10就行了。借位则是看之前的结果是否小于10,如果小于10说明借位了。不过要注意的是,我们要用较大的数减去较小的数,如果减数反而较大,我们要用减数减去被减数,然后结果加上负号。判断两个数的大小的方法,是先判断其长度,如果长度不一样,则较长的较大,如果长度一样,则需要比较每一位。

代码

private static String subString(String num1, String num2){int len1 = num1.length(), len2 = num2.length();// 根据两数的大小关系,决定是直接相减,还是反过来相减取负if(len1 > len2){return coreSub(num1, num2);} else if (len1 < len2){return "-"+coreSub(num2, num1);} else {int compare = num1.compareTo(num2);if(compare > 0){return coreSub(num1, num2);} else if(compare < 0){return "-"+coreSub(num2, num1);} else {return "0";}}
}private static String coreSub(String num1, String num2){int i = num1.length() - 1, j = num2.length() - 1;int[] num3 = new int[i + 1];int diff = 0, borrow = 0;while(i >= 0){int d1 = num1.charAt(i) - '0';int d2 = j >= 0? num2.charAt(j) - '0': 0;// 计算差值时要先加上10diff = d1 + 10 - borrow - d2;num3[i] = diff % 10;borrow = diff < 10 ? 1 : 0;i--;j--;}i = 0;while(num3[i] == 0){i++;}StringBuilder sb = new StringBuilder();while(i < num3.length){sb.append(num3[i]);i++;}return sb.toString();
}

有符号减法

代码

private static String subSignedString(String num1, String num2){int sign1 = 1, sign2 = 1;if(num1.charAt(0) == '-'){sign1 = -1;num1 = num1.substring(1);}if(num2.charAt(0) == '-'){sign2 = -1;num2 = num2.substring(1);}if(sign1 == sign2){// 都是正数则直接相减if(sign1 == 1){return subString(num1, num2);// 都是负数则后面减去前面} else {return subString(num2, num1);}} else {// 前正后负则相加if(sign1 == 1){return addString(num1, num2);// 前负后正则相加后取负} else {return "-"+addString(num1, num2);}}
}

https://www.jiucaihua.cn/news/show-3196935.html

相关文章

InvocationHandler实现类中的invoke方法为什么会被自动执行

一&#xff1a;首先需要明确的是动态代理中&#xff0c;InvocationHandler实现类并不是代理类&#xff0c;只是代理类与被代理类的一个中间类&#xff0c;该类只是用来做功能增强的&#xff0c;这也是动态代理能够解耦的原因 二&#xff1a;动态代理中的代理类是通过Proxy.newI…

MyBatis框架中sql语句的执行过程

一&#xff1a;概述 主要思路&#xff1a;dom4j解析配置文件生成一个全局配置对象&#xff0c;利用jdk动态代理创建出接口的代理类&#xff0c;通过代理类完成crud的操作&#xff0c;从而间接完成接口方法中的crud操作&#xff08;代理通过以接口方法名为id就可以拿到对应的sql…

对数据库事务的总结

一&#xff1a;事务的概念 所谓事务&#xff0c;即一件事&#xff0c;那么完成一件事肯定有很多个步骤&#xff0c;所以事务实际就是很多个步骤的集合。即事务实际就是增删改等一系列数据库操作的集合 二&#xff1a;事务的四大特性&#xff08;ACID&#xff09; 1.原子性:集…

Oracle Weblogic 重置密码的方法

为什么80%的码农都做不了架构师&#xff1f;>>> 原文地址 Shut down the WebLogic domain, the managed servers, Admin Server and Node Manager.Set the following environment variables in the command prompt (cmd) to help you navigate easily, in my case …

单片机_CT107D训练平台电路原理图\蓝桥杯训练板\ 存储/IO 扩展模块\ 8255 扩展芯片\EEPROM 芯片 AT24C02\

存储/IO 扩展 8255 扩展芯片原理图&#xff1a; 8255芯片是Intel公司生产的可编程并行I/O接口芯片&#xff0c;有3个8位并行I/O口。具有3个通道3种工作方式的可编程并行接口芯片&#xff08;40引脚&#xff09;。 其各口功能可由软件选择&#xff0c;使用灵活&#xff0c;通用性…

老鸟手把手教你利用linux技能追求女孩子

看老男孩老师教你用linux技能追求女孩子实践1.首先要确定想发的情书内容&#xff0c;也可以准备多封每天一封。2、注册邮件账号或使用已有的&#xff0c;配置Linux客户端邮件发送功能[rootoldboy ~]# tail -1 /etc/mail.rc set fromxiaxia_5321163.com smtpsmtp.163.comsmtp-au…

Swing编程基础 之五

按钮控件实例&#xff1a; 一、JButton package cn.tl.buttontest;import java.awt.*; import javax.swing.*;public class Button1 {static final int WIDTH 300;static final int HEIGHT 200;public static void main(String[] args) {//创建顶层框架类&#xff08;设置标题…

再造 “手机QQ” 侧滑菜单(三)——视图联动

代码示例&#xff1a;https://github.com/johnlui/SwiftSideslipLikeQQ 本 文中&#xff0c;我们将一起使用 UINavigationController 来管理主视图&#xff0c;并实现点击左视图中菜单时&#xff0c;主视图自动联动的功能。本文是本系列文章的终结篇&#xff0c;也是最有难度的…

java中接口与父类的妙用(模板方法模式)

之前的博客中已经详细说明了接口&#xff0c;抽象类&#xff0c;普通类以及实例的作用了&#xff0c;该文章用现实中的例子来更好地了解这些关系&#xff0c;但是实际编码中&#xff0c;好处究竟在哪里呢&#xff1f; 接口&#xff0c;继承父类等设计&#xff0c;都是为了面向…

PLSQL_统计信息系列03_统计信息的收集

20150506 Created By Baoxinjian 一、摘要 二、通过工具包dbms_stats 1. 通过工具包dbms_stats 2. 配置dbms_stats 2. 配置dbms_stats 3. 使用待定的统计信息 3. 使用待定的统计信息 4. 调度收集统计信息 4. 调度收集统计信息 Thanks and Regards 转载于:https://www.cnblogs.c…