在做题中学习(30):字符串相加

思路:

相加时要转换成对应的数字,所以让字符数字-'0'    如‘9’-‘0’=(ASCII)57-48=9

9+1=10,会进1,把进位保存起来,只取0头插到新串里。

头插时要转换对应字符数字,所以让对应的数字+‘0’   如0+'0'=48 =='0'

之后下标往前走依次取值相加(每次都要+进位)。

实现
class Solution 
{
public:
    string addStrings(string num1, string num2) 
    {
        int end1=num1.size()-1,end2=num2.size()-1;
        int next=0;
        string str;
        while(end1>=0||end2>=0)
        {
            int val1 = 0;
            int val2 = 0;
            if(end1>=0)
            {
                val1=num1[end1--]-'0';
            }
            if(end2>=0)
            {
                val2=num2[end2--]-'0';
            }
            int ret=val1+val2+next;
            next=ret/10;
            ret%=10;

            str.insert(0,1,ret+'0');
        }
        
        return str;
    }
};

发现还有用例没通过,可以看出是结束时循环走出来了没有+进位,所以在循环结束后加个判断条件:

if(next==1)
{
    str.insert(0,1,'1');
}

最后看到用时很长,因为头插的时间复杂度是(n^2)。

优化:

         把头插换成尾插

class Solution 
{
public:
    string addStrings(string num1, string num2) 
    {
        int end1=num1.size()-1,end2=num2.size()-1;
        int next=0;
        string str;
        while(end1>=0||end2>=0)
        {
            int val1 = 0;
            int val2 = 0;
            if(end1>=0)
            {
                val1=num1[end1--]-'0';
            }
            if(end2>=0)
            {
                val2=num2[end2--]-'0';
            }
            int ret=val1+val2+next;
            next=ret/10;
            ret%=10;

            
            str.push_back(ret+'0');
        }
        if(next==1)
        {
            str.push_back('1');
        }
        reverse(str.begin(),str.end());
        return str;
    }
};

