【算法】字符串:高精度计算之加法、乘法(数组模拟)
目录
1、高精度算法是什么?
2、易错点
高精度加法:
高精度减法:
高精度乘法:
高精度除法:
3、高精度加法
思路:
例题
4、高精度乘法
思路
例题
参考文章
高精度算法——数组模拟(加、减、乘、除)_高精度数据计算算法有哪些-CSDN博客
高精度算法详解(加减乘除+高精度案例)-CSDN博客
1、高精度算法是什么?
- 在c++中int、long long int等存储方式只能计算十几位的整数运算,而当我们想要计算更多位时,就需要用到高精度算法。
- 高精度算法:它是处理大数字的数学计算方法,在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除等运算。
- 思想:
- 将这种大数字拆开,拆成一位一位的,这样可已输入位数很长的数,接下来将每一位取出,存入数组中 ,然后用一个数组去存储每个数字,最后再将数组进行相应的运算(加、减、乘、除、等)。
- 应用范围
- 高精度计算广泛应用于算法设计中,包括动态规划、数论、组合数学、几何算法等领域。许多经典算法问题,如大整数乘法、大整数除法、高精度加减法等都需要高精度计算来解决。
2、易错点
高精度加法:
倒叙输入,倒序输出,但中间是正着运算;
相加之后的进位处理;
高精度减法:考虑结果出现的正情况;
前导0的处理;
考虑减法的借位处理;
高精度乘法:倒叙输入,倒序输出,但中间是正着运算;
运算过程:使用无进位相乘,中间结果存到临时数组中,最后再处理进位。
前导0的处理(0被相乘)!!!容易被忽略;
可以将乘法单个位数相乘再转化成加法的思想;
此时题目中没有涉及到负数的情况。如出现负数,只需考虑两个字符串第一位是否为负号,然后结尾特殊判断一下即可;
高精度除法:(高精度÷低精度)
输入、计算、输出、需要同时逆序或同时正序;
前导0的处理!!!容易被忽略;
不能考虑进位的情况!!
3、高精度加法
思路:
1. 输入处理 - 将输入的两个高精度数以字符串的形式接收。
2.将字符串拆解为一个个数字存到int数组中(倒序存储在数组中,例如 string num1 ="123",存储为int n1[] = {3,2,1},方便按照正序计算)
3. 逐位相加 - 从低位(数组头部n1[0])开始,逐位将两个数的对应位数字相加,并加上前一 位的进位。 - 计算当前位的和,并计算进位。
4. 处理进位 - 如果当前位的和大于等于 10 ,则需要向高位进位。
5. 结果处理 - 去除结果前面(数组末尾)可能存在的多余的 0 。
例题
67. 二进制求和 - 力扣(LeetCode)
class Solution {
public:string addBinary(string a, string b) {//模拟列竖式计算过程int n = a.size() - 1, m = b.size() - 1;int tmp = 0;//存储临时结果,以及进位情况string ret;while (n >= 0 || m >= 0 || tmp){if (n >= 0) tmp += a[n--] - '0';if (m >= 0) tmp += b[m--] - '0';//取余ret += tmp % 2 + '0';//查看进位情况tmp /= 2;}reverse(ret.begin(),ret.end());return ret;}
};
4、高精度乘法
思路
- 准备工作:
- 获取输入的两个字符串
num1
和num2
的长度n
和m
,并创建一个长度为m + n
的整数数组t
用于存储中间结果(中间结果的个数最多是m+n个),将num1
和num2
反转(逆序输入),方便后续从低位到高位的计算。- 无进位相乘:
- 使用嵌套的
for
循环,将num1
的第i
位和num2
的第j
位相乘,将结果累加到t[i + j]
中,模拟乘法的竖式计算,此时不考虑进位。- 处理进位:
- 初始化进位
tmp
为 0 和当前位置cur
为 0,以及结果字符串ret
。在while
循环中,将tmp
累加上当前位置的中间结果t[cur]
(如果cur
未超出范围),将tmp
的个位数添加到ret
中并更新进位tmp
为除以 10 的结果。- 处理前导零:
- 去除结果字符串
ret
末尾的多余零(如果结果不是 0),最后将ret
反转回来得到最终结果。
例题
43. 字符串相乘 - 力扣(LeetCode)
class Solution {
public:string multiply(string num1, string num2) {int n = num1.size(), m = num2.size();//无进位相乘后相加,然后处理进位vector<int> t(m + n, 0);//存储中间结果reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//1.无进位相乘//tmp[0]存储个位数,tmp[1]存储十位数for (int i = 0; i < n; i++)//第二个乘数:456{for (int j = 0; j < m; j++)//第一个乘数:123{t[i + j] += (num1[i] - '0') * (num2[j] - '0');}}//2.处理进位int tmp = 0;//存储进位、临时结果int cur = 0;string ret;while (cur < m + n || tmp != 0){if (cur < m + n) tmp += t[cur++];ret += tmp % 10 + '0';//转换为字符,存储到答案集tmp /= 10;//进位计算}//3. 处理前导零while (ret.size() > 1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};
相关文章:
【算法】字符串:高精度计算之加法、乘法(数组模拟)
目录 1、高精度算法是什么? 2、易错点 高精度加法: 高精度减法: 高精度乘法: 高精度除法: 3、高精度加法 思路: 例题 4、高精度乘法 思路 例题 参考文章 高精度算法——数组模拟(加、减…...
4.JoranConfigurator解析logbak.xml
文章目录 一、前言二、源码解析GenericXMLConfiguratorlogback.xml解析通过SaxEvent构建节点model解析model节点DefaultProcessor解析model 三、总结 一、前言 上一篇介绍了logback模块解析logback.mxl文件的入口, 我们可以手动指定logback.xml文件的位置, 也可以使用其它的名…...
JavaWeb开发(十六)实战-生鲜后台管理系统(三)BeanUtils介绍、Servlet的抽取
1. 生鲜后台管理系统-BeanUtils的使用 1.1. BeanUtils介绍 BeanUtils 是 Apache commons组件的成员之一,主要用于简化JavaBean封装数据的操作。它可以给JavaBean封装一个字符串数据,也可以将一个表单提交的所有数据封装到JavaBean中。使用第三方工具&am…...
人形机器人将制造iPhone!
前言 优必选机器人和富士康通过一项突破性的合作伙伴关系,正在将先进的人形机器人(如Walker S1及其升级版Walker S2)整合到制造流程中,以改变iPhone的生产方式。这一合作旨在通过提升机器人能力、优化工作流程以及实现更智能的自动…...
Oracle 深入学习 Part 14:Managing Password Security and Resources(管理密码安全性和资源)
Profiles Profile 是一个以名称标识的集合,用于管理 密码 和 资源限制。 每个用户都对应一个profiles,可以通过 CREATE USER 或 ALTER USER 命令分配给用户。 Profiles 可以启用或禁用。 Profiles 可以关联到默认的 DEFAULT Profile。 密码管理&…...
202209 青少年软件编程等级考试C/C++ 二级真题答案及解析(电子学会)
第 1 题 统计误差范围内的数 统计一个整数序列中与指定数字m误差范围小于等于X的数的个数。 时间限制:5000 内存限制:65536 输入 输入包含三行: 第一行为N,表示整数序列的长度(N <= 100); 第二行为N个整数,整数之间以一个空格分开; 第三行包含2个整数,为指定…...
qt中透明度表示
透明度的表示方法 在 Qt 样式表中,使用 rgba 或 argb 颜色表示法时,透明度通常用一个介于 0 和 1 之间的小数表示。 rgba 表示法:rgba(red, green, blue, alpha),其中 alpha 是透明度,例如 rgba(255, 0, 0, 0.5) 表示…...
Mybatis 进阶 / Mybatis—Puls (详细)
目录 一.动态SQL 1.1标签 1.2 标签 1.3标签 1.4标签 1.5标签 1.6标签 mybatis总结: 二.Mybatis-Puls 2.1准备工作 2.2CRUD单元测试 2.2.1创建UserInfo实体类 2.2.2编写Mapper接⼝类 2.2.3 测试类 2.3 常见注解 2.3.1TableName 2.3.2TableField 2.4打印日…...
opencv在图片上添加中文汉字(c++以及python)
opencv在图片上添加中文汉字(c以及python)_c opencv绘制中文 知乎-CSDN博客 环境: ubuntu18.04 desktopopencv 3.4.15 opencv是不支持中文的。 这里C代码是采用替换原图的像素点来实现的,实现之前我们先了解一下汉字点阵字库。…...
js截取video视频某一帧为图片
1.代码如下 <template><div class"box"><div class"video-box"><video controls ref"videoRef" preload"true"src"https://qt-minio.ictshop.com.cn:9000/resource-management/2025/01/08/7b96ac9d957c45a…...
Observability:最大化可观察性 AI 助手体验的 5 大提示(prompts)
作者:来自 Elastic Zoia_AUBRY 在过去三年担任客户工程师期间,我遇到了数百名客户,他们最常问的问题之一是:“我的数据在 Elastic 中;我该如何利用它获得最大优势?”。 如果这适用于你,那么本…...
HDFS的架构优势与基本操作
目录 写在前面一、 HDFS概述 1.1 HDFS简介1.2 HDFS优缺点 1.2.1 优点1.2.2 缺点 1.3 HDFS组成架构1.4 HDFS文件块大小 二、HDFS的Shell操作(开发重点) 2.1 基本语法2.2 命令大全2.3 常用命令实操 2.3.1 上传2.3.2 下载2.3.3 HDFS直接操作 三、HDFS的AP…...
hive表修改字段类型没有级连导致历史分区报错
一:问题背景 修改hive的分区表时有级连概念,指字段的最新状态,默认只对往后的分区数据生效,而之前的分区保留历史元数据状态。好处就是修改语句的效率很快,坏处就是如果历史分区的数据还有用,那就回发生分…...
023:到底什么是感受野?
本文为合集收录,欢迎查看合集/专栏链接进行全部合集的系统学习。 合集完整版请查看这里。 在前面介绍卷积算法时,一直在强调一个内容,那就是卷积算法的运算过程是—— 卷积核在输入图像上滑动扫描的过程。 在每一次扫描时,可以…...
GoFrame g.* 方法和数据类型
GoFrame g.* 方法和数据类型 GoFrame 框架通过 g.* 方法提供了一系列常用的数据类型和对象获取方法。这个模块采用强耦合设计,目的是为开发者提供便捷的类型和对象调用方式。 使用方式 import "github.com/gogf/gf/v2/frame/g"数据类型 基础类型别名 …...
分苹果,若a ^ b ^ c = 0意味着:a 和 (b ^ c) 的值相等,或者 b 和 (a ^ c) 的值相等,以及 c 和 (a ^ b) 的值相等。
若a ^ b ^ c faultSum,那么faultSum 0时,即可产生上面的平分方案。说明可以满足二进制平分 #include<bits/stdc.h> using namespace std; int main() { int n; cin>>n; vector<int> weight(n); for(int i0;i<n;i) {…...
深入解析人工智能中的协同过滤算法及其在推荐系统中的应用与优化
目录 什么是协同过滤算法核心原理基本步骤相似度计算代码实现详解1.流程图2.创建基础的数据结构存储用户评分数据3.计算用户相似度4.获取相似用户5.推荐方法 算法优化建议1. 数据预处理优化去除异常值和噪声数据进行数据标准化使用稀疏矩阵优化存储 2. 相似度计算优化使用局部敏…...
电梯系统的UML文档04
这个版本的类图是直接从4.2节中用例图的描述得来的,这个视图中的类覆盖了系统所有的功能。我们用电梯类和电梯控制器类(ElevatorControl)移动或停止电梯;用门类开门或关门;用指示器类让乘客知道电梯的位置和方向&#…...
《自动驾驶与机器人中的SLAM技术》ch4:预积分学
目录 1 预积分的定义 2 预积分的测量模型 ( 预积分的测量值可由 IMU 的测量值积分得到 ) 2.1 旋转部分 2.2 速度部分 2.3 平移部分 2.4 将预积分测量和误差式代回最初的定义式 3 预积分的噪声模型和协方差矩阵 3.1 旋转部分 3.2 速度部分 3.3 平移部分 3.4 噪声项合并 4 零偏的…...
海量数据的处理
一般来说都是针对数据量特别大,内存有限制的。 第一类:topk问题 比如,在海量数据中找前50大的数据怎么办? 方法一:使用小顶堆,用小顶堆维护这50个元素,当有新元素到来时,直接与堆…...
Python人脸识别库DeepFace使用教程及源码解析
目录 一、DeepFace介绍 1、人脸库设计 2、DeepFace.find 3、DeepFace.verify 4、DeepFace.analyze 5、DeepFace.extract_faces 6、DeepFace.represent 7、DeepFace.stream 二、DeepFace二次开发 1、开发活体检测API 2、模型权重持久化 三、总结 一、DeepFace介绍 …...
Nacos:使用PgSQL数据源
数据源插件开源仓库地址:nacos-datasource-extend-plugins 一、PostgreSQL数据库安装 1、本文使用Docker进行数据库的安装,使用docker命令拉取的PG14版本的数据库: docker pull postgres:14.6 2、创建PG容器并启动,映射了5432…...
基于Python的多元医疗知识图谱构建与应用研究(下)
五、基于医疗知识图谱的医疗知识图谱程序构建 5.1 数据层构建 5.1.1 数据源选择与获取 在构建基于医疗知识图谱的医疗知识图谱数据层时,数据源的选择与获取至关重要。数据源的质量和丰富度直接决定了知识图谱的可靠性和实用性。医学文献是重要的数据源之一,包括学术期刊论…...
JAVA:Spring Boot 实现责任链模式处理订单流程的技术指南
1、简述 在复杂的业务系统中,订单流程往往需要一系列的操作,比如验证订单、检查库存、处理支付、更新订单状态等。责任链模式(Chain of Responsibility)可以帮助我们将这些处理步骤分开,并且以链式方式处理每一个操作…...
SpringBoot多级配置文件
1.问题先导 有这样的场景,我们开发完毕后需要测试人员进行测试,由于测试环境和开发环境的很多配置都不相同,所以测试人员在运 行我们的工程时需要临时修改很多配置,如下 java –jar springboot.jar –-spring.profiles.activete…...
阿里云安装mikrotik7配置内网互通
阿里云近期推出了200M不限量机器,对于没有公网接入的中小企业可以借助这个机器对多地分支机构进行内网互通。目前已经有很多机构用这个搞跨云k8s,跨云集群了。 mikrotik作为一个商用的软件,操作性比一些开源的软件好用不少。 本文使用的网段为172.16.1…...
std::forward实现原理与应用场景
std::forward 是 C11 引入的一个函数模板,用于实现完美转发(Perfect Forwarding)。它的核心作用是根据传入的参数,决定将参数以左值引用还是右值引用的方式进行转发,从而保持参数的原始值类别。 实现原理 template&l…...
TiDB 在市面上的热门应用领域
TiDB 在市面上的热门应用领域 TiDB 作为一款分布式数据库,凭借其高可扩展性和强一致性,逐渐成为多个行业和领域的热门选择。那么,TiDB 在市面上主要应用在哪些领域呢?今天我们来看看 TiDB 在几个热门领域的应用场景。 1. 互联网…...
“深入浅出”系列之C++:(11)推荐一些C++的开源项目
1. SQLiteCpp - 简单易用的Sqlite C封装库 仓库地址:https://github.com/SRombauts/SQLiteCpp 简介:SQLiteCpp是一个对Sqlite数据库进行C封装的开源库,代码行数约2,500行。它提供了简洁易用的接口,使得在C项目中操作Sqlite数据库…...
高等数学学习笔记 ☞ 定积分的积分方法
1. 定积分的换元积分法 1. 换元积分公式:设函数在闭区间上连续,令,若满足: ①:当时,;当时,。 此时的大小关系不一定,但与最好对应着写,否则就要留意变号的问…...
KVA教程-插件开发
“如果结果不如你所愿,就在尘埃落定前奋力一搏。”——《夏目友人帐》 “有些事不是看到了希望才去坚持,而是因为坚持才会看到希望。”——《十宗罪》 “维持现状意味着空耗你的努力和生命。”——纪伯伦 KVA 技术教程 * 插件开发 简介 插件开发是KVA&a…...
AI守护煤矿安全生产:基于视频智能的煤矿管理系统架构解析
前言 本文我将介绍我和我的团队自主研发设计的一款AI产品的成果展示——“基于视频AI识别技术的煤矿安全生产管理系统”。 这款产品是目前我在创业阶段和几位矿业大学的博士共同从架构设计、开发到交付的全过程中首次在博客频道发布, 我之前一直想写但没有机会来整理这套系统的…...
AI编程工具横向评测--Cloudstudio塑造完全态的jupyter notebook助力数据分析应用开发
AI编程工具横向评测–Cloudstudio塑造完全态的jupyter notebook助力数据分析应用开发 数据分析类应用的开发,指的是首先进行数据分析,比如统计学分析、机器学习模型的构建等,然后将分析的流程开发成数据分析类的工具,或者将数据分…...
04JavaWeb——Maven-SpringBootWeb入门
Maven 课程内容 初识Maven Maven概述 Maven模型介绍 Maven仓库介绍 Maven安装与配置 IDEA集成Maven 依赖管理 01. Maven课程介绍 1.1 课程安排 学习完前端Web开发技术后,我们即将开始学习后端Web开发技术。做为一名Java开发工程师,后端Web开发…...
ThreeJS能力演示——界面点选交互能力
1、支持界面点选 点选模型整体思路是:根据camera位置作为起始点,叠加鼠标相对位置作为偏置,摄像头方向作为射线方向。 根据射线方向中的遇到的3D物体列表,第一个遇到的物体作为被点选的物体。 // 鼠标事件处理let selectedObjec…...
Linux:常用命令--文件与目录操作
ls命令 功能:(list)列出当前目录的文件信息 语法:ls [-l -h -a] [参数] 参数:被查看的文件夹,不提供参数,表示查看当前工作目录-l,以列表形式查看每个文件的属性,包含…...
Node.js NativeAddon 构建工具:node-gyp 安装与配置完全指南
Node.js NativeAddon 构建工具:node-gyp 安装与配置完全指南 node-gyp Node.js native addon build tool [这里是图片001] 项目地址: https://gitcode.com/gh_mirrors/no/node-gyp 项目基础介绍及主要编程语言 Node.js NativeAddon 构建工具(node-gyp…...
docker运行Java项目,Kaptcha因为字体缺失没法显示验证码图片
2015工作至今,10年资深全栈工程师,CTO,擅长带团队、攻克各种技术难题、研发各类软件产品,我的代码态度:代码虐我千百遍,我待代码如初恋,我的工作态度:极致,责任ÿ…...
C++otlv4连接sql serveer使用记录(注意点)
C使用otlv4在做插入时,有一些设计的坑需要注意 插入数据: 当要给表中插入单个字符时,数据库表设计使用varchar(1)是合理的,但是otlv4一直报错char。 后续查很久才知道,otlv4所写的绑定的字符数组的长度应该实际数组…...
[思考记录]认知和思考
在以前,具备一定的技能和经验就能轻易找到自己的一席之地。但在AI时代下,这些东西很容易就被抹平,那么我们的竞争力又在哪里?“认知和思考”是一个方向,帮助我们能去应对复杂情境、帮我们更容易去看到真相。 1.很多时…...
前端开发Web
Ajax 概念:Asynchronous JavaScriptAnd XML,异步的JavaScript和XML 作用: 数据交换:通过Ajax可以给服务器发送请求,并获取服务器响应的数据。 异步交互:可以在不重新加载整个页面的情况下,与服务器交换数据并更新部分网页的…...
【C++提高篇】—— C++泛型编程之模板基本语法和使用的详解
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、模板的概念二、函数模板2.1 函数模板的使用2.2 函数模板注意事项2.3 普通函数与函数模板的区别2.4 普通函数与函数模板的调用规则2.5 模板的局限性 三、类模…...
WPS计算机二级•高效操作技巧
听说这里是目录哦 斜线表头 展示项目名称🍋🟩横排转竖排🍐批量删除表格空白行🍈方法一方法二建辅助列找空值 能量站😚 斜线表头 展示项目名称🍋🟩 选中单元格,单击右键➡️“设…...
【Maui】视图界面与数据模型绑定
文章目录 前言一、问题描述二、解决方案三、软件开发(源码)3.1 创建模型3.2 视图界面3.3 控制器逻辑层 四、项目展示 前言 .NET 多平台应用 UI (.NET MAUI) 是一个跨平台框架,用于使用 C# 和 XAML 创建本机移动和桌面应用。 使用 .NET MAUI&…...
vue3-sfc-loader 加载远程.vue文件(sfc)案例
注意事项 style标签如果增加了lang比如:lang“scss”,需要提供scss-loader的处理器,这个暂时没研究,我的处理方式是将动态模版的css放在了全局打包暂时还没有测试,后面测试了会同步更新 安装vue3-sfc-loader npm inst…...
Hadoop美食推荐系统 爬虫1.8w+数据 协同过滤余弦函数推荐美食 Springboot Vue Element-UI前后端分离
Hadoop美食推荐系统 爬虫1.8w数据 协同过滤余弦函数推荐美食 Springboot Vue Element-UI前后端分离 【Hadoop项目】 1. data.csv上传到hadoop集群环境 2. data.csv数据清洗 3.MapReducer数据汇总处理, 将Reducer的结果数据保存到本地Mysql数据库中 4. SpringbootEchartsMySQL 显…...
使用Linux驱动程序的fasync(文件异步通知机制)向用户空间发送SIGIO信号的学习记录
前言 本文学习使用Linux驱动程序的fasync(文件异步通知机制)向用户空间发送SIGIO信号。 fasync(文件异步通知机制)名字的来历 fasync 是 “file asynchronous” 的缩写,意思是 文件异步通知。 这里的文件是指文件结构体struct file *file ,关于文件结…...
面试经验分享-回忆版某小公司
说说你项目中数据仓库是怎么分层的,为什么要分层? 首先是ODS层,连接数据源和数据仓库,数据会进行简单的ETL操作,数据来源通常是业务数据库,用户日志文件或者来自消息队列的数据等 中间是核心的数据仓库层&a…...
【算法学习笔记】35:扩展欧几里得算法求解线性同余方程
线性同余方程问题 线程同余方程问题是指 a x ≡ b ( m o d m ) ax \equiv b~(mod~m) ax≡b (mod m),给定 a a a、 b b b和 m m m,找到一个整数 x x x使得该方程成立,即使得 a x m o d m b ax~mod~mb ax mod mb,随便返回任何一个…...
ent.SetDatabaseDefaults()
在 AutoCAD 的 .NET API 中,ent.SetDatabaseDefaults() 这句代码通常用于将一个实体(Entity)对象的属性设置为与其所在的数据库(Database)的默认设置相匹配。这意味着,该实体将采用数据库级别的默认颜色、图…...