ching/blog
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
blog/public/2020/04/14/leetcode-add-two-numbers-ii/index.html
Ching 482b55e66d feat(package.json): 重装依赖 
重装依赖

Signed-off-by: Ching <loooching@gmail.com>
2022-02-02 21:07:01 +08:00

14 lines
12 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<!DOCTYPE html><html lang="zh-CN"><head><meta charset="utf-8"><meta name="X-UA-Compatible" content="IE=edge"><title> leetcode-add-two-numbers-ii · MarkDown</title><meta name="description" content="leetcode-add-two-numbers-ii - Ching"><meta name="viewport" content="width=device-width, initial-scale=1"><link rel="short icon" href="/favicon.png"><link rel="stylesheet" href="/css/apollo.css"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,600" type="text/css"><meta name="generator" content="Hexo 6.0.0"><link rel="alternate" href="/atom.xml" title="MarkDown" type="application/atom+xml">
</head><body><header><a href="/" class="logo-link"><img src="/logo.png"></a><ul class="nav nav-list"><li class="nav-list-item"><a href="/" target="_self" class="nav-list-link">ALL</a></li><li class="nav-list-item"><a href="/categories/leetcode/" target="_self" class="nav-list-link">LEETCODE</a></li><li class="nav-list-item"><a href="/atom.xml" target="_self" class="nav-list-link">RSS</a></li></ul></header><section class="container"><div class="post"><article class="post-block"><h1 class="post-title">leetcode-add-two-numbers-ii</h1><div class="post-meta"><div class="post-time">2020年4月14日</div></div><div class="post-content"><h3 id="445-两数相加-II"><a href="#445-两数相加-II" class="headerlink" title="445. 两数相加 II"></a>445. 两数相加 II</h3><p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/add-two-numbers-ii/">题目</a></p>
<span id="more"></span>
<p>看到顺序的链表就想到用倒序链表的方法做，折腾了半天</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">ListNode</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, x</span>):</span></span><br><span class="line"> self.val = x</span><br><span class="line"> self.<span class="built_in">next</span> = <span class="literal">None</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">addTwoNumbers</span>(<span class="params">self, l1: ListNode, l2: ListNode</span>) -&gt; ListNode:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">_reverse</span>(<span class="params">l</span>):</span></span><br><span class="line"> <span class="keyword">if</span> l.<span class="built_in">next</span>:</span><br><span class="line"> last = _reverse(l.<span class="built_in">next</span>)</span><br><span class="line"> l.<span class="built_in">next</span>.<span class="built_in">next</span> = l</span><br><span class="line"> l.<span class="built_in">next</span> = <span class="literal">None</span></span><br><span class="line"> <span class="keyword">return</span> last</span><br><span class="line"> <span class="keyword">return</span> l</span><br><span class="line"></span><br><span class="line"> l1e = _reverse(l1)</span><br><span class="line"> l2e = _reverse(l2)</span><br><span class="line"> new_l = ListNode(<span class="number">0</span>)</span><br><span class="line"> head = new_l</span><br><span class="line"> c = <span class="number">0</span></span><br><span class="line"> <span class="keyword">import</span> ipdb; ipdb.set_trace()</span><br><span class="line"> <span class="keyword">while</span> l1e <span class="keyword">and</span> l2e:</span><br><span class="line"> new_val = l1e.val + l2e.val</span><br><span class="line"> <span class="keyword">if</span> c==<span class="number">1</span>:</span><br><span class="line"> new_val += <span class="number">1</span></span><br><span class="line"> c = <span class="number">0</span></span><br><span class="line"> <span class="keyword">if</span> new_val &gt;= <span class="number">10</span>:</span><br><span class="line"> new_val -= <span class="number">10</span></span><br><span class="line"> c = <span class="number">1</span></span><br><span class="line"></span><br><span class="line"> new_l.val = new_val</span><br><span class="line"> next_n = <span class="literal">None</span></span><br><span class="line"> <span class="keyword">if</span> l1e.<span class="built_in">next</span> <span class="keyword">and</span> l2e.<span class="built_in">next</span> <span class="keyword">or</span> c:</span><br><span class="line"> next_n = ListNode(c)</span><br><span class="line"> new_l.<span class="built_in">next</span> = next_n</span><br><span class="line"> new_l = next_n</span><br><span class="line"> l1e = l1e.<span class="built_in">next</span></span><br><span class="line"> l2e = l2e.<span class="built_in">next</span></span><br><span class="line"> <span class="keyword">if</span> l2e:</span><br><span class="line"> l1e = l2e</span><br><span class="line"> <span class="keyword">if</span> <span class="keyword">not</span> l1e <span class="keyword">and</span> c:</span><br><span class="line"> l1e = ListNode(<span class="number">0</span>)</span><br><span class="line"> <span class="keyword">while</span> l1e:</span><br><span class="line"> new_l.val = l1e.val</span><br><span class="line"> new_l.val += c</span><br><span class="line"> c = <span class="number">0</span></span><br><span class="line"> <span class="keyword">if</span> new_l.val &gt;= <span class="number">10</span>:</span><br><span class="line"> c = <span class="number">1</span></span><br><span class="line"> new_l.val -= <span class="number">10</span></span><br><span class="line"> l1e = l1e.<span class="built_in">next</span></span><br><span class="line"> <span class="keyword">if</span> l1e:</span><br><span class="line"> new_l.<span class="built_in">next</span> = ListNode(<span class="number">0</span>)</span><br><span class="line"> new_l = new_l.<span class="built_in">next</span></span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> new_l.<span class="built_in">next</span> = ListNode(<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> _reverse(head)</span><br><span class="line"></span><br><span class="line"> <span class="comment"># 84 ms 13.9 MB</span></span><br></pre></td></tr></table></figure>
<p>最后面各种进位的处理应该还可以更清晰优雅一些，但是懒得搞了，感觉很蠢。翻了答案看到了小 tips，需要倒序处理的情况可以用栈。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">addTwoNumbers</span>(<span class="params">self, l1: ListNode, l2: ListNode</span>) -&gt; ListNode:</span></span><br><span class="line"> s1, s2 = [], []</span><br><span class="line"> <span class="keyword">while</span> l1:</span><br><span class="line"> s1.append(l1.val)</span><br><span class="line"> l1 = l1.<span class="built_in">next</span></span><br><span class="line"> <span class="keyword">while</span> l2:</span><br><span class="line"> s2.append(l2.val)</span><br><span class="line"> l2 = l2.<span class="built_in">next</span></span><br><span class="line"> ans = <span class="literal">None</span></span><br><span class="line"> carry = <span class="number">0</span></span><br><span class="line"> <span class="keyword">while</span> s1 <span class="keyword">or</span> s2 <span class="keyword">or</span> carry != <span class="number">0</span>:</span><br><span class="line"> a = <span class="number">0</span> <span class="keyword">if</span> <span class="keyword">not</span> s1 <span class="keyword">else</span> s1.pop()</span><br><span class="line"> b = <span class="number">0</span> <span class="keyword">if</span> <span class="keyword">not</span> s2 <span class="keyword">else</span> s2.pop()</span><br><span class="line"> cur = a + b + carry</span><br><span class="line"> carry = cur // <span class="number">10</span></span><br><span class="line"> cur %= <span class="number">10</span></span><br><span class="line"> curnode = ListNode(cur)</span><br><span class="line"> curnode.<span class="built_in">next</span> = ans</span><br><span class="line"> ans = curnode</span><br><span class="line"> <span class="keyword">return</span> ans</span><br><span class="line"></span><br><span class="line">作者：LeetCode-Solution</span><br><span class="line">链接：https://leetcode-cn.com/problems/add-two-numbers-ii/solution/liang-shu-xiang-jia-ii-by-leetcode-solution/</span><br><span class="line">来源：力扣（LeetCode）</span><br><span class="line">著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。</span><br></pre></td></tr></table></figure>
<p>不过就执行效率来看差不多。</p>
</div></article></div></section><footer><div class="paginator"><a href="/2020/04/16/leetcode-01-matrix/" class="prev">PRVE</a><a href="/2020/04/14/leetcode-design-twitter/" class="next">NEXT</a></div><div class="copyright"><p>© 2016 - 2022 <a href="http://blog.tunpok.com">Ching</a>, unless otherwise noted.</p></div></footer><script src="https://cdn.bootcss.com/mathjax/2.5.3/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script></body></html>
Reference in New Issue View Git Blame Copy Permalink