建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「程序新視界」，作者丑胖俠二師兄 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序新視界眾號(hào)。
10余年的湘潭縣網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷推廣的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整湘潭縣建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)建站從事“湘潭縣網(wǎng)站設(shè)計(jì)”,“湘潭縣網(wǎng)站推廣”以來(lái)，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
前言
一道小學(xué)加法題，竟然在LeetCode上被標(biāo)記為“中等”難度，有些人“流下了沒(méi)有技術(shù)的眼淚”，有些人“一頓操作猛如虎，一看擊敗百分五……”。今天我們來(lái)看看LeetCode的第二道題“兩數(shù)相加”。
“兩數(shù)相加”
先來(lái)看題目描述，對(duì)應(yīng)官方鏈接：https://leetcode-cn.com/problems/add-two-numbers
給你兩個(gè)非空的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照逆序的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ)一位數(shù)字。請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。你可以假設(shè)除了數(shù)字0之外，這兩個(gè)數(shù)都不會(huì)以0開(kāi)頭。
兩數(shù)相加
鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
- public class ListNode {
- int val;
- ListNode next;
- ListNode() {}
- ListNode(int val) { this.val = val; }
- ListNode(int val, ListNode next) { this.val = val; this.next = next; }
- }
題目說(shuō)明
題目描述相對(duì)來(lái)說(shuō)比較繞，我們可以直接理解為兩個(gè)多位的整數(shù)相加，只不過(guò)整數(shù)的每一位都是通過(guò)鏈表進(jìn)行存儲(chǔ)。比如，整數(shù)342，通過(guò)鏈表存儲(chǔ)正常來(lái)說(shuō)應(yīng)該是3->4->2，但是計(jì)算時(shí)，往往需要從低位開(kāi)始計(jì)算，逢十進(jìn)一，所以題目中直接將整數(shù)表示為2->4->3，這樣反而不用將鏈表順序進(jìn)行反轉(zhuǎn)了，直接相加就可以了。
兩數(shù)相加
需要注意的是如果兩個(gè)鏈表的長(zhǎng)度不同，則可以認(rèn)為長(zhǎng)度短的鏈表的后面有若干個(gè) 0 ，鏈表遍歷結(jié)束，則如果進(jìn)位值大于0，則還需要在結(jié)果鏈表中附加一個(gè)值為1的節(jié)點(diǎn)。
方法一：模擬
上面已經(jīng)提到，鏈表是逆序的，因此直接對(duì)應(yīng)數(shù)字相加即可?；静僮鞅闅v兩個(gè)列表，逐位計(jì)算它們的和，并與當(dāng)前位置的進(jìn)位值相加。
比如，兩個(gè)鏈表對(duì)應(yīng)位的數(shù)字分別為n1和n2，進(jìn)位為carry(通常為0和1)，則它們的和為(n1 + n2 + carry)，對(duì)應(yīng)位上數(shù)字變?yōu)?n1 + n2 + carry)%10，新的進(jìn)位為(n1 + n2 + carry)/10。
如果兩個(gè)鏈表長(zhǎng)度不一樣，長(zhǎng)度短的鏈表后續(xù)對(duì)應(yīng)位上值均為0即可。如果遍歷結(jié)束之后，carray大于0(也就是等于1)，則在結(jié)構(gòu)鏈表后面新增一個(gè)節(jié)點(diǎn)，
實(shí)現(xiàn)代碼如下：
- class Solution {
- public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
- ListNode head = null, tail = null;
- int carry = 0;
- while (l1 != null || l2 != null) {
- int n1 = l1 != null ? l1.val : 0;
- int n2 = l2 != null ? l2.val : 0;
- int sum = n1 + n2 + carry;
- if (head == null) {
- head = tail = new ListNode(sum % 10);
- } else {
- tail.next = new ListNode(sum % 10);
- tail = tail.next;
- }
- carry = sum / 10;
- if (l1 != null) {
- l1 = l1.next;
- }
- if (l2 != null) {
- l2 = l2.next;
- }
- }
- if (carry > 0) {
- tail.next = new ListNode(carry);
- }
- return head;
- }
- }
上述方法時(shí)間復(fù)雜度的計(jì)算與鏈表的長(zhǎng)度有關(guān)，比如兩個(gè)鏈表的長(zhǎng)度分別為m和n，則遍歷的次數(shù)為max(m,n)，也就m和n中取最大值，所以時(shí)間復(fù)雜度為O(n)。
由于要對(duì)鏈表的每一位進(jìn)行計(jì)算存儲(chǔ)，并且最后如果有進(jìn)位，還要多加一位，因此最長(zhǎng)鏈表為max(m,n)+1，所以空間復(fù)雜度為O(n);
通過(guò)思路分析，寫(xiě)出上面的代碼還是比較容易的。但這個(gè)題目是否可以考慮用遞歸的形式來(lái)解決呢?我們來(lái)看看方法二。
方法二：遞歸
第一種方法很簡(jiǎn)單，按照正常的思維邏輯來(lái)就可以了。但評(píng)論區(qū)有這樣一句話“不用遞歸沒(méi)有靈魂。盡管多數(shù)時(shí)候，遞歸不見(jiàn)得更有效率。”那么我們就來(lái)看看用遞歸的形式如何實(shí)現(xiàn)。
- class Solution {
- public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
- return add(l1,l2,0);
- }
- public ListNode add(ListNode l1, ListNode l2, int carry){
- if(l1 == null && l2 == null && carry == 0) return null;
- int x = l1==null ? 0 : l1.val;
- int y = l2==null ? 0 : l2.val;
- int sum = x + y + carry;
- ListNode n = new ListNode(sum % 10);
- n.next = add(l1==null ? null : l1.next,
- l2==null ? null : l2.next,
- sum/10);
- return n;
- }
- }
上述代碼的基本迭代邏輯循環(huán)如下：
兩數(shù)相加
通過(guò)上圖我們可以推演一下遞歸調(diào)用的時(shí)間復(fù)雜度。針對(duì)遞歸調(diào)用的時(shí)間復(fù)雜度計(jì)算，本質(zhì)上要看：遞歸的次數(shù)??每次遞歸中的操作次數(shù)。那么，上述方法遞歸了幾次呢?遞歸的次數(shù)也是與兩個(gè)鏈表最長(zhǎng)的那個(gè)的長(zhǎng)度有關(guān)，最后可能會(huì)因?yàn)檫M(jìn)位多算一次，因此遞歸次數(shù)為n或n+1，而內(nèi)部計(jì)算并不隨n的變化而變化，執(zhí)行次數(shù)為常數(shù)。因此整體時(shí)間復(fù)雜度為n*1 = O(n)。
空間復(fù)雜度依舊與結(jié)果鏈表的長(zhǎng)度有關(guān)，因此依舊為O(n)。
小結(jié)
就算法本身而言是比較簡(jiǎn)單的，理清思路，逐漸添加判斷即可獲得解法。重點(diǎn)在于大家是否能夠想到通過(guò)遞歸算法來(lái)進(jìn)行解答。本道題遞歸算法并沒(méi)有讓時(shí)間復(fù)雜度降低，而在某些情況下通過(guò)遞歸算法能將時(shí)間復(fù)雜度從O(n)降低到O(logn)，這將是很大性能提升。比如，求x的n次方，大家可以嘗試一下。
本文名稱：“兩數(shù)相加”，小學(xué)加法運(yùn)算而已，不用遞歸沒(méi)有靈魂！
文章出自：http://www.5511xx.com/article/cohjpcc.html
