Leetcode刷題2---兩數相加 Python

目錄

  • 題目及分析
  • 解法一: 迭代法
  • 解法二: 遞歸法
  • 解法三:反轉鏈表法

題目及分析

(力扣序號2:兩數相加)
給你兩個非空的鏈表,表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的,并且每個節點只能存儲 一位 數字。

請你將兩個數相加,并以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。
示例 1:
在這里插入圖片描述
輸入:l1 = [2,4,3], l2 = [5,6,4]
輸出:[7,0,8]
解釋:342 + 465 = 807.

示例 2:
輸入:l1 = [0], l2 = [0]
輸出:[0]

示例 3:
輸入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出:[8,9,9,9,0,0,0,1]

提示:
每個鏈表中的節點數在范圍 [1, 100] 內
0 <= Node.val <= 9
題目數據保證列表表示的數字不含前導零

解法一: 迭代法

基本思路:

  • 創建一個啞節點作為結果鏈表的頭節點。
  • 初始化一個變量carry為0,用于存儲進位值。
  • 使用一個循環遍歷兩個鏈表,直到兩個鏈表都為空且沒有進位:
    • 將兩個鏈表對應位置的值和carry相加。
    • 計算新的節點值和新的進位值。
    • 創建一個新節點,存儲計算出的節點值,并將其連接到結果鏈表的末尾。
    • 移動鏈表指針到下一個節點。
  • 返回結果鏈表的頭節點。
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 解法一:迭代法
def add_two_numbers_iterative(l1: ListNode, l2: ListNode) -> ListNode:dummy_head = ListNode(0)current = dummy_headcarry = 0while l1 or l2 or carry:val1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10current.next = ListNode(total % 10)current = current.nextif l1:l1 = l1.nextif l2:l2 = l2.nextreturn dummy_head.next

解法二: 遞歸法

基本思路:

  • 如果兩個鏈表和進位都為空,返回None。
  • 計算當前節點的和及新的進位值。
  • 創建一個新節點,存儲計算出的節點值。
  • 遞歸處理下一個位置的值和進位。
  • 返回新節點。
# 解法二:遞歸法
def add_two_numbers_recursive(l1: ListNode, l2: ListNode, carry=0) -> ListNode:if not l1 and not l2 and not carry:return Noneval1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10result = ListNode(total % 10)l1_next = l1.next if l1 else Nonel2_next = l2.next if l2 else Noneresult.next = add_two_numbers_recursive(l1_next, l2_next, carry)return result

解法三:反轉鏈表法

基本思路:

  • 由于鏈表存儲的是逆序的數字,可以將兩個鏈表反轉,使得數字變為正序。
  • 反轉后按照正常的加法計算,最后再將結果鏈表反轉,得到最終結果。
  • 這種方法需要注意鏈表的反轉和恢復。
# 解法三:反轉鏈表法
def reverse_list(head: ListNode) -> ListNode:prev = Nonecurrent = headwhile current:next_node = current.nextcurrent.next = prevprev = currentcurrent = next_nodereturn prevdef add_two_numbers_reverse(l1: ListNode, l2: ListNode) -> ListNode:l1 = reverse_list(l1)l2 = reverse_list(l2)dummy_head = ListNode(0)current = dummy_headcarry = 0while l1 or l2 or carry:val1 = l1.val if l1 else 0val2 = l2.val if l2 else 0total = val1 + val2 + carrycarry = total // 10current.next = ListNode(total % 10)current = current.nextif l1:l1 = l1.nextif l2:l2 = l2.nextreturn reverse_list(dummy_head.next)

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/diannao/40779.shtml
繁體地址,請注明出處:http://hk.pswp.cn/diannao/40779.shtml
英文地址,請注明出處:http://en.pswp.cn/diannao/40779.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

python之音頻處理(2)兩個音頻文件的合并

from pydub import AudioSegment# 加載兩個音頻文件 audio1 AudioSegment.from_file(r"D:\websiteDownload\huanxing.wav") audio2 AudioSegment.from_file(r"D:\websiteDownload\我今天被一件事情搞得很煩.wav")# 設置間隔&#xff08;單位&#xff1a;…

