面试经典150题——两数相加

news/2024/5/26 19:47:18/文章来源:https://blog.csdn.net/m0_60388871/article/details/136568082

​Anything is worth "fighting for," and when you get it, don't doubt it, you deserve it, you deserve it.

a couple of palm trees that are next to each other

1. 题目描述

image-20240307164738539

2.  题目分析与解析

2.1 思路一

这个题目虽然标的是中等,但是大家看一下应该还是比较容易想到思路的,这不就相当于小学学的两数求和嘛,需要注意的就是进位的问题,其它没什么太过于复杂的,因此直接给出代码思路。

代码思路:

  1. 创建一个新的链表作为结果,一个指针指向结果链表的头部,创建一个变量存储进位

  2. 遍历两个链表,获取两个链表的值,计算当前位的值,更新进位,更新当前位的值,更新两个链表的指针

  3. 如果最后一位有进位,需要再创建一个节点

  4. 返回结果链表

优化

因为我们的返回结果新建了一个链表,如果想要更少的内存消耗,我们可以把结果直接在原来的某一个链表上进行修改。具体操作步骤见下代码实现。

3. 代码实现

3.1 思路一

image-20240308163643302

image-20240308163701111

优化

image-20240308173412844

image-20240308173343276

4. 相关复杂度分析

时间复杂度分析:

思路一:
  • 遍历两个链表需要 O(max(m, n)) 的时间,其中 m 和 n 分别是两个链表的长度。

  • 在遍历的过程中,进行加法操作和更新指针操作都是常数时间的操作,不影响总体时间复杂度。

  • 因此,思路一的时间复杂度为 O(max(m, n))。

思路二:
  • 在原链表上进行操作,遍历两个链表需要 O(max(m, n)) 的时间。

  • 在遍历的过程中,进行加法操作和更新指针操作都是常数时间的操作。

  • 因此,思路二的时间复杂度也是 O(max(m, n))。

空间复杂度分析:

思路一:
  • 创建了一个新的链表作为结果,其空间复杂度为 O(max(m, n)),其中 m 和 n 分别是两个链表的长度。

  • 在遍历的过程中,只使用了常数级别的额外空间。

  • 因此,思路一的空间复杂度为 O(max(m, n))。

思路二:
  • 在原链表上进行操作,没有额外创建新的链表,只进行了常数级别的额外空间操作。

  • 因此,思路二的空间复杂度为 O(1)。

综上所述,思路一和思路二的时间复杂度均为 O(max(m, n)),而思路一的空间复杂度为 O(max(m, n)),思路二的空间复杂度为 O(1)。

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

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

相关文章

Keepalived+LVS构建高可用集群

目录 一、Keepalive基础介绍 1. Keepalive与VRRP 2. VRRP相关技术 3. 工作原理 4. 模块 5. 架构 6. 安装 7. Keepalived 相关文件 7.1 配置组成 7.2 全局配置 7.3 VRRP实例配置(lvs调度器) 7.4 虚拟服务器与真实服务器配置 二、Keepalived…

mac系统下GCC优化编译的使用

mac系统下GCC优化编译的使用 编译流程 预处理:g -E homework.cpp -o homework.i 编译:g -S homework.i -o homework.s //.s为汇编文件 汇编:g -c homework.s -o homework.o 链接:g homework.o -o homework 优化选项 -O0&#…

前端网页如何在 Windows 上测试 Safari

“Windows上的Safari?”,“那不可能! Safari 无法在 Windows 上运行。当然的! 曾经可以在windows上运行,但苹果早在 2012 年就停止支持 Windows。对于想要测试 Safari 兼容性的 Web 开发人员来说,这真是太不…

数据结构-树状数组

📑前言 本文主要是【树状数组】——树状数组简单使用的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一…

VR数字展厅在企业中应用的优势有哪些?

随着VR全景技术的成熟,VR数字展厅逐渐成为了企业展示形象和产品的重要手段之一。VR企业数字展厅是一种通过VR技术、3D建模技术展示企业形象和产品的创新方式,将企业线下的展厅搬到线上,为企业品牌形象带来了很多优势。 VR数字展厅在企业中应用…

【大厂AI课学习笔记NO.68】开源和开源发展情况

开源即源代码公开,任何人能获取源代码,查看、修改、分发他们认为合适的代码。 依托同行评审和社区生成,旨在以分散、协作的方式开发。 我们曾经很详细的讨论过开源协议的问题,详细可以参考我的文章: https://giszz.…

为什么要用scrapy爬虫库?而不是纯python进行爬虫?

为什么要用scrapy爬虫库?而不是纯python进行爬虫? Scrapy的优点Scrapy节省的工作使用纯Python编写爬虫的不足 Scrapy是一个使用Python编写的开源和协作的web爬虫框架,它被设计用于爬取网页数据并从中提取结构化数据。Scrapy的强大之处在于其广…

