BAT面試算法進階(1)--兩數(shù)之和

一.算法題

  • 題目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

  • Example

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

二. 解決方案:

  • 題目大意:給定2個非空鏈表來表示2個非負整數(shù).位數(shù)按照逆序方式存儲,它們的每個節(jié)點只存儲單個數(shù)字,將兩數(shù)相加返回一個新的鏈表.你可以假設(shè)除了數(shù)字0之外,這2個數(shù)字都不會以零開頭.

2.1 思路

我們使用變量來跟蹤進位,并從包含最低有效位的表頭開始模擬逐位相加的過程.


Snip20180810_119.png

2.2 算法

就如同小學數(shù)學計算2個數(shù)相加一般,我們首先從低位有效位計算,也就是L1,L2的表頭第一個位置開始相加.我們進行的十進制相加,所以當計算的結(jié)果大于9時,就會造成"溢出"的現(xiàn)象.例如5+7=12.此時,我們就會把當前為的值設(shè)置為2,但是溢出的位需要進位.那么則用carry存儲,carry = 1.帶入到下一次迭代計算中.進位的carry必定是0或者1.2個數(shù)累加,需要考慮進位問題.則采用一個變量來保存進位值.

2.3 偽代碼

  • 將當前節(jié)點初始化為返回列表的啞節(jié)點;
  • 將進位carry設(shè)置為0;
  • 將p,q分別指向為列表L1,L2的頭部.
  • 遍歷列表L1,L2直到他們的尾端.
    • 將x設(shè)為節(jié)點的p的值.如果P已經(jīng)到達L1的末尾,則將其值設(shè)置為0;
    • 將y設(shè)置為節(jié)點q的值,如果q已經(jīng)到達L2的末尾,則將其值設(shè)置為0;
    • 求和 sum = x+y+carry;
    • 更新進位 carry = sum/10;
    • 創(chuàng)建一個新的節(jié)點,將其設(shè)置為下一個節(jié)點.并將當前節(jié)點移動到下一節(jié)點
    • 同時,將p,q移動到下一個節(jié)點位置.
  • 檢查carry 是否等于1,如果等于1則往列表中追加數(shù)字1到新節(jié)點中.
  • 返回啞節(jié)點的下一個節(jié)點.

2.4 復(fù)雜度分析

  • 時間復(fù)雜度: O(max(m,n)),假設(shè)m,n分別表示L1,l2長度.上面的算法最多重復(fù)max(m,n)
  • 空間復(fù)雜度:O(max(m,n)), 新列表的長度最多max(m,n)+1

2.5 參考代碼

#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* addTwoNumbers(struct ListNode * l1, struct ListNode *  l2) {
  
    struct ListNode *dummyHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p = l1, *q = l2, *curr = dummyHead;
    int carry = 0;
    while (p != NULL || q != NULL) {
        int x = (p != NULL) ? p->val : 0;
        int y = (q != NULL) ? q->val : 0;
        
        int sum = carry + x + y;
        carry = sum / 10;
        
        curr->next = (struct ListNode *)malloc(sizeof(struct ListNode));
        curr->val = sum%10;
        curr = curr->next;
        if (p != NULL) p = p->next;
        if (q != NULL) q = q->next;
    }
    if (carry > 0) {
        curr->next = (struct ListNode *)malloc(sizeof(struct ListNode));
    }
    
    return curr;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末闽铐,一起剝皮案震驚了整個濱河市冰肴,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌踩娘,老刑警劉巖表谊,帶你破解...
    沈念sama閱讀 211,743評論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件钞护,死亡現(xiàn)場離奇詭異,居然都是意外死亡爆办,警方通過查閱死者的電腦和手機难咕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,296評論 3 385
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來距辆,“玉大人余佃,你說我怎么就攤上這事√舾瘢” “怎么了咙冗?”我有些...
    開封第一講書人閱讀 157,285評論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長漂彤。 經(jīng)常有香客問我雾消,道長,這世上最難降的妖魔是什么挫望? 我笑而不...
    開封第一講書人閱讀 56,485評論 1 283
  • 正文 為了忘掉前任立润,我火速辦了婚禮,結(jié)果婚禮上媳板,老公的妹妹穿的比我還像新娘桑腮。我一直安慰自己,他們只是感情好蛉幸,可當我...
    茶點故事閱讀 65,581評論 6 386
  • 文/花漫 我一把揭開白布破讨。 她就那樣靜靜地躺著,像睡著了一般奕纫。 火紅的嫁衣襯著肌膚如雪提陶。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,821評論 1 290
  • 那天匹层,我揣著相機與錄音隙笆,去河邊找鬼。 笑死,一個胖子當著我的面吹牛撑柔,可吹牛的內(nèi)容都是我干的瘸爽。 我是一名探鬼主播,決...
    沈念sama閱讀 38,960評論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼铅忿,長吁一口氣:“原來是場噩夢啊……” “哼剪决!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起辆沦,我...
    開封第一講書人閱讀 37,719評論 0 266
  • 序言:老撾萬榮一對情侶失蹤昼捍,失蹤者是張志新(化名)和其女友劉穎识虚,沒想到半個月后肢扯,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,186評論 1 303
  • 正文 獨居荒郊野嶺守林人離奇死亡担锤,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,516評論 2 327
  • 正文 我和宋清朗相戀三年蔚晨,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片肛循。...
    茶點故事閱讀 38,650評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡铭腕,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出多糠,到底是詐尸還是另有隱情累舷,我是刑警寧澤,帶...
    沈念sama閱讀 34,329評論 4 330
  • 正文 年R本政府宣布夹孔,位于F島的核電站被盈,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏搭伤。R本人自食惡果不足惜只怎,卻給世界環(huán)境...
    茶點故事閱讀 39,936評論 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望怜俐。 院中可真熱鬧身堡,春花似錦、人聲如沸拍鲤。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,757評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽季稳。三九已至擅这,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間绞幌,已是汗流浹背蕾哟。 一陣腳步聲響...
    開封第一講書人閱讀 31,991評論 1 266
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人谭确。 一個月前我還...
    沈念sama閱讀 46,370評論 2 360
  • 正文 我出身青樓帘营,卻偏偏與公主長得像,于是被迫代替她去往敵國和親逐哈。 傳聞我的和親對象是個殘疾皇子芬迄,可洞房花燭夜當晚...
    茶點故事閱讀 43,527評論 2 349

推薦閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,738評論 0 33
  • 這些天我一直在苦惱昂秃,因為我用知乎一個月左右禀梳,越來越離不開知乎了。我越來越喜歡用手機刷知乎肠骆,當然還有其他有趣的網(wǎng)站了...
    雪莉只是新一的朋友閱讀 382評論 3 1
  • 沒有實現(xiàn)的愿望算途,具有詛咒般的力量。生命中最大的現(xiàn)實之一是你有些愿望注定不能實現(xiàn)了蚀腿,它有可能是你小時候一直想...
    鮑弘軍閱讀 426評論 0 1
  • 今天已是第60天了嘴瓤,早上主要是做肌肉訓(xùn)練和核心運動。今天的主要任務(wù)是做車的保養(yǎng)莉钙,在那足足等了三個多小時廓脆,利用這三個...
    心雨Michelle閱讀 110評論 0 1
  • 目錄 導(dǎo)語 1. Math對象 2. Date對象 3. Date對象方法的應(yīng)用——日歷插件; 4. 小結(jié) 導(dǎo)語 ...
    犯迷糊的小羊閱讀 566評論 1 4