leetcode:字符串相乘(两种方法)
题目:
给定两个以字符串形式表示的非负整数 num1
和 num2
,返回 num1
和 num2
的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示:
1 <= num1.length, num2.length <= 200
num1
和num2
只能由数字组成。num1
和num2
都不包含任何前导零,除了数字0本身。
代码实现1
class Solution
{
public:string multiply(string num1, string num2){if (num1 == "0" || num2 == "0"){return "0";}int m = num1.size() - 1;int n = num2.size() - 1;string ret = "0";//用于字符串的相加for (int i = n; i >= 0; i--)//num2的每一位固定住,去和num1的所有位相乘{string s;//存储num2的某一位与num1所有位相乘的结果int j = 0;for ( j = n; j > i; j--)//由于是从后往前存的,所以要先补齐结果的0{s += '0';}int carry = 0;int x = num2[i] - '0';//num2的某一位for (j = m; j >= 0; j--)//num1的所有位{int y = num1[j] - '0';int mul = x * y + carry;s += mul % 10 + '0';carry = mul / 10;}if (carry){s += carry + '0';}reverse(s.begin(), s.end());//倒着存的,要逆置一下ret = addstring(ret, s);//num2的某一位与num1相乘的结果与之前的结果相加}return ret;}string addstring(const string& num1, const string& num2)//字符串相加算法{int m = num1.size() - 1;int n = num2.size() - 1;int carry = 0;string s;while (m >= 0 || n >= 0 || carry){int x = m >= 0 ? num1[m] - '0' : 0;//已经遍历结束的,以0来替补不存在的位int y = n >= 0 ? num2[n] - '0' : 0;int sum = x + y + carry;s += sum % 10 + '0';carry = sum / 10;m--;n--;}reverse(s.begin(), s.end());//也是倒着存的,所以要逆置一下return s;}
};
思路详解:
1 选择num1或者num2字符串固定住,这里以固定num2为例
2 num2的每一位都与num1相乘,得到一个字符串
3 将这些字符串相加(注意在相加前该补0的要补0)
注意:当num1或是num2为0时,要返回"0",不能按照以上思路去计算
比如,num1为"123" num2为"0"时,计算的结果是"000"而不是"0"
代码实现2
相较代码1,代码2的解题思路效率高
class Solution
{
public:string multiply(string num1, string num2){if (num1 == "0" || num2 == "0"){return "0";}int m = num1.size();int n = num2.size();vector<int> v(m + n);//提前开m+n个空间for (int i = m - 1; i >= 0; i--)//num1的每一位固定住,与num2的所有位相乘,所得结果存入数组中{int x = num1[i] - '0';for (int j = n - 1; j >= 0; j--){int y = num2[j] - '0';v[i + j + 1] += x * y;//注意是+=}}for (int i = m + n - 1; i > 0; i--)//让数组中的前一位的结果加上后一位/10{v[i - 1] += v[i] / 10;v[i] %= 10;//只余下位数为1的数字}int index = v[0] == 0 ? 1 : 0;//数组中有效数据的起始位置string s;while (index < m + n)//将数组中的数据写入字符串中{s += v[index++] + '0';}return s;}
};
思路详解:
利用数组,数组提前开m+n个空间,因为m长度的数字与n长度的数字相乘,所得结果长度为m+n或者是m+n-1
1 随意选择num1,num2中的一个固定住,这里以固定num1为例
2 num1的每一位与num2的所有位相乘,所得数字存入数组中
3 让数组数据中的前一个加上后一个/10
后一个%=10,变成位数为1的数字
相关文章:
leetcode:字符串相乘(两种方法)
题目: 给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。 注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。 示例 1: 输入: num1 "2", nu…...
【爬虫练习之glidedsky】爬虫-基础2
题目 链接 爬虫往往不能在一个页面里面获取全部想要的数据,需要访问大量的网页才能够完成任务。 这里有一个网站,还是求所有数字的和,只是这次分了1000页。 思路 找到调用接口 可以看到后面有个参数page来控制页码 代码实现 import reques…...
03.有监督算法——决策树
1.决策树算法 决策树算法可以做分类,也可以做回归 决策树的训练与测试: 训练阶段:从给定的训练集构造出一棵树(从根节点开始选择特征,如何进行特征切分) 测试阶段:根据构造出来的树模型从上…...
网络协议详解之STP
目录 一、STP协议(生成树) 1.1 生成树协议核心知识点: 1.2 生成树协议与导致问题: 生成树含义: 1.3 802.1D 规则: 802.1D 缺点: 1.4 PVST cisco私有 1.5 PVST 1.6 快速生成树 快速的原…...
Eltima USB Network Gate 10.0 Crack
USB Network Gate -通过网络共享USB 设备 USB Network Gate (前身为以太网USB控制器USB) 轻松的通过网络(Internet/LAN/WAN)分享您的一个或者多个连接到您计算机的USB设备。 无论您身处异国还是近在隔壁办公室,您都可以轻松使用远程扫描仪、打印机、摄像头、调制解…...
SpringCloudGateway网关实战(一)
SpringCloudGateway网关实战(一) 目前对cloud的gateway功能还是不太熟悉,因此特意新建了对应的应用来尝试网关功能。 网关模块搭建 首先我们新建一个父模块用于添加对应的springboot依赖和cloud依赖。本模块我们的配置读取使用的是nacos&a…...
django中使用ajax发送请求
1、ajax简单介绍 浏览器向网站发送请求时 是以URL和表单的形式提交的post 或get 请求,特点是:页面刷新 除此之外,也可以基于ajax向后台发送请求(异步) 依赖jQuery 编写ajax代码 $.ajax({url: "发送的地址"…...
C++之std::list<string>::iterator迭代器应用实例(一百七十九)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
VSCode好用的插件
文章目录 前言1.Snippet Creator & easy snippet(自定义代码)2.Indent Rainbow(代码缩进)3.Chinese (Simplified) Language Pack(中文包)4.Path Intellisense(路径提示)5.Beauti…...
js实现滚轮滑动到底部自动加载(完整版)
这里我们用vue实现(原生js相似), 这里我们用一个div当作一个容器; <div class="JL" @scroll="onScroll" ref="inin"> <div v-for="(item,index) in this.list" :key="index" > ....…...
如何限制PDF打印?限制清晰度?
想要限制PDF文件的打印功能,想要限制PDF文件打印清晰度,都可以通过设置限制编辑来达到目的。 打开PDF编辑器,找到设置限制编辑的界面,切换到加密状态,然后我们就看到 有印刷许可。勾选【权限密码】输入一个PDF密码&am…...
python计算模板图像与原图像各区域的相似度
目录 1、解释说明: 2、使用示例: 3、注意事项: 1、解释说明: 在Python中,我们可以使用OpenCV库进行图像处理和计算机视觉任务。其中,模板匹配是一种常见的方法,用于在一幅图像中识别出与给定…...
阿里云云解析DNS核心概念与应用
文章目录 1.DNS解析基本概念1.1.DNS基本介绍1.2.域名的分层结构1.3.DNS解析原理1.4.DNS递归查询和迭代查询的区别1.5.DNS常用的解析记录 2.使用DNS云解析将域名与SLB公网IP进行绑定2.1.进入云解析DNS控制台2.2.添加域名解析记录2.3.验证解析是否生效 1.DNS解析基本概念 DNS官方…...
计算机竞赛 垃圾邮件(短信)分类算法实现 机器学习 深度学习
文章目录 0 前言2 垃圾短信/邮件 分类算法 原理2.1 常用的分类器 - 贝叶斯分类器 3 数据集介绍4 数据预处理5 特征提取6 训练分类器7 综合测试结果8 其他模型方法9 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 垃圾邮件(短信)分类算…...
compositionAPI
面试题:composition api相比于option api有哪些优势? 不同于reactivity api,composition api提供的函数很多是与组件深度绑定的,不能脱离组件而存在。 1. setup // component export default {setup(props, context){// 该函数在…...
vscode配置调试环境-windows系统
1. 下载Vscode 下载网址code.visualstudio.com 2. 安装vscode 直打开下载好的.exe文件进行安装即可 3.安装插件 4下载mingw编译器 4.1下载 下载网址sourceforge.net/projects/mingw-w64/files/ 下拉找到该位置,下载圈中的版本。下载速度有点慢 临时下载地址 htt…...
智慧城市能实现嘛?数字孪生又在其中扮演什么角色?
数字孪生智慧城市是将数字孪生技术与城市智能化相结合的新兴概念,旨在通过实时数字模拟城市运行,优化城市管理与服务,创造更智能、高效、可持续的城市环境。 在智慧城市中,数字孪生技术可以实时收集、分析城市各个方面的数据&…...
【置顶帖】关于博主/关于博客/博客大事记
关于博主 ● 信息安全从业者 ● 注册信息安全认证专家资质 ● CSDN认证业界专家、安全博客专家 、全栈安全领域优质创作者 ● 中国信通院【2021-GOLF IT新治理领导力论坛】演讲嘉宾 ● 安世加【2021-EISS企业信息安全峰会-上海】演讲嘉宾 ● CSDN【2022-隐私计算论坛】演讲嘉宾…...
华为数通方向HCIP-DataCom H12-821题库(单选题:01-20)
第01题 下面关于OSPF邻居关系和邻接关系描述正确的是 A、邻接关系由 OSPF的 DD 报文维护 B、OSPF 路由器在交换 Hello 报文之前必须建立邻接关系 C、邻居关系是从邻接关系中选出的为了交换路由信息而形成的关系 D、并非所有的邻居关系都可以成为邻接关系 答案:D 解析…...
Java【手撕双指针】LeetCode 11. “盛水最多的容器“, 图文详解思路分析 + 代码
文章目录 前言一、盛水最多的容器1, 题目2, 思路分析3, 代码展示 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表…...
vue3——递归组件的使用
该文章是在学习 小满vue3 课程的随堂记录示例均采用 <script setup>,且包含 typescript 的基础用法 一、使用场景 递归组件 的使用场景,如 无限级的菜单 ,接下来就用菜单的例子来学习 二、具体使用 先把菜单的基础内容写出来再说 父…...
【爬虫练习之glidedsky】爬虫-基础1
题目 链接 爬虫的目标很简单,就是拿到想要的数据。 这里有一个网站,里面有一些数字。把这些数字的总和,输入到答案框里面,即可通过本关。 思路 找到调用接口 分析response 代码实现 import re import requestsurl http://www.…...
计算机视觉入门 1)卷积分类器
目录 一、卷积分类器(The Convolutional Classifer)训练分类器 二、【代码示例】汽车卡车图片分类器步骤1. 导入数据步骤2 - 定义预训练模型步骤3 - 连接头部步骤4 - 训练模型 一、卷积分类器(The Convolutional Classifer) 卷积…...
SpringBoot 配置优先级
一般而言,SpringBoot支持配置文件进行配置,即在resources下的application.properties或application.yml。 关于配置优先级而言, application.properties>application.yml>application.yaml 另外JAVA程序程序还支持java系统配置和命令行…...
钢筋的形变屈服度测量
钢筋力学性能检测方法与检测报告《建筑材料检测技术》杨丛慧 建筑形变检测锚点,本身无实质内容。 建筑的倾角和形变检测方法,工程测量学,李章树 毫米级的卫星位移定位 挠度检测。 赛格事件:SHM-Structural Health Monitoring…...
【BASH】回顾与知识点梳理(三十七)
【BASH】回顾与知识点梳理 三十七 三十七. 基础系统设定与备份策略37.1 系统基本设定网络设定 (手动设定与 DHCP 自动取得)手动设定 IP 网络参数(nmcli)自动取得 IP 参数(dhcp)修改主机名(hostnamectl) 37.2 日期与时间设定时区的显示与设定时间的调整用 ntpdate 手动网络校时 …...
智慧农场云养猪平台原来是这样的!
随着数字化和智能化的发展,农业行业也逐渐开始融入互联网技术,其中云养猪平台作为新兴的农业数字化解决方案之一,备受关注。本文将探讨如何开发一款具备专业、思考深度和逻辑性的云养猪平台。 一、前期准备阶段: 1.明确目…...
【3Ds Max】可编辑多边形“边界”层级的简单使用
目录 示例 (1)挤出 (2)插入顶点 (3)切角 (4)利用所选内容创建图形 (5)封口 (6)桥 示例 这里我们首先创建一个长方体ÿ…...
Rancher-RKE2-安装流程
一、什么是rke2? 1.rke2是Rancher的下一代k8s发行版, 二、与rke的不同 1.重要的是,RKE2 不像 RKE1 那样依赖 Docker。RKE1 利用 Docker 来部署和管理控制平面组件以及 Kubernetes 的容器运行时间。RKE2 将控制平面组件作为静态 pod 启动&…...
OrienterNet: visual localization in 2D public maps with neural matching 论文阅读
论文信息 题目:OrienterNet: visual localization in 2D public maps with neural matching 作者:Paul-Edouard Sarlin, Daniel DeTone 项目地址:github.com/facebookresearch/OrienterNet 来源:CVPR 时间:…...
辣条类网站建设规划书/手机关键词seo排名优化
本文主要记录下自己在react道路上的爬坑过程 以及对于刚学习redux的同学提供一些可供参考的例子。 之前用vue用了很久 vue的语法糖用起来是真的舒服 不过现在公司项目用的是react 只好默默的从vue转到react 其实毕竟他们都是类似的框架, 虽然语法大不同,…...
中国建设银行校园招聘网站/提升排名
移动端的布局不同于pc端,首先我们要知道在移动端中,css中的1px并不等于物理上的1px,因为手机屏幕的分辨率已经越来越高,高像素但是屏幕尺寸却没有发生太大变化,那就意味着一个物理像素点实际上塞入了好几个像素。 在移…...
在服务器做网站/此网站三天换一次域名
题目描述 夏天到了,各家各户的用电量都增加了许多,相应的电费也交的更多了。小玉家今天收到了一份电费通知单。小玉看到上面写:据闽价电[2006]27号规定,月用电量在150千瓦时及以下部分按每千瓦时0.4463元执行,月用电量…...
罗湖网站建设罗湖网站设计/线上营销的优势
和许多其他语言一样,JavaScript 也需要靠很多小技巧去完成各种不同的事情。有的可能早已经广为人知,有的却可能会让你感到有些迷惑。接下来先介绍27个马上就能用起来的 JavaScript 小技巧,下面和千锋广州前端培训小编一起来看看吧!…...
网站的开发语言有哪些/关键词林俊杰mp3在线听
文章目录(一)inline 内联函数(1)宏函数和内联函数的区别:(2)inline 内联函数的优缺点:(3)使用内联函数建议:(二)inline函数…...
百度度小店申请入口/深圳纯手工seo
第一步:查看表空间的名字及文件所在位置:select tablespace_name, file_id, file_name, round(bytes/(1024*1024),0) total_space from dba_data_files order by tablespace_name第二步:增大所需表空间大小alter database datafile 表空间位…...