LeetCode 熱題 HOT 100(01，兩數(shù)相加)

不夠優(yōu)秀，發(fā)量尚多，千錘百煉，方可成佛。

算法的重要性不言而喻，無論你是研究者，還是最近比較火熱的IT 打工人，都理應(yīng)需要一定的算法能力，這也是面試的必備環(huán)節(jié)，算法功底的展示往往能讓面試官眼前一亮，這也是在大多數(shù)競(jìng)爭(zhēng)者中脫穎而出的重要影響因素。

然而往往大多數(shù)人比較注重自身的實(shí)操能力，著重于對(duì)功能的實(shí)現(xiàn)，卻忽視了對(duì)算法能力的提高。有的時(shí)候采用不同的算法來解決同一個(gè)問題，運(yùn)行效率相差還是挺大的，畢竟我們最終還是需要站在客戶的角度思考問題嘛，能給用戶帶來更加極致的體驗(yàn)當(dāng)然再好不過了。

萬法皆空，因果不空。Taoye之前也不怎么情愿花費(fèi)太多的時(shí)間放在算法上，算法功底也是相當(dāng)?shù)谋∪酢＿@不，進(jìn)入到了一個(gè)新的學(xué)習(xí)階段，面對(duì)導(dǎo)師的各種“嚴(yán)刑拷打”和與身邊人的對(duì)比，才開始意識(shí)到自己“菜”的事實(shí)。

講到這，流下了沒技術(shù)的眼淚！！！

這次的題目是LeeTCode 熱題 HOT 100的第二題，難度屬于中等，涉及到了鏈表的知識(shí)。

自打接觸Python以來，都沒有從中用到過鏈表，也無法通過指針來操作鏈表。曾經(jīng)也只是在備考408，學(xué)習(xí)C的過程中刷過一些鏈表相關(guān)算法，一開始拿到這道題的時(shí)候，不知道Python如何下手，不知道怎么操作鏈表，菜是原罪(ノへ￣、)

查找資料之后才發(fā)現(xiàn)，我們操作鏈表的時(shí)候其實(shí)就是將其封裝成一個(gè)實(shí)例對(duì)象，而實(shí)例對(duì)象中存儲(chǔ)了節(jié)點(diǎn)的相關(guān)信息(其實(shí)和C中差不多)。但與C或C++中不同的是，Python沒有指針，也就沒有什么指向操作，所以從對(duì)鏈表的整體結(jié)構(gòu)理解上，Python和C、C++還是有點(diǎn)區(qū)別的。意思類似下圖：

可以理解成一種俄羅斯套娃的形式。

注意：只是理解上有所區(qū)別，其實(shí)表達(dá)的意思還是一樣的。

下面，我們就來看看這道題吧。

題目：兩數(shù)相加

給出兩個(gè) 非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來，則會(huì)返回一個(gè)新的鏈表來表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開頭。

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

思路

前面也提到了，在Python中，鏈表可以理解成一種套娃的形式，通過輸入兩個(gè)鏈表，輸出一個(gè)新的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)的產(chǎn)生過程基本一致，所以我們初步判斷通過遞歸的方法來解決該問題。

當(dāng)然了，遞歸能解決的問題，非遞歸同樣可以，只是將一次遞歸函數(shù)的調(diào)用替換成一次循環(huán)。所以下面將分別介紹兩種方法。

• 方法一：遞歸

題中給出的例子里的兩個(gè)鏈表的長度是一樣的，但題意所表明的意思是任意長度的兩個(gè)鏈表。所以，為了提高算法的“泛化性能”，在輸入兩個(gè)長度不同鏈表的前提下，我們需要對(duì)其進(jìn)行一個(gè)統(tǒng)一，就是對(duì)長度短的鏈表我們需要做一個(gè)補(bǔ)0處理。補(bǔ)0并不影響求和操作，但又方便了我們對(duì)截止遞歸的判斷。

這種處理方式在數(shù)學(xué)上還是挺常見的，比如說在求最值的時(shí)候，我們常常會(huì)用到均值不等式，但題目中給出的數(shù)值維數(shù)可能并不會(huì)明顯地滿足均值不能式，所以常常會(huì)用到一個(gè)擴(kuò)維的操作，很巧妙的將題目向均值不等式靠近，從而簡(jiǎn)化了對(duì)題目的解答，比如下面這道題的巧妙解答：

最后，左右同開5次方，再同乘27即可證畢。

回到算法題吧。

題目既然要我們求鏈表所對(duì)應(yīng)的單位數(shù)之和，那么肯定會(huì)涉及進(jìn)位，我們不妨將進(jìn)位表達(dá)為carry。至此，我們不難想到，每次的遞歸需要的參數(shù)有三個(gè)，分別是第一個(gè)鏈表中的值、第二個(gè)鏈表中的值、上一次進(jìn)位的值(非0即1)。

前面也有說到，在Python中，鏈表其實(shí)就是一個(gè)對(duì)象，而該對(duì)象中又有倆個(gè)屬性，分別是val和next，而next本身有代表一個(gè)鏈表對(duì)象。所以我們遞歸方法傳入的第一、第二個(gè)參數(shù)可以用當(dāng)前鏈表節(jié)點(diǎn)所獲取到。

