LeetCode Digest
3 分鐘 閱讀文 (大約 486 個字)

Add Two Numbers

題目
思路：

  1. 既然 Linked List 是由個位數開始，剛好可以用小學學的加法來從個位數開始相加。所以須設計一個迴圈來執行可重複執行的加法動作，一步步構建答案所需的 linked list，一次建立一個 node，直到完成。
  2. 迴圈要可重複執行，需要有個指標，在迴圈內對該指標所指的 node 做操作，並在迴圈結束時讓指標指到下一個 node，讓下一次迴圈來操作
  3. 迴圈內算出的當下位數的答案 digit_sum % 10 的 node 為何是指定給 curr.next 而非 curr?
    • 因為迴圈結束前 curr 必須指向下一個 node，也就是 curr.next，以下分兩種情況解釋：
      • 答案放在 curr 身上：必須創造一個空的 node 來當 curr.next，而假如這次的迴圈已經是最後一次了，此 linked list 的尾巴就會多一個空的 node
      • 答案放在 curr.next 身上：迴圈結束前 curr 指向 curr.next 繼續下一次的操作，假如此次已是最後一次迴圈，也不會多出空的 node 在 linked list 末端，只會在開頭多出一個沒用到的 dummy_head 而已，因此最後回傳答案時是回傳 dummy_head.next

Python3 solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    carry = 0  # 位數相加後除以 10 得到的商
    dummy_head = ListNode()  # 用 dummy_head 保留最前面的指標，到時候才有辦法回傳答案
    curr = dummy_head        # 不能只用 `curr = ListNode()`，因為 `curr` 所指的 node 必須一直變
    while l1 or l2 or carry:  # 可以繼續加的條件
        v1 = l1 and l1.val or 0
        v2 = l2 and l2.val or 0
        digit_sum = v1 + v2 + carry
        carry = digit_sum // 10
        curr.next = ListNode(digit_sum % 10)
        curr = curr.next
        l1 = l1 and l1.next
        l2 = l2 and l2.next
    return dummy_head.next
#
Remove Duplicates from Sorted List
Search Insert Position

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×