Altium Designer專業PCB設計軟件下載安裝 Altium Designer安裝包下載獲取

在電子設計的廣袤領域中&#xff0c;PCB設計無疑占據著重要的地位。而Altium Designer作為一款業界領先的電子設計自動化軟件&#xff0c;其提供的先進布局工具&#xff0c;無疑為設計師們打開了一扇通往高效、精確設計的大門。 在PCB設計的核心環節——布局中&#xff0c;Alti…

初學Spring之自動裝配 Bean

Bean 的作用域&#xff1a; 1.單例模式&#xff08;Spring 默認機制&#xff09; scope“singleton” 2.原型模式&#xff1a;每次從容器中 get 時&#xff0c;都會產生一個新對象 scope"prototype" 3. request、session、application&#xff0c;只能在 web 開…

《c語言結構體怎么函數傳參》

在C語言中&#xff0c;結構體&#xff08;struct&#xff09;是一種用戶自定義的數據類型&#xff0c;用于組合多個不同類型的數據成員。當你要將結構體作為參數傳遞給函數時&#xff0c;可以按照以下幾種方式進行&#xff1a; 值傳遞&#xff08;Pass by Value&#xff09;&a…

【pytorch擴展】CUDA自定義pytorch算子(簡單demo入手)

Pytorch作為一款優秀的AI開發平臺&#xff0c;提供了完備的自定義算子的規范。我們用torch開發時&#xff0c;經常會因為現有算子的不足限制我們idea的迸發。于是&#xff0c;CUDA/C自定義pytorch算子是不得不磕了。 今天通過一個小實驗來梳理自定義pytorch算子都需要做哪些準…

軟設之類的繼承與泛化,多重繼承

在類中&#xff0c;假如父類已經寫好屬性或方法&#xff0c;子類想要實現相同的功能&#xff0c;不用專門寫代碼&#xff0c;直接用專門的繼承語言繼承就可以了。 比如說有一個動物類&#xff0c;有毛色和叫這兩個屬性和方法&#xff0c;又寫了一個子類是貓類&#xff0c;貓類…

騰訊云COS分布式對象存儲

騰訊云COS分布式對象存儲 騰訊云對象存儲&#xff08;Cloud Object Storage&#xff0c;COS&#xff09;是騰訊云提供的一種用于存儲海量文件的分布式存儲服務。 騰訊云 COS 適用于多種場景&#xff0c;如靜態網站托管、大規模數據備份和歸檔、多媒體存儲和處理、移動應用數據存…

Kafka搭建(單機版)

部署前提 VMware環境 : 兩臺centos系統 Jdk包:jdk-8u202-linux-x64.tar.gz Kafka包:kafka_2.12-3.5.0.tgz Zookeeper包:apache-zookeeper-3.7.2-bin.tar.gz 百度網盤自取: 鏈接: https://pan.baidu.com/s/11EWuhBoSmH3musd_3Rgodw?pwde32t 提取碼: e32t Kafka搭建&#xff08;…

Camtasia 2024新功能 Camtasia2024更新介紹:AI剪輯助力微課制作 Camtasia2024密鑰 Camtasia2023免費升級更新

Camtasia 是一款功能強大的屏幕錄制和視頻編輯軟件&#xff0c;廣泛應用于教育、商業和娛樂領域。無論是創建教學視頻、產品演示、教程還是營銷內容&#xff0c;Camtasia都能提供專業的工具和功能&#xff0c;幫助用戶制作高質量的視頻內容。 Camtasia 2024 中文免費安裝包百度…

暑假學習DevEco Studio第2天

學習目標&#xff1a; 掌握頁面跳轉 學習內容&#xff1a; 跳轉頁面 創建頁面&#xff1a; 在“project”窗口。打開“entry>src>main>ets”,右擊“pages”&#xff0c;選擇“New>ArkTS File”,命名“Second”&#xff0c;點擊回車鍵。 在頁面的路由&#xff0…