判斷跳出遞歸的條件：前面，我們已經(jīng)對(duì)鏈表進(jìn)行處理過了，也就是說無論你輸入的兩個(gè)鏈表長度是否一致，我們都對(duì)其進(jìn)行了統(tǒng)一長度的處理。所以說當(dāng)我們所傳入的三個(gè)參數(shù)同時(shí)為False的時(shí)候即可跳出遞歸。舉例說明： 1、輸入兩個(gè)空鏈表和一個(gè)carry為1的參數(shù)，說明已經(jīng)產(chǎn)生了進(jìn)位，此時(shí)我們需要對(duì)其進(jìn)行處理，而非跳出遞歸。2、輸入的一個(gè)鏈表節(jié)點(diǎn)value值為5，而另一個(gè)節(jié)點(diǎn)為None，carry為0，此時(shí)我們依然需要進(jìn)行求和處理，即使另一個(gè)節(jié)點(diǎn)為None，但我們已經(jīng)對(duì)其進(jìn)行了補(bǔ)0處理。3、至于其他可能性，各位看官可自行思考。

求和處理：

求出兩個(gè)鏈表當(dāng)前value值和carry的和，并對(duì)10進(jìn)行一個(gè)divmod操作。說明： Python中divmod會(huì)返回一個(gè)元組，第一個(gè)值為進(jìn)位，第二個(gè)值為取余，比如divmod(13, 10) = (1, 3)。注意：在求和的過程中，有可能當(dāng)前節(jié)點(diǎn)為None，這個(gè)時(shí)候則需要將節(jié)點(diǎn)的value值作為0進(jìn)行求和。

實(shí)例化一個(gè)鏈表，也就是我們的目標(biāo)返回鏈表，其value值為上述的取余。注意：這里一定理解清楚題意，鏈表中的值是實(shí)際值的逆序。

result的next屬性所對(duì)應(yīng)的值本身又是一個(gè)鏈表，而對(duì)其進(jìn)行賦值的時(shí)候，我們需要調(diào)用遞歸方法。傳遞的三個(gè)參數(shù)：經(jīng)過上述過程，鏈表中的當(dāng)前值已經(jīng)處理完畢，這個(gè)時(shí)候需要處理鏈表的下一個(gè)值，也就是將下一個(gè)節(jié)點(diǎn)作為參數(shù)進(jìn)行一次遞歸。但這里需要考慮的是，假如我們的當(dāng)前節(jié)點(diǎn)為空，也就是說當(dāng)前鏈表已經(jīng)遍歷結(jié)束，則需要傳遞None給遞歸函數(shù)。

相關(guān)代碼：

class?Solution:
????def?recursion(self,?list_node1,?list_node2,?carry):
????????#?判斷跳出遞歸的條件
????????if?(list_node1?==?None)?and?(list_node2?==?None)?and?(carry?==?0):?return?None
????????#?兩個(gè)節(jié)點(diǎn)值和進(jìn)位值的求和操作，若傳入的節(jié)點(diǎn)為None，則需要將value賦值為0進(jìn)行求和，也就是補(bǔ)0
????????sum_number?=?(list_node1.val?if?list_node1?else?0)?+?(list_node2.val?if?list_node2?else?0)?+?carry
????????#?產(chǎn)生新的carry進(jìn)位值，作為下一次遞歸的判斷。
????????carry,?value?=?divmod(sum_number,?10)
????????#?實(shí)例新的節(jié)點(diǎn)(result，為返回的目標(biāo)節(jié)點(diǎn)的)，其val屬性為value
????????result?=?ListNode(value)????
????????#?進(jìn)行下一次遞歸
????????result.next?=?self.recursion(list_node1.next?if?list_node1?else?None,?list_node2.next?if?list_node2?else?None,?carry)
????????return?result

