两数相加c++_LeetCode 热题 HOT 100(01,两数相加)
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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Vue之组件之间的数据传递
- 下一篇: python编写人机交互界面_Pytho