【C++】 —— 笔试刷题day_6
刷题day_6,继续加油哇!
今天这三道题全是高精度算法
一、大数加法
题目链接:大数加法
题目解析与解题思路
OK,这道题题目描述很简单,就是给我们两个字符串形式的数字,让我们计算这两个数字的和
看题目我们可以发现,题目所给的数组范围特别大,所以,我们使用int、long long
肯定是不行的;
对于这种高精度算法题,我们解题思路呢也很简单,就直接模拟加法(加法竖式
)就可以了。
怎么模拟呢?(这里自己给出两个数字,来模拟一下过程)
现在自己给出两个字符串
1314
、521
;我们来模拟一下这两个数字求和的过程
我们通过观察可以发现,在列竖式计算时:当前位的结果等于两个数当前位的和
再加上进位数
,(而进位数等于上一位的结果/10
)最后再%10
;
那我们就可以来模拟整个过程了:
这里有两种思路:
一就是先将字符串中的每一位转化成int
并存储起来,再进行计算,最后转化成string
结果返回
这种思路也是博主在做这道题时用的思路,实现起来并不算特别麻烦;
但是有一点,需要为
s
、t
和结果ret
创建三个int
类型的数组。
这里就不实现这一种思路了,来看第二种思路
第二种思路也是模拟整个过程,但是不需要创建数组来存储数据,直接从字符串的最后一位开始计算,结果直接存放在ret
要返回的string
中,直到结束
在整个过程中,我们需要注意:
- 计算结果是通过
push_back()
尾插到结果中,所以在结果中个位
是在前面的,在返回之前我们需要对其进行逆置。
代码实现
class Solution {
public:string solve(string s, string t) {// write code hereint i = s.size() - 1;int j = t.size() - 1;string ret;int tmp = 0;//进位数while(i>=0 || j>=0 ||tmp){if(i>=0)tmp+=(s[i--]-'0');if(j>=0)tmp+=(t[j--]-'0');ret+=(tmp%10 +'0');tmp/=10;}reverse(ret.begin(),ret.end());return ret;}
};
二、链表相加
题目链接:链表相加
题目解析
来看这一道题目,给我们两个单链表(9->3->7
、6->3
)每一个链表代表一个整数,让我们计算这两个链表所代表整数的和。
当然这一道题看起来和上一题类似,解法也类似,只不过多了一些链表的相关操作。
算法思路
我们通过题目给的示例可以发现,数字的最低位是在链表的结尾;
我们计算的时候都是从最低位开始计算的,所以本道题需要先将链表进行逆置再进行操作
整体思路如下:
- 首先将链表逆置。
- 再同时遍历两个逆置后的链表,计算结果,一位一位的头插到结果链表中。
- 最后返回结果链表即可。
这里解释一下为什么要用头插:因为我们是从个位开始计算的,而个位应该在链表的尾部,所以使用头插;就避免了使用尾插后再进行逆置链表。
逆置链表:
之前我们逆置链表是使用两个指针来逆置,这个就不多说了;
现在来看一种新的逆置方法
- 先定义一个链表的头节点,
- 再遍历原链表,将原链表的节点头插到定义的新链表中,
- 最后遍历结束,头结点的下一个节点就是逆置完的链表的第一个节点。
代码实现
现在来看代码实现:(当然这里也可以现将所以数取出来再进行计算)
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {public:ListNode* reverse(ListNode* head) {ListNode* phead = new ListNode(0);ListNode* cur = head;while (cur) {//头插法逆置链表ListNode* next = cur->next;cur->next = phead->next;phead->next = cur;cur = next;}ListNode* ret = phead->next;delete phead;return ret;}ListNode* addInList(ListNode* head1, ListNode* head2) {// write code herehead1 = reverse(head1);head2 = reverse(head2);int tmp = 0;ListNode* head = new ListNode(0);while (head1 != nullptr || head2 != nullptr || tmp) {if (head1) {tmp += head1->val;head1 = head1->next;}if (head2) {tmp += head2->val;head2 = head2->next;}int x = tmp % 10;ListNode* newnode = new ListNode(x);newnode->next = head->next;head->next = newnode;tmp /= 10;}ListNode* ret = head->next;delete head;return ret;}
};
三、大数乘法
题目链接:大数乘法
题目解析
这道题就有意思了,大数乘法,前两道我们都是算的加法,现在来看乘法;
给定字符串,计算这两个字符串对应的乘积;
算法思路
看到这道题,多多少少还是有那么一点思路的,我们还是需要模拟整个乘法的过程;
乘法呢,我们知道,一个数的每一位都要和另一个数去乘的,所以这里我们使用两层
for
循环就可以解决问题。但是新的问题又来了,那就是个位、十位和百位与另一个数乘是不一样的;那乘完之后将数放到哪里呢?
这里定义一个vector
,大小是m+n
(m
和n
分别表示两个字符串的长度)。
我们现将两个字符逆置过来,这样个位所对应的下标就是0
、十位就是1
;
所以我们在计算乘的时候(一个数的个位
与另一个数的每一位相乘)所得的积就要放在vector[i+j]
中,什么意思呢?
可以看到,这样我们就知道了两个数的每一位相乘需要放到哪一个位置上了。
这里注意,我们在第一次计算的过程中最好不要进位(因为太麻烦了)
- 这里计算完成以后(不进位),我们遍历整个
vector
数组,将其中的数依次进位,然后转换成字符;- 注意:遍历完
vector
数组后,可能存在进位未转换,需要单独处理- 最后,我们需要对字符串进行一个去
0
操作,就是将最高位的0
去掉- 再逆置一下即可
代码实现
class Solution {
public:string solve(string s, string t) {// write code herereverse(s.begin(),s.end());reverse(t.begin(),t.end());int m = s.size();int n = t.size();vector<int> v(m+n,0);//不进位计算for(int i=0;i<m;i++){for(int j = 0;j<n;j++)v[i+j] += (s[i]-'0')*(t[j]-'0');}//处理进位int tmp = 0;string ret;for(auto e:v){tmp+=e;ret+=(tmp%10 + '0');tmp/=10;}//进位可能有余while(tmp){ret+=(tmp%10 + '0');tmp/=10;}//对最高位进行去0while(ret.size()>1 && ret.back()=='0')ret.pop_back();reverse(ret.begin(),ret.end());return ret;}
};
这三道高精度的算法题,希望对你有所帮助!
感谢支持
相关文章:
【C++】 —— 笔试刷题day_6
刷题day_6,继续加油哇! 今天这三道题全是高精度算法 一、大数加法 题目链接:大数加法 题目解析与解题思路 OK,这道题题目描述很简单,就是给我们两个字符串形式的数字,让我们计算这两个数字的和 看题目我…...
PostgreSQL:语言基础与数据库操作
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编…...
cmake 之 CMakeLists.txt 中的函数是从哪里来的
我们都知道,cmake会解释执行 CMakeLists.txt 以及其他 *.cmake 脚本, 这里先给出一个“先验” 的知识点: 任何一个独立脚本或脚本函数命令的执行,都是通过 CPP 函数 RunListFile(...) 调用的 void cmMakefile::RunListFile(cmL…...
谷歌or-tools开源库入门
1.命令行编译程序 这里要说明下,直接用qt或者VS2022打开cmake工程,编译没有成功。所以,老老实实的按照官方教程来,使用命令行编译。 (1)准备 1)安装cmake,版本3.18以上࿰…...
深入解析 C++ Vector:全面掌握 STL 核心容器的原理与高效实践
一、Vector 的核心概念与特性 Vector 是 C 标准库中最常用的动态数组容器,其底层基于连续内存存储元素,兼具数组的高效访问与动态扩容的灵活性。以下是其核心特性: 1.1 核心特性对比 特性普通数组Vector 容器内存分配静态固定动态增长访问效…...
【MySQL】MySQL数据存储机制之存储引擎
目录 1.如何理解存储引擎? 2.MySQL 提供的存储引擎 3.存储引擎的功能特性 (1)存储介质 (2)事务处理能力 (3)锁定 (4)备份和恢复 (5)优化…...
OpenCV旋转估计(1)用于估计图像间仿射变换关系的类cv::detail::AffineBasedEstimator
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 基于仿射变换的估计器。 这种估计器使用匹配器估算的成对变换来为每个相机估算最终的变换。 cv::detail::AffineBasedEstimator 是 OpenCV 库中…...
小红书不绑定手机号会显示ip吗
小红书作为一个生活方式分享平台,拥有庞大的用户群体。在小红书上,用户可以分享自己的生活点滴、购物心得、美食体验等,与其他用户进行互动交流。最近,不少用户对于小红书是否会在不绑定手机号的情况下显示IP属地产生了疑问&#…...
网络空间安全(36)数据库权限提升获取webshell思路总结
一、获取数据库访问权限 寻找漏洞: SQL注入:这是最常见的方法之一。攻击者通过SQL注入漏洞,可以在数据库执行任意SQL语句,从而获取数据库中的数据,甚至可能获取数据库的访问权限。配置文件泄露:有时&#x…...
OceanBase 中,如何抓包分析应用连接超时的问题
本文作者:胡呈清,爱可生 DBA 团队成员,擅长故障分析、性能优化 与MySQL这类单机数据库相比,OceanBase分布式数据库的访问链路相对较长,因此在遇到连接异常时,排查过程需要额外考虑更多环节。接下来…...
用uv管理python环境/项目(各种应用场景)
一、安装uv 有python的情况 pip install uvWindows powershell -ExecutionPolicy ByPass -c "irm https://astral.sh/uv/install.ps1 | iex"linux或macOS curl -LsSf https://astral.sh/uv/install.sh | sh二、换镜像源 uv不会读取pip的镜像源配置,所…...
Linux——进程(5)进程地址空间
先看一个程序和现象 预期现象是,子进程和父进程相互独立,子进程的gval是100,101,102....而父进程一直都是100. 结果我们并不意外,只是我们发现,父子进程的gval的地址是一样的,这有点颠覆我们的认…...
docker(1) -- centos镜像
1. 前言 我在WSL中运行的系统是ubuntu2024,并安装了docker,想要在docker中运行一个centos的系统。 2. 下载并运行镜像 # 下载centos最新版镜像 $ docker pull centos Using default tag: latest latest: Pulling from library/centos a1d0c7532777: P…...
Vitis 2024.1 无法正常编译custom ip的bug(因为Makefile里的wildcard)
现象:如果在vivado中,添加了自己的custom IP,比如AXI4 IP,那么在Vitis(2024.1)编译导出的原本的.xsa的时候,会构建build失败。报错代码是: "Compiling blank_test_ip..."…...
【源码阅读】多个函数抽象为类(实现各种类型文件转为PDF)
目录 一、原始函数二、类三、转换过程 一、原始函数 最开始就是写了几个函数(包括doc、excel、ppt类型的文件)转换为pdf,需要将这些函数形成一个类。相似的一类函数就可以组成一个实现特定功能的类 import subprocess import pandas as pd i…...
word插入Mathtype公式居中和自动更新
word插入公式自动更新 前提:安装Mathtype 1.word中查看页的宽度 出现如下 2.设置样式 出现这个窗口 给样式随便起个名字 3.修改样式 3.1 设置两个制表位 第二个 3.2 修改公式字体 如下所示 4. 修改公式格式 4.1在word中打开 Mathtype 4.2 修改公式的格式 变成…...
SpringSecurity配置(自定义认证过滤器)
文末有本篇文章的项目源码文件可供下载学习 在这个案例中,我们已经实现了自定义登录URI的操作,登录成功之后,我们再次访问后端中的API的时候要在请求头中携带token,此时的token是jwt字符串,我们需要将该jwt字符串进行解析,查看解析后的User对象是否处于登录状态.登录状态下,将…...
python字符级差异分析并生成 Word 报告 自然语言处理断句
import difflib from docx import Document from docx.shared import RGBColor from snownlp import SnowNLPdef analyze_char_differences(text_a, text_b):"""分析两个文本的字符级差异:param text_a: 第一个文本:param text_b: 第二个文本"""…...
企业级云MES全套源码,支持app、小程序、H5、台后管理端
企业级云MES全套源码,支持app、小程序、H5、台后管理端,全套源码 开发环境 技术架构:springboot vue-element-plus-admin 开发语言:Java 开发工具:idea 前端框架:vue.js 后端框架ÿ…...
使用GoldenGate完成SQLserver到Oracle的数据实时同步
一、环境准备 *项目**源环境**目标环境*操作系统CentOS Linux release 7.6CentOS Linux release 7.6IP地址192.168.3.92192.168.3.168数据库及版本SQLserver 2016Oracle 11.2.0.4.0GoldenGate用户oggoggGoldenGate版本12.3.0.2.012.3.0.2.0 二、OGG架构 GoldenGate v11 能够…...
【OpenCV C++】如何快速 高效的计算出图像中大于值的像素个数? 遍历比较吗? No,效率太低!那么如何更高效?
文章目录 1 问题2 分析3 代码实现 (两种方法实现)方法1: 使用cv::compare方法2: 使用cv::threshold3.2 compare和threshold 看起来都有二值化效果? 那么二者效率?4 compare函数解释4.1 参数解释4.2 底层行为规则4.3 应用示例4.4 典型应用场景1 问题 一幅图像的目标区域ROI…...
Golang | 每日一练 (6)
💢欢迎来到张胤尘的技术站 💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥 文章目录 Golang | 每日一练 (6)题目参考答案什么是内存逃逸&am…...
git clone, 算是解决可以访问github但无法clone的问题
本文的前提是使用了**且可以正常访问github 查看代理的端口 将其配置到git 首先查看git配置 git config --list然后添加配置,我这边使用的是Hiddfy默认的端口是12334,如果是clash应该是7890 git config --global http.proxy 127.0.0.1:12334其他 删除…...
SpringBoot项目controller层接收对应格式请求的相关RequestMapping配置
目录 (1) (2) (3) 注:此情况注意和(4)中情况进行区分 (4) 在几个springboot项目开发后,我总结了以下的一些常见的接收对应请求的…...
基于ssm学科竞赛小程序的设计及实现(源码+lw+部署文档+讲解),源码可白嫖!
摘要 随着信息时代的来临,过去的学科竞赛管理方式的缺点逐渐暴露,本次对过去的学科竞赛管理方式的缺点进行分析,采取计算机方式构建学科竞赛小程序。本文通过阅读相关文献,研究国内外相关技术,提出了一种关于竞赛信息…...
【论文笔记】VGGT-从2D感知3D:pose估计+稠密重建+点跟踪
VGG组联合Meta改进了dust3r,输入图片,输出对应的一系列3D属性,被CVPR2025收录! 1.abstract 我们提出了VGGT,一种前馈神经网络,能够直接从场景的一个、几个或数百个视角推断出所有关键的3D属性,…...
【大模型系列篇】硅基智能开源数字人模型HeyGem.ai,开启数字人时刻
硅基智能开源数字人模型HeyGem.ai, 1秒克隆生成4K视频, 支持离线多语言, 开源72小时狂揽1.3k星, 目前已经获得3.4k星。 硅基智能正式宣布在GitHub开源全球TOP级数字人模型,同时发布基于该模型的同名数字人工具硅基数字人克隆的本地安装包,这一举措标志着…...
腾讯云容器集群:节点可以访问公网,节点内的pod无法访问公网
腾讯云容器集群:节点可以访问公网,节点内的pod无法访问公网 curl https://www.baidu.com/index.htm参考链接:https://cloud.tencent.com/document/product/457/50356 sysctl -a|grep net.ipv4.conf.all.rp_filter sysctl -a|grep net.ipv4.c…...
Winform优化控件布局性能 SuspendLayout 和 ResumeLayout 方法详解
在Winform中,SuspendLayout 和 ResumeLayout 方法用于优化控件布局性能,适用于批量修改控件属性或动态调整控件时的场景。以下是具体使用方法和注意事项: 一、基本用法 1.调用 SuspendLayout() 在开始批量修改控件前,调用…...
基于Netty实现高性能HTTP服务的架构解析
一、HTTP协议基础 1.1 HTTP协议概述 HTTP(HyperText Transfer Protocol)作为现代Web应用的基石,是基于TCP/IP的应用层协议,具有以下核心特性: 请求/响应模型:客户端发起请求,服务端返回响应无…...
Sqlite下载、安装与数据库创建
Sqlite官网 https://www.sqlite.org/index.html 官方文档链接 https://www.sqlite.org/docs.html 官方文档是英文版的,如果想看中文的文档请参考 **菜鸟教程** 网站中的 **《Sqlite教程》:https://www.runoob.com/sqlite/sqlite-tutorial.html 官方下载…...
内网环境安装dlv,本地远程调试go
背景:内网环境(服务器)下安装dlv,本地通过dlv调试编译后的go代码。 可以配合观看: 【dlv远程调试-哔哩哔哩】 https://b23.tv/NqPZ5q9 内网安装dlv步骤 1、dlv安装: (我额服务器和内网的go都是1.21以上) # 先在有网络的环境下(…...
【使用 Element UI 实现手动上传文件:FormData 追加文件和其他参数,支持单文件覆盖上传】
在开发 Web 应用时,文件上传是一个常见的需求。Element UI 提供了强大的 el-upload 组件,可以轻松实现文件上传功能。本文将详细介绍如何使用 Element UI 实现以下功能: 手动触发文件上传:用户选择文件后,点击按钮手动…...
python基础8 单元测试
通过前面的7个章节,作者学习了python的各项基础知识,也学习了python的编译和执行。但在实际环境上,我们需要验证我们的代码功能符合我们的设计预期,所以需要结合python的单元测试类,编写单元测试代码。 Python有一个内…...
第四节:sqlx库使用指南
在项目中我们通常可能会使用database/sql连接MySQL数据库。本文借助使用sqlx实现批量插入数据的例子,介绍了sqlx中可能被你忽视了的sqlx.In和DB.NamedExec方法。 sqlx介绍 在项目中我们通常可能会使用database/sql连接MySQL数据库。sqlx可以认为是Go语言内置datab…...
麒麟操作系统作为服务器,并且需要在浏览器上调试 MATLAB
在内网环境下,使用麒麟操作系统作为服务器,并且需要在浏览器上调试 MATLAB 程序,这确实复杂,但仍然有可行的解决方案。麒麟操作系统是国产化的 Linux 发行版(如基于 Ubuntu Kylin 或银河麒麟),因…...
在线教育网站项目第四步:deepseek骗我, WSL2不能创建两个独立的Ubuntu,但我们能实现实例互访及外部访问
一、说明 上一章折腾了半天,搞出不少问题,今天我们在deepseek的帮助下,完成多个独立ubuntu24.04实例的安装,并完成固定ip,实践证明,deepseek不靠谱,浪费我2个小时时间,我们将在下面实…...
AI安全、大模型安全研究(DeepSeek)
DeepSeek 点燃AI应用革命之火,但安全 “灰犀牛” 正在逼近 DeepSeek-R1国产大模型的发布,以技术创新惊艳了全球,更是极致的性价比推动国内千行百业接入 AI,政府、企业竞速开发智能业务处理、智能客服、代码生成、营销文案等应用,“落地效率” 成为第一关键词。然而与此相…...
(hash表+vector 数位和相等数对的最大和)leetcode 2342
一定要断点调试看看数据对不对的上!!!不然很容易弄不清楚值和下标 这个题意思是在nums中找出相同数位和的值 如 数位和为7 nums中符合要求的有 43,7 在这些数中选两个相加取最大值,再与其他数位和取得的相加最大值比…...
正则表达式引擎深入探讨
正则表达式引擎(Regular Expression Engine)是正则表达式得以“活起来”的核心。它是一个精密的软件组件,负责接收正则表达式和输入文本,解析模式并执行匹配或替换操作,最终输出结果——可能是简单的“是否匹配”&…...
[蓝桥杯 2023 省 B] 飞机降落(不会dfs的看过来)
[蓝桥杯 2023 省 B] 飞机降落 题目描述 N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D i D_{i} Di 个单位时间,即它最早可以于 T i T_{i} Ti 时刻…...
DockerTLS加密/不加密传输
前言: 在Docker容器的网络通信中,安全性是至关重要的。DockerTLS作为一种加密传输协议,通过为Docker守护进程与客户端之间的通信提供加密层,有效防止数据在传输过程中被窃取或篡改。然而,在某些特定场景下,…...
基于微信小程序的充电桩管理系统
一、开发背景 在开发充电汽车管理系统之前,深入的需求分析至关重要。我们要充分了解不同用户群体的需求,比如私家车主希望充电过程便捷、高效、安全,能够实时查看充电状态和费用明细;出租车、网约车司机则更注重充电速度和充电桩…...
Excel导出工具类--复杂的excel功能导出(使用自定义注解导出)
Excel导出工具类 前言: 简单的excel导出,可以用easy-excel, fast-excel, auto-poi,在导出实体类上加上对应的注解,用封装好的工具类直接导出,但对于复杂的场景, 封装的工具类解决不了,要用原生的excel导出(easy-excel, fast-excel, auto-poi都支持原生的) 业务场景: 根据…...
创新实训项目初始化——gitee的使用
创新实训项目管理采用gitee,写下这篇博客熟悉gitee进行项目创建和版本同步 一、gitee概述 Gitee 是一个基于 Git 的代码托管平台,与 GitHub 类似,Gitee 提供了丰富的功能,比如代码仓库的创建、分支管理、代码审查等。 二、gite…...
【原创】使用ElasticSearch存储向量实现大模型RAG
一、概述 检索增强生成(Retrieval-Augmented Generation,RAG)已成为大型语言模型(LLM)应用的重要架构,通过结合外部知识库来增强模型的回答能力,特别是在处理专业领域知识、最新信息或企业私有数…...
Gymnasium Cart Pole 环境与 REINFORCE 算法 —— 强化学习入门 2
Title: Gymnasium Cart Pole 环境与 REINFORCE 算法 —— 强化学习入门 2 文章目录 I. Gymnasium Cart Pole 环境II. REINFORCE 算法1. 原理说明2. REINFORCE 算法实现 I. Gymnasium Cart Pole 环境 Gymnasium Cart Pole 环境是一个倒立摆的动力学仿真环境. 状态空间: 0: Ca…...
响应式数据 和 Pinia 状态
响应式数据 和 Pinia 状态 是 Vue.js 应用中用于管理数据的两种重要机制,它们之间有密切的关系。以下是它们的定义、特点以及关系: 1. 响应式数据 定义 响应式数据 是 Vue.js 的核心特性之一,指的是当数据发生变化时,视图会自动…...
在大数据开发中hive是指什么?
hello宝子们...我们是艾斯视觉擅长ui设计和前端数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩! 在大数据技术的浩瀚星空中,Apache Hive犹如一座桥梁,连接着传统数据仓库理念…...
LeRobot源码剖析——对机器人各个动作策略的统一封装:包含ALOHA ACT、Diffusion Policy、VLA模型π0
前言 过去2年多的深入超过此前7年,全靠夜以继日的勤奋,一天当两天用,抠论文 抠代码 和大模型及具身同事讨论,是目前日常 而具身库里,idp3、π0、lerobot值得反复研究,故,近期我一直在抠π0及l…...