LeetCode 2. Add Two Numbers
分類
建立時間: 2022年10月29日 03:36
更新時間: 2022年10月30日 06:07
題目
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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
給定兩個代表兩個非負整數的非空鏈結串列。這些數字以相反的順序存儲,並且它們的每個節點都包含一個數字。將兩個數字相加並且返回作為鏈結串列的總和。
您可以假設這兩個數字不包含任何前導0,除了數字0本身除外。
注: 前導0就是有像是情報員編號0028526,這種0開頭的數字
範例1:
輸入: l1 = [2,4,3], l2 = [5,6,4]
輸出: [7,0,8]
解釋: 342 + 465 = 807.
範例2:
輸入: l1 = [0], l2 = [0]
輸出: [0]
範例3:
輸入: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出: [8,9,9,9,0,0,0,1]
限制:
- 每個鏈結串列中的節點數在 [1, 100] 範圍內。
- 0 <= Node.val <= 9
- 保證該串列表示一個沒有前導零的數字。
以下以範例一為例,需注意數字以相反的順序存儲
果斷放棄的解決方法
2 + 4 * 10 + 3 * 100 = 342
這種乘10的方法會造成溢位
解決辦法
使用國小基礎的直式加法運算來解這題
342
+465
-----
807
第1步
l1[0] + l2[0] = 2 + 5 = 7
第2步
l1[1] + l2[1] = 4 + 6 = 10
寫0,然後進1位
第3步
l1[2] + l2[2] = 3 + 4 = 7
剛進1位
7 + 1 = 8
將這些步驟程式化,在程式中會有一些檢查工作
例如 4 + 6 = 10 我要寫0,並記錄要進1位
解答
python
class ListNode:
# Definition for singly-linked list.
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
# 是否進位
carry = False
# 當前 ListNode
current_list_node = None
# 上個 ListNode
last_list_node = None
result = None
while(l1 is not None or l2 is not None or carry is True):
value1 = 0
value2 = 0
if(l1 is not None):
value1 = l1.val
l1 = l1.next
if(l2 is not None):
value2 = l2.val
l2 = l2.next
# 此次節點得值
current_value = value1 + value2
if carry:
current_value += 1
carry = False
if current_value >= 10:
current_value %= 10
carry = True
current_list_node = ListNode(current_value)
if result is None:
result = current_list_node
if last_list_node is not None:
last_list_node.next = current_list_node
last_list_node = current_list_node
return result
觀看次數: 807
addleetCodenumbersprogramtwo刷題
一杯咖啡的力量,勝過千言萬語的感謝。
支持我一杯咖啡,讓我繼續創作優質內容,與您分享更多知識與樂趣!