时间复杂度(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162121.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

各类软件docker安装

docker Docker 要求 CentOS 系统的内核版本高于 3.10 ,通过 uname -r 命令查看你当前的内核版本: uname -r 3.10.0-1062.1.2.el7.x86_64 安装 Docker: 安装 Docker:yum -y install dockerkafka和zookeeper docker pull wurstmei…

Unity 6 是下一个 LTS 版本即将发布

Unity 公司宣布,即将发布 Unity 6,并表示其为下一个长期支持版本 (LTS)。 Unity 在大会上演示了全新的 Unity 6引擎,并通过 Syncy Studios 采用 Unity 6 制作的《幻想王国(Fantasy Kingdom)》Demo 进行了演示&#xff…

OpenGL_Learn13(材质)

1. 材质 cube.vs #version 330 core layout (location 0) in vec3 aPos; layout (location 0 ) in vec3 aNormal;out vec3 FragPos; out vec3 Normal;uniform mat4 model; uniform mat4 view; uniform mat4 projection;void main() {FragPosvec3(model*vec4(aPos,1.0));Norma…

【MATLAB】史上最全的5种数据插值算法全家桶

有意向获取代码,请转文末观看代码获取方式~ 大家吃一顿火锅的价格便可以拥有5种数据插值算法,绝对不亏,知识付费是现今时代的趋势,而且都是我精心制作的教程,有问题可随时反馈~也可单独获取某一算法的代码&#xff08…

Gem5模拟器学习之旅

安装gem5 模拟器 翻译自官网(https://www.gem5.org/documentation/learning_gem5/part1/building/) 支持的操作系统和环境 gem5的设计考虑到了Linux环境。我们定期在 Ubuntu 18.04、Ubuntu 20.04 和 Ubuntu 22.04 上进行测试,以确保 gem5 在…

zyj-ha 安装过程及使用部署

一.安装过程排坑 1. 硬件环境准备 排坑 1 首先,服务器至少需要 2 台,每台服务器至少需要 2 块网卡,并且必须有预留 心跳线网口,不能被其他业务占用,否则容易出现脑裂。 2. 通过配置管理工具导入安装包 …

CAD长方形纤维插件2D

插件介绍 CAD长方形纤维插件2D版本可用于在AutoCAD软件内生成随机分布的长方形纤维图形,生成的dwg格式模型可用于模拟二维随机分布的纤维复合材料、随机初始裂缝等,同时模型可导入COMSOL、Abaqus、ANSYS、Fluent等有限元软件内进行仿真分析计算。 插件…

基于libcurl+libopenssl开源库编译出curl下载工具及代码集成curl功能

准备素材: 1. openssl的版本: openssl-1.1.1w.tar.gz 2.curl的版本:curl-8.4.0.tar.gz 目标: 1.编译出openssl库; 2.编译出curl可执行文件及库; 步骤一:先解压压缩包 tar -zxvf openssl-1…

风光能互补发电庭院路灯系统技术原理

风光互补发电系统是由风力发电机组配合太阳能电池组件组成,通过专用的控制逆变器,将风力发电机输出的低压交流电整流成直流电,并与光伏电池组件输出的直流电汇集在一起,充入蓄电池组,实现稳压、蓄能和逆变全过程&#…

不动产数据质量提升_电子档案挂接

前言 做了不动产数据质量提升项目,其中包括集体土地所有权档案扫描、挂接。扫描的工作已经完成了,现在需要进行电子档案挂接。正常来说通过不动产系统技术支撑单位的批量挂接功能,但现实是一言难尽。   尝试过进行抓包分析,提交…

MySQL数据库下的Explain命令深度解析

Explain是一个非常有的命令,可以用来获取关于查询执行计划的信息,以及如何解释输出。Explain命令是查看查询优化器如何决定执行查询的主要方法。这个功能有一定的局限性,并不总是会说出真相,但是它的输出是可以获取的最好信息&…

C#单例模式懒汉式与饿汉式

单例模式一般分为懒汉模式和饿汉模式,懒汉式单例在第一次引用时创建实例,不是在类加载时;饿汉式单例模式是一种在类加载时就创建实例的方式,因此也称为静态初始化。 单例模式实现的技巧时构造私有,向外提供静态实例。…

【数据分享】2023年我国省市县三级的独角兽企业数量(Excel/Shp格式)

企业是经济活动的参与主体。一个城市的企业数量决定了这个城市的经济发展水平!比如一个城市的金融企业较多,那这个城市的金融产业肯定比较发达;一个城市的制造业企业较多,那这个城市的制造业肯定比较发达。 之前我们给大家分享了…

【算法萌新闯力扣】:找到所有数组中消失对数字

力扣热题:找到所有数组中消失对数字 开篇 这两天刚交了蓝桥杯的报名费,刷题的积极性高涨。算上打卡题,今天刷了10道算法题了,题目都比较简单,挑选了一道还不错的题目与大家分享。 题目链接:448.找到所有数组中消失对…

UML统一建模语言

UML包含3种构造块:事物、关系、图。 事物:模型中代表性成分的抽象关系:把事物结合在一起图:聚集了相关的事物 事物 结构事务:模型的静态部分,包括类、接口、协作、用例、主动类、构件、制品、结点 行为事…

【LeetCode刷题-双指针】--16.最接近的三数之和

16.最接近的三数之和 方法&#xff1a;排序双指针 class Solution {public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int ans nums[0] nums[1] nums[2];for(int i 0;i<nums.length;i){int start i1,end nums.length - 1;while(start < en…

11 月 11 日 ROS 学习笔记——ROS 架构及概念

文章目录 前言一、 ROS 文件系统级1). 工作空间 Ws2). 功能包3). 消息 msg4). 服务 srv 二、计算图级1). 动态加载节点 nodelet2). 主题 topic3). 服务 srv4). 消息 msg5). 试用练习5). 创建工作空间6). 创建 ROS 功能包和元功能包7). 编译ROS功能包8). 使用 ROS 节点9). 使用主…

kubernetes|云原生| 如何优雅的重启和更新pod---pod生命周期管理实务

前言&#xff1a; kubernetes的管理维护的复杂性体现在了方方面面&#xff0c;例如&#xff0c;&#xff50;&#xff4f;&#xff44;的管理&#xff0c;服务的管理&#xff0c;用户的管理&#xff08;&#xff32;&#xff22;&#xff21;&#xff23;&#xff09;&#xf…

linux进程间通信之信号

摘要 本文旨在研究Linux进程间通信的机制之一&#xff1a;信号。信号是由操作系统来处理的&#xff0c;说明信号的处理在内核态。信号不一定会立即被处理&#xff0c;此时会储存在信 号的信号表中。最后&#xff0c;我们会对这种通信方式的优缺点进行全面的分析&#xff0c;并给…