<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0445. 兩數相加 II ## 題目地址(445. 兩數相加 II) <https://leetcode-cn.com/problems/add-two-numbers-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給你兩個 非空 鏈表來代表兩個非負整數。數字最高位位于鏈表開始位置。它們的每個節點只存儲一位數字。將這兩數相加會返回一個新的鏈表。 你可以假設除了數字 0 之外,這兩個數字都不會以零開頭。 進階: 如果輸入鏈表不能修改該如何處理?換句話說,你不能對列表中的節點進行翻轉。 示例: 輸入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出:7 -> 8 -> 0 -> 7 ``` ``` ## 前置知識 - 鏈表 - 棧 ## 公司 - 騰訊 - 百度 - 字節 ## 思路 由于需要從低位開始加,然后進位。 因此可以采用棧來簡化操作。 依次將兩個鏈表的值分別入棧 stack1 和 stack2,然后相加入棧 stack,進位操作用一個變量 carried 記錄即可。 最后根據 stack 生成最終的鏈表即可。 > 也可以先將兩個鏈表逆置,然后相加,最后將結果再次逆置。 ## 關鍵點解析 - 棧的基本操作 - carried 變量記錄進位 - 循環的終止條件設置成`stack.length > 0` 可以簡化操作 - 注意特殊情況, 比如 1 + 99 = 100 ## 代碼 - 語言支持:JS,C++, Python3 JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=445 lang=javascript * * [445] Add Two Numbers II */</span> <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */</span> <span class="hljs-keyword">var</span> addTwoNumbers = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">l1, l2</span>) </span>{ <span class="hljs-keyword">const</span> stack1 = []; <span class="hljs-keyword">const</span> stack2 = []; <span class="hljs-keyword">const</span> stack = []; <span class="hljs-keyword">let</span> cur1 = l1; <span class="hljs-keyword">let</span> cur2 = l2; <span class="hljs-keyword">let</span> curried = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (cur1) { stack1.push(cur1.val); cur1 = cur1.next; } <span class="hljs-keyword">while</span> (cur2) { stack2.push(cur2.val); cur2 = cur2.next; } <span class="hljs-keyword">let</span> a = <span class="hljs-params">null</span>; <span class="hljs-keyword">let</span> b = <span class="hljs-params">null</span>; <span class="hljs-keyword">while</span> (stack1.length > <span class="hljs-params">0</span> || stack2.length > <span class="hljs-params">0</span>) { a = <span class="hljs-params">Number</span>(stack1.pop()) || <span class="hljs-params">0</span>; b = <span class="hljs-params">Number</span>(stack2.pop()) || <span class="hljs-params">0</span>; stack.push((a + b + curried) % <span class="hljs-params">10</span>); <span class="hljs-keyword">if</span> (a + b + curried >= <span class="hljs-params">10</span>) { curried = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { curried = <span class="hljs-params">0</span>; } } <span class="hljs-keyword">if</span> (curried === <span class="hljs-params">1</span>) { stack.push(<span class="hljs-params">1</span>); } <span class="hljs-keyword">const</span> dummy = {}; <span class="hljs-keyword">let</span> current = dummy; <span class="hljs-keyword">while</span> (stack.length > <span class="hljs-params">0</span>) { current.next = { val: stack.pop(), next: <span class="hljs-params">null</span> }; current = current.next; } <span class="hljs-keyword">return</span> dummy.next; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">addTwoNumbers</span><span class="hljs-params">(ListNode* l1, ListNode* l2)</span> </span>{ <span class="hljs-keyword">auto</span> carry = <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> ret = (ListNode*)<span class="hljs-params">nullptr</span>; <span class="hljs-keyword">auto</span> s1 = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>(); toStack(l1, s1); <span class="hljs-keyword">auto</span> s2 = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>(); toStack(l2, s2); <span class="hljs-keyword">while</span> (!s1.empty() || !s2.empty() || carry != <span class="hljs-params">0</span>) { <span class="hljs-keyword">auto</span> v1 = <span class="hljs-params">0</span>; <span class="hljs-keyword">auto</span> v2 = <span class="hljs-params">0</span>; <span class="hljs-keyword">if</span> (!s1.empty()) { v1 = s1.back(); s1.pop_back(); } <span class="hljs-keyword">if</span> (!s2.empty()) { v2 = s2.back(); s2.pop_back(); } <span class="hljs-keyword">auto</span> v = v1 + v2 + carry; carry = v / <span class="hljs-params">10</span>; <span class="hljs-keyword">auto</span> tmp = <span class="hljs-keyword">new</span> ListNode(v % <span class="hljs-params">10</span>); tmp->next = ret; ret = tmp; } <span class="hljs-keyword">return</span> ret; } <span class="hljs-keyword">private</span>: <span class="hljs-title">// 此處若返回而非傳入vector,跑完所有測試用例多花8ms</span> <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">toStack</span><span class="hljs-params">(<span class="hljs-keyword">const</span> ListNode* l, <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& ret)</span> </span>{ <span class="hljs-keyword">while</span> (l != <span class="hljs-params">nullptr</span>) { ret.push_back(l->val); l = l->next; } } }; <span class="hljs-title">// 逆置,相加,再逆置。跑完所有測試用例比第一種解法少花4ms</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">addTwoNumbers</span><span class="hljs-params">(ListNode* l1, ListNode* l2)</span> </span>{ <span class="hljs-keyword">auto</span> rl1 = reverseList(l1); <span class="hljs-keyword">auto</span> rl2 = reverseList(l2); <span class="hljs-keyword">auto</span> ret = add(rl1, rl2); <span class="hljs-keyword">return</span> reverseList(ret); } <span class="hljs-keyword">private</span>: <span class="hljs-function">ListNode* <span class="hljs-title">reverseList</span><span class="hljs-params">(ListNode* head)</span> </span>{ ListNode* prev = <span class="hljs-params">NULL</span>; ListNode* cur = head; ListNode* next = <span class="hljs-params">NULL</span>; <span class="hljs-keyword">while</span> (cur != <span class="hljs-params">NULL</span>) { next = cur->next; cur->next = prev; prev = cur; cur = next; } <span class="hljs-keyword">return</span> prev; } <span class="hljs-function">ListNode* <span class="hljs-title">add</span><span class="hljs-params">(ListNode* l1, ListNode* l2)</span> </span>{ ListNode* ret = <span class="hljs-params">nullptr</span>; ListNode* cur = <span class="hljs-params">nullptr</span>; <span class="hljs-keyword">int</span> carry = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (l1 != <span class="hljs-params">nullptr</span> || l2 != <span class="hljs-params">nullptr</span> || carry != <span class="hljs-params">0</span>) { carry += (l1 == <span class="hljs-params">nullptr</span> ? <span class="hljs-params">0</span> : l1->val) + (l2 == <span class="hljs-params">nullptr</span> ? <span class="hljs-params">0</span> : l2->val); <span class="hljs-keyword">auto</span> temp = <span class="hljs-keyword">new</span> ListNode(carry % <span class="hljs-params">10</span>); carry /= <span class="hljs-params">10</span>; <span class="hljs-keyword">if</span> (ret == <span class="hljs-params">nullptr</span>) { ret = temp; cur = ret; } <span class="hljs-keyword">else</span> { cur->next = temp; cur = cur->next; } l1 = l1 == <span class="hljs-params">nullptr</span> ? <span class="hljs-params">nullptr</span> : l1->next; l2 = l2 == <span class="hljs-params">nullptr</span> ? <span class="hljs-params">nullptr</span> : l2->next; } <span class="hljs-keyword">return</span> ret; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for singly-linked list.</span> <span class="hljs-title"># class ListNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.next = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">addTwoNumbers</span><span class="hljs-params">(self, l1: ListNode, l2: ListNode)</span> -> ListNode:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">listToStack</span><span class="hljs-params">(l: ListNode)</span> -> list:</span> stack, c = [], l <span class="hljs-keyword">while</span> c: stack.append(c.val) c = c.next <span class="hljs-keyword">return</span> stack <span class="hljs-title"># transfer l1 and l2 into stacks</span> stack1, stack2 = listToStack(l1), listToStack(l2) <span class="hljs-title"># add stack1 and stack2</span> diff = abs(len(stack1) - len(stack2)) stack1 = ([<span class="hljs-params">0</span>]*diff + stack1 <span class="hljs-keyword">if</span> len(stack1) < len(stack2) <span class="hljs-keyword">else</span> stack1) stack2 = ([<span class="hljs-params">0</span>]*diff + stack2 <span class="hljs-keyword">if</span> len(stack2) < len(stack1) <span class="hljs-keyword">else</span> stack2) stack3 = [x + y <span class="hljs-keyword">for</span> x, y <span class="hljs-keyword">in</span> zip(stack1, stack2)] <span class="hljs-title"># calculate carry for each item in stack3 and add one to the item before it</span> carry = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i, val <span class="hljs-keyword">in</span> enumerate(stack3[::<span class="hljs-params">-1</span>]): index = len(stack3) - i - <span class="hljs-params">1</span> carry, stack3[index] = divmod(val + carry, <span class="hljs-params">10</span>) <span class="hljs-keyword">if</span> carry <span class="hljs-keyword">and</span> index == <span class="hljs-params">0</span>: stack3 = [<span class="hljs-params">1</span>] + stack3 <span class="hljs-keyword">elif</span> carry: stack3[index - <span class="hljs-params">1</span>] += <span class="hljs-params">1</span> <span class="hljs-title"># transfer stack3 to a linkedList</span> result = ListNode(<span class="hljs-params">0</span>) c = result <span class="hljs-keyword">for</span> item <span class="hljs-keyword">in</span> stack3: c.next = ListNode(item) c = c.next <span class="hljs-keyword">return</span> result.next ``` ``` **復雜度分析** 其中 M 和 N 分別為兩個鏈表的長度。 - 時間復雜度:O(M+N)O(M + N)O(M+N) - 空間復雜度:O(M+N)O(M + N)O(M+N) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看