新手如何快速上手学习单片机?

读者朋友能容我,不使博文负真心 新开专栏,期待与诸君共享精彩 个人主页:17_Kevin-CSDN博客 专栏:《单片机》 学习单片机是一个有趣且有挑战性的过程。单片机是一种微控制器,广泛应用于各种电子设备和嵌入式系统中。在这…

精通Linuxd磁盘分区挂载的精髓:从理论到实战一网打尽

前言 想要深入了解Linux系统中磁盘分区挂载的原理和操作步骤吗?这篇文章将为你揭开分区挂载的神秘面纱,从理论到实践,详细讲解分区挂载的一切。无论你是初学者还是有一定经验的用户,都能从中获取新知识,提升技能水平。…

前后端交互理解 简易表白墙(servlet)

前后端交互理解 简易表白墙(servlet) 文章目录 前后端交互理解 简易表白墙(servlet)后端核心内容前后端交互接口约定后端代码展示 上期介绍过 Servlet API ,本篇文章目的是借助 servlet 做出一个完整的网站。在一个网站…

RabbitMQ应用场景

1、异步处理 假设想象一下我们做一个商城项目,在用户支付模块中,可能会涉及到其它业务,比如:积分折扣、消费券、短信验证等功能。我们传统的执行步骤是逐步执行,也就是说当用户点击支付 ----> 积分折扣 ----> 消…

Docker进阶:深入了解 Dockerfile

Docker进阶:深入了解 Dockerfile 一、Dockerfile 概述二、Dockerfile 优点三、Dockerfile 编写规则四、Dockerfile 中常用的指令1、FROM2、LABEL3、RUN4、CMD5、ENTRYPOINT6、COPY7、ADD8、WORKDIR9、 ENV10、EXPOSE11、VOLUME12、USER13、注释14、ONBUILD 命令15、…

区块链基础知识(上):区块链基本原理、加密哈希、公钥加密

目录 基本原理 加密哈希: 公钥加密: 希望有人向你发送只有你才能打开的加密文档/消息时使用 PKC 希望向其他人发送加密文档/消息并证明它确实由你发送时使用 PKC 使用 PKC 和加密哈希对文档/消息进行数字签名 交易哈希链使用数字签名转让数字资产所…

【洛谷 P8781】[蓝桥杯 2022 省 B] 修剪灌木 题解(模拟+差分)

[蓝桥杯 2022 省 B] 修剪灌木 题目描述 爱丽丝要完成一项修剪灌木的工作。 有 N N N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木,让灌木的高度变为 0 0 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木…

centos 系统 yum 无法安装(换国内镜像地下)

centos 系统 yum 因为无法连接到国外的官网而无法安装,问题如下图: 更换阿里镜像,配置文件路径:/etc/yum.repos.d/CentOS-Base.repo(如果目录有多余的文件可以移动到子目录,以免造成影响) bas…

docker使用jupyter/datascience-notebook,重置密码,并且设置各类易用参数

前言 前一篇文章写了自己安装conda环境,然后添加C、C语言环境等,那时候就在想,有没有现成的docker可以用,后来搜了一下docker的网上镜像,还真的有: 可以看到有一个人的镜像,星星是最多的&#x…

React-嵌套路由

1.概念 说明&#xff1a;在一级路由中又内嵌了其他路由&#xff0c;这种关系就叫做嵌套路由&#xff0c;嵌套至一级路由内的路由又称作二级路由。 2.实现步骤 说明&#xff1a;使用childen属性配置路由嵌套关系&#xff0c;使用<Outlet/>组件配置二级路由渲染的位置。…

基于springboot实现驾校信息管理系统项目【项目源码+论文说明】

基于springboot实现驾校信息管理系统演示 摘要 随着人们生活水平的不断提高&#xff0c;出行方式多样化&#xff0c;也以私家车为主&#xff0c;那么既然私家车的需求不断增长&#xff0c;那么基于驾校的考核管理也就不断增强&#xff0c;那么业务系统也就慢慢的随之加大。信息…

[保姆级教程]Windows安装MongoDB教程

文章目录 导文MongoDB安装包下载1.点击进入mongodb官网2.点击MongoDB Community Edition&#xff08;社区版&#xff09;&#xff0c;进入下图界面3.选择版本4.下载5.安装6.勾选同意协议&#xff0c;点击“Next"7.选择自定义安装8.点击“Next"9.修改到合适的地址10.点…

Tensorflow实现手写数字识别

模型架构 具有10个神经元&#xff0c;对应10个类别&#xff08;0-9的数字&#xff09;。使用softmax激活函数&#xff0c;对多分类问题进行概率归一化。输出层 (Dense):具有64个神经元。激活函数为ReLU。全连接层 (Dense):将二维数据展平成一维&#xff0c;为全连接层做准备。展…