LeetCode攀登之旅(1)
- 2019 年 10 月 5 日
- 筆記
LeetCode攀登之旅(1)
1.題目
2.解法
2.1 解法一
2.2 解法二
3.結果
4.作者的話
1.題目
Question:
給定兩個非空鏈表來表示兩個非負整數。位數按照逆序方式存儲，它們的每個節點只存儲單個數字。將兩數相加返回一個新的鏈表。
你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
2.解法
2.1 解法一
【Thinking:】
特殊情況:
兩個鏈表開頭均為0，直接返回其中一個鏈表即可；第一個鏈表開頭為0，第二個鏈表開頭不為0，返回第二個鏈表；第一個鏈表開頭不為0，第二個鏈表開頭為0，返回第一個鏈表。
其他情況如下：
如上例子所示得到807，然後逆向翻轉即可得到7->0->8,那麼怎麼得到807呢，這個直接看上面Explanation：342+465，那麼342與564又怎麼得到呢？
很簡單，分別對兩個鏈表逆轉組合的數即為這兩個數，那麼在鏈表操作，又如何得到這兩個數？
以其中一個數字342為例子，他是由2*1+4*10+3*100得到的，那麼只需要設置個參數t，首次賦值t=1,後面每次乘以10，作累加即可。另外一個數字同此方法，那麼兩數相加得到807，怎麼展開成7、0、8，並分別賦給鏈表節點呢。
- 將807每次除以10，所得的餘數剛好為7，繼續以807/10的結果按照前面操作依次得到0、8；
- 在每次得到的數字7或者0、8的同時，可通過創建動態鏈表節點，並賦值即可。
到這裡就有問題了，你怎麼保證兩數相加所得到的數不超過int範圍。。。萬一所給的鏈表很長，豈不是一下子就越界了。。那麼以下程式碼運行就出現了這種問題。。所以不建議。
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode* p=(struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode *s, *r=p; //r 為表尾指針 int t=1; int a=0,b=0,c; if(l1->val==0&&l2->val==0) { return l1; } else if(l1->val==0&&l2->val!=0) { return l2; } else if(l1->val!=0&&l2->val==0) { return l1; } else { while(l1) { a += t*(l1->val); l1 = l1->next; t *= 10; } t=1; while(l2) { b += t*(l2->val); l2 = l2->next; t *= 10; } c = a + b; while(c) { s=(struct ListNode *)malloc(sizeof(struct ListNode)); s->val=c%10; r->next=s; r=s; c=c/10; } r->next = NULL; return p->next; } }
2.2 解法二
【Thinking:】
特殊情況：鏈表一為空，返回鏈表二；鏈表二為空，返回鏈表一；
當鏈表一或者鏈表二一開始都不為空時，思考如下：
# 正方向直接算結果 (2 -> 4 -> 3) (5 -> 6 -> 4) (7 -> 0 -> 8)
那就是，當對應位置上的數相加超過10，就會使得下一位+1，有點類似於普通的兩數相加，只不過反過來了。看出以上規律了？
那麼我們這裡很明確，因為當前位置上的數，最多兩個9，和最大18，向後進位最多1，也就是當前位置上的兩個數之和只要超過10，那麼讓他往後加上一個flag數即可，此處的flag為0或者1。
當前位置最終的數為兩個鏈表對應位置數之和除以10的餘數！
下一位是否進位通過前面一位對應兩個鏈表相加，除以10的結果向前取整！
【c語言實現】
那麼接下來，進入演算法實現環節，首先來看c語言實現：
- 定義一個頭結點head，並賦初值為0，可以不賦值；
- 定義動態節點s，此節點對應的值為每次兩鏈表運算所得的數；
- 定義r節點，表示尾節點，採用尾插法，每次鏈向s；
- 特殊情況處理；
- 兩鏈表循環內部操作；
- 利用尾節點直接指向頭節點的下一個節點，並釋放頭結點，返回r所指的head的下一個節點，即為最終結果。
struct ListNode * addTwoNumbers( struct ListNode * l1, struct ListNode * l2 ) { struct ListNode * head, *r, *s; int tr; head = (struct ListNode *)malloc( sizeof(struct ListNode) ); head->val = 0; r = head; if (l1 == NULL) return(l2); if (l2 == NULL) return(l1); int tsum; int flag = 0; while (l1||l2) { tsum = 0; if (l1) { tsum += l1->val; l1 = l1->next; } if (l2) { tsum += l2->val; l2 = l2->next; } tr = (tsum + flag) % 10; flag = (int) ( (tsum + flag) / 10); s = (struct ListNode * ) malloc( sizeof(struct ListNode) ); s->val = tr; r->next = s; r = r->next; } if ( flag ) { s = (struct ListNode *)malloc( sizeof(struct ListNode) ); s->val = 1; r->next = s; r = s; } r->next = NULL; r = head->next; free(head); return(r); }
【python語言實現】
- c與py鏈表操作不同
python鏈表操作與c語言鏈表操作不同，在python中直接使用ListNode(0)即可表示為當前節點賦值為0,並同時創建了當前節點。同理，c語言與python語言的next操作也不一樣！
- 整除，c語言中使用int強制從float轉換，而python中使用兩個/，即
//直接返迴向下取整結果。
其餘思想同上！
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ if l1 is None: return l2 if l2 is None: return l1 head = ListNode(0) r = head flag=0 while l1 or l2: tsum = 0 if l1: tsum += l1.val l1=l1.next if l2: tsum += l2.val l2=l2.next tr = ((tsum + flag) % 10) flag = ((tsum + flag) // 10) r.next = ListNode(tr) r = r.next if flag: r.next = ListNode(1) r = head.next del head return r
3.結果
LeetCode中，c語言第一次通過擊敗人數才60%左右，再次提交就100%了。哈哈~~~
c提交圖
python通過後，第一次擊敗人數95.74%，後面再提交58%。。然後再提交，就又高了，很不準確~~~
python提交圖
4.作者的話
最後，您如果覺得本公眾號對您有幫助，歡迎您多多支援，轉發，謝謝！
更多刷題，請關注本公眾號演算法系列！