????#?主函數(shù)
????def?addTwoNumbers(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
????????return?self.recursion(l1,?l2,?0)????#?執(zhí)行入口，調(diào)用遞歸函數(shù)，傳入初試的兩個(gè)節(jié)點(diǎn)，默認(rèn)進(jìn)位為0

• 方法二：非遞歸

非遞歸的思想和遞歸差不多，只是除了返回result鏈表之外，還需要額外創(chuàng)建一個(gè)新的鏈表用于循環(huán)。

class?Solution:
????def?addTwoNumbers(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
????????#?初始node，result為返回結(jié)果鏈表，temp_node用作循環(huán)遍歷，鏈接產(chǎn)生新的節(jié)點(diǎn)
????????result?=?temp_node?=?ListNode(0)????
????????carry?=?0???#?初始進(jìn)位為0
????????while?l1?or?l2?or?carry:????#?跳出循環(huán)的條件和遞歸一樣，三者同時(shí)為False的時(shí)候跳出循環(huán)
????????????#?兩個(gè)節(jié)點(diǎn)值和進(jìn)位值的求和操作，若傳入的節(jié)點(diǎn)為None，則需要將value賦值為0進(jìn)行求和，也就是補(bǔ)0
????????????sum_number?=?(l1.val?if?l1?else?0)?+?(l2.val?if?l2?else?0)?+?carry
????????????#?l1和l2當(dāng)前節(jié)點(diǎn)操作完畢，指向下一個(gè)節(jié)點(diǎn)，準(zhǔn)備進(jìn)入下一次循環(huán)
????????????l1?=?l1.next?if?l1?else?None;?l2?=?l2.next?if?l2?else?None
????????????#?產(chǎn)生新的carry進(jìn)位值，作為下一次遞歸的判斷。
????????????carry,?value?=?divmod(sum_number,?10)
????????????#?重新賦值temp_node節(jié)點(diǎn)，不斷為result鏈表進(jìn)行延伸補(bǔ)充節(jié)點(diǎn)
????????????temp_node.next?=?ListNode(value);?temp_node?=?temp_node.next
????????return?result.next

總的來說，非遞歸表達(dá)的思想和遞歸差不多。

不過這里有一點(diǎn)值得說明下： result節(jié)點(diǎn)只在初始和最后返回時(shí)用到過，而在算法的核心while循環(huán)中并沒有用到，為什么還能返回正常的result鏈表呢？

這主要是因?yàn)?#xff0c;我們初始化創(chuàng)建的result已經(jīng)和temp_node都賦值給新的鏈表了，其中val為0，next屬性值為None，其內(nèi)存位置是固定的。而初試的result和temp_node是相等的，所指向的內(nèi)存地址是一樣的，所以我們只需要的延伸temp_node節(jié)點(diǎn)即可，而result地址不變，而result指向的下一個(gè)節(jié)點(diǎn)的地址則會(huì)隨著temp_node的變化而變化。

注意： result的內(nèi)存地址從始至終都是不變的，初試的時(shí)候和temp_node的地址是一樣，只不過之后變化的是temp_node，而result不變。我們可以在通過如下操作簡(jiǎn)單測(cè)試下這個(gè)過程：

也不知道自己表述清楚了沒有？

也不知道各位看官理解了沒有？

如果沒看懂的話，強(qiáng)烈建議重新看一遍，細(xì)細(xì)琢磨下，這個(gè)地方還是挺重要的。

• 最后

在逛討論區(qū)的時(shí)候，看到了另外一種解法，感覺這算法寫的挺優(yōu)雅的，在這里分享下。

"""
??? Author：學(xué)廢了的Kai
"""
class?Solution:
????def?addTwoNumbers(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:
????????head?=?curr?=?ListNode()
????????carry?=?val?=?0
????????while?carry?or?l1?or?l2:
????????????val?=?carry
????????????if?l1:?l1,?val?=?l1.next,?l1.val?+?val
????????????if?l2:?l2,?val?=?l2.next,?l2.val?+?val
????????????carry,?val?=?divmod(val,?10)
????????????curr.next?=?curr?=?ListNode(val)
????????return?head.next

這種解法和上面非遞歸表達(dá)的是同種思想，只不過在求sum的時(shí)候這個(gè)是疊加的形式，而非一次性求和。上面算法還有一點(diǎn)值得學(xué)習(xí)的是，在最后curr.next = curr = ListNode(val)這行代碼中，其表達(dá)的意思是如下：

curr.next?=ListNode(val)
curr?=?curr.next

Taoye也不知道為什么是這種賦值順序，按道理講應(yīng)該是先賦值curr = ListNode(val)，再賦值curr.next = curr？但經(jīng)過測(cè)試之后，上述兩行代碼塊才是正確的，暫時(shí)不知道為什么，之后有機(jī)會(huì)再回過頭看看吧。

我是Taoye，研究生在讀。愛專研，愛分享，熱衷于各種技術(shù)，學(xué)習(xí)之余喜歡下象棋、聽音樂、聊動(dòng)漫，希望借此一畝三分地記錄自己的成長過程以及生活點(diǎn)滴，也希望能結(jié)實(shí)更多志同道合的圈內(nèi)朋友，更多內(nèi)容歡迎來訪微信公主號(hào)：玩世不恭的Coder。

推薦閱讀：

LeetCode 熱題 HOT 100(00，兩數(shù)之和)
Taoye滲透到一家黑平臺(tái)總部，背后的真相細(xì)思極恐
《大話數(shù)據(jù)庫》-SQL語句執(zhí)行時(shí)，底層究竟做了什么小動(dòng)作？
那些年，我們玩過的Git，真香
基于Ubuntu+Python+Tensorflow+Jupyter notebook搭建深度學(xué)習(xí)環(huán)境
網(wǎng)絡(luò)爬蟲之頁面花式解析
手握手帶你了解Docker容器技術(shù)
一文詳解Hexo+Github小白建站
打開ElasticSearch、kibana、logstash的正確方式

總結(jié)

以上是生活随笔為你收集整理的两数相加c++_LeetCode 热题 HOT 100（01，两数相加）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。