昇思25天學習打卡營第16天|文本解碼原理——以MindNLP為例

在大模型中&#xff0c;文本解碼通常是指在自然語言處理&#xff08;NLP&#xff09;任務中使用的大型神經網絡模型&#xff08;如Transformer架構的模型&#xff09;將編碼后的文本數據轉換回可讀的原始文本的過程。這些模型在處理自然語言時&#xff0c;首先將輸入文本&#…

【Unix/Linux】Unix/Linux如何查看系統版本

Unix和Linux查看系統版本的指令有些區別&#xff0c;下面分別介紹: 一.Unix查看系統版本 在Unix系統中&#xff0c;查看系統版本的方法可能會根據具體的Unix操作系統而有所不同。以下是一些通用的方法&#xff0c;適用于多種Unix系統&#xff0c;包括但不限于Solaris、AIX、H…

vienna整流器過零畸變原因分析

Vienna整流器是一種常見的三電平功率因數校正&#xff08;PFC&#xff09;整流器&#xff0c;廣泛應用于電源和電能質量控制領域。由于其高效率、高功率密度和低諧波失真的特點&#xff0c;Vienna整流器在工業和電力電子應用中具有重要地位。然而&#xff0c;在實際應用中&…

ssh:(xshell)遠程連接失敗

項目場景&#xff1a; 提示&#xff1a;這里簡述項目相關背景&#xff1a; 云服務器遠程連接失敗 xshell 遠程連接失敗 xshell (ssh客戶端&#xff09; ---------------------------------------------安全組----------防火墻-------黑白名單-----SSH服務 問題排查 1. 安全…

Playwright之錄制腳本轉Page Object類

Playwright之錄制腳本轉Page Object類 設計思路 &#xff1a; 我們今天UI自動化設計的時候&#xff0c;通常會遵循一些設計模式&#xff0c;例如Page Object模式。但是自己找元素再去填寫有一些麻煩&#xff0c;所以我們可以通過拆解錄制的腳本&#xff0c;將其中的元素提取出來…

DALL-E、Stable Diffusion 等 20+ 圖像生成模型綜述

二、任務場景 2.1. 無條件生成 無條件生成是指生成模型在生成圖像時不受任何額外條件或約束的影響。模型從學習的數據分布中生成圖像&#xff0c;而不需要關注輸入條件。 2.2. 有條件生成 有條件生成是指生成模型在生成圖像時受到額外條件或上下文的影響。這些條件可以是類別…

Vscode 保存代碼,代碼自動格式化

我這里使用的插件是Prettier-Code formatter&#xff1a;自動縮進整理代碼的格式&#xff0c;使用方法如下&#xff1a; 先在vscode商店找到插件并安裝&#xff1a;安裝插件之后&#xff0c;隨便找到一個項目文件&#xff0c;右鍵選擇格式化文檔&#xff1a;選中我們安裝的插件…

掌握Vim的會話之道:深度解析會話管理功能

掌握Vim的會話之道&#xff1a;深度解析會話管理功能 在高效的文本編輯工作流中&#xff0c;能夠保存和恢復編輯會話是極其重要的。Vim&#xff0c;作為一個功能強大的文本編輯器&#xff0c;提供了會話管理功能&#xff0c;允許用戶保存當前的工作狀態&#xff0c;并在之后重…

spring6框架解析(by尚硅谷)

文章目錄 spring61. 一些基本的概念、優勢2. 入門案例實現maven聚合工程創建步驟分析實現過程 3. IoC&#xff08;Inversion of Control&#xff09;基于xml的bean環境搭建獲取bean獲取接口創建實現類依賴注入 setter注入 和 構造器注入原生方式的setter注入原生方式的構造器注…

Java 多線程stream流按行讀取文件

stream并行流快&#xff08;文件11g&#xff09; try (Stream<String> lines Files.lines(filePath)) {lines.parallel().forEach(str -> operatePartData(str, allDataList)); } catch (IOException e) {throw new RuntimeException(e); }線程池慢&#xff08;文件…