附錄三Day1Day2：荷蘭國旗Day3：奇偶鏈表Day4：兩個數組的交集IDay12Day13：刪除鏈表中的結點Day14：相交鏈表Day15：反轉字符串Day16：三角IDay17：三角IIDay20：Nim游戲Day21：二叉樹的前序遍歷Day22：二叉樹的中序遍歷Day23：二叉樹的后序遍歷Day24：二叉樹的層次遍歷IDay25：二叉樹的層次遍歷IIDay26：二叉樹的所有路徑Day27：二叉樹的最近公共祖先Day28：翻Day30Day31：二叉樹的最小深度Day32：二叉樹的深度Day33：二二叉樹展開為鏈表Day35：Day1：解決方法：2*searchmidDay2：012輸入輸出輸入輸出0、120、1、2的排序，重寫當前解決方法（一1.nums[i]0redwhiteblueblue解決方法（二部分，每一個元素（紅白藍分別對應0、1、2）必屬于其中之一。然后設置一個遍歷指針i，從頭開始進行遍歷。后i向前移動一個位置。所以此時i不前進。而同1），high向前移動一個位置。Day3：給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。請嘗試使用原地算法完成。你的算法的空間復雜度應為O(1)，時間復雜度應為O(nodes)，nodes為節點總數。輸入:輸入:1->2->3->4->5-輸出:1->3->5->2->4要求：請嘗試使用原地算法完成。你的算法的空間復雜度應為1)，時間復雜度應為nes，noe為節點總數。題干限制。將綠色的nextfrontback不斷向后移動并修改。特殊情況處理，當鏈表只有12定義一個back_head最后用front->next=back_head給定num1=[1,22,1],nums2=[22]個for循環即可解決問題，假設兩個數組的大小都為n，那么時間復雜度為O（n2）。集數字的出現次數必定會增加，做好標記，返回交集。時間復雜度為O（n）。集。時間復雜度也就是哈希所有元素的復雜度O(n)。給定nums1=[1,2,2,1],nums2=[2,2],返回[2如果給定的數組已經排好序呢？你將如何優化你的算法？如 nums1的大小 nums2小很多，哪種方法更優如果nums2的元素在磁盤上，內存是有限的，你不能一次加載所有的元素到內存中，你該怎么辦？（一）如果給定的數組已經排好序呢？你將如何優化你的算法？優化算法：即昨日的算法二去掉前面的排序部分。（二）如 nums1的大小 nums2小很多，哪種方法更優這里只提供我本人的一些想法：我們假設，nums1只有4個元素，而nums2有10000個元素。二者都是排好序的情況下，如何在最短時間內找到交集呢？不妨用二分法nums1的各個元素在nums2數組中進行查找和匹配，匹配成功則輸出交集，失敗則為空集。這樣時間復雜度為O（N1*lgN2）其中N1<<N2。當然，你也可能會考慮Hash表的方法，但是處理nums2的Hash表是一個麻煩，因為他自身可能就會出現很多碰撞或稱（collision）。（三）如果nums2的元素在磁盤上，內存是有限的，你不能一次加載所有的元素到內存中，你該怎么辦？方法一：把nums1做成利用隊列在排好序的情況下，然后將數組加入到隊列中，拿元素個數較小的做為循環條件，比較兩個隊列pk數值。相等則輸出并出隊列，否則將較小值所在的隊列進行出隊列操作并及時釋放內存至到某個隊列為空結束循環。方法三：如果nums1，num2（以下摘自w外排序的一個例子是外歸并排序（Externalmergesort），它讀入一些能放在內存內的數據后再進行歸并。[1][2]900MB100MB的可用100MB（如快速排序、堆排序、歸并排序12100MB（臨時文件）900MB100MB9讀入每個臨時文件（順串）10MB（100MB(91)）的數據放入內10MB（實踐中，將輸入緩沖適當調sorting。它可以產生大于內存大小的順串。具體方法是在內存中使用一個最小堆進行排序，設該最小堆的大小為。算法描述如下：20此方法能生成平均長度為的順串，可以進一步減少外部器的次數，節約給定一個鏈表給定一個鏈表1->2->3->4->5n解決方法：較，返回值應賦給l2->next。示例輸入輸入輸出示例輸入輸入輸出Day10：不要使用額外的數組空間，你必須在原地修改輸入數組O(1)額外空間的條件下示例nums[3,2,2,3]val2nums2。示例nums[0,1,2,2,3,0,4,2]val5nums01304。說明////nums是以 ,for(inti=0;i<len;{}如果不相等則前移count短路問題：（一）if（條件1&&條件當執行到if時，首先判定條件1的真假，真，則執行條件2，否則跳出if不再執行。也就是說當條件1為假時，后面的條件不會再執行。（二）if（條件 ||條件當執行到if時，首先判定條件1的真假，假，則執行條件2，否則跳出if不再執行。也就是說當條件1為真時，后面的條件不會再執行。推廣：在今后的工程中，應該將容易判斷的放面Day11：push(x)--xpop()--top()--empty注意你只能使用隊列的基本操作--pushtobackpeek/popfromfrontlistdeque（雙端隊列）來模擬一個隊列,只要是標準的隊列操作即可。你可以假設所有操作都是有效的（例如,poptop操queue1（forilength1queue2的元素在壓入queue1里面Day12：輸入為非空字符串且只包含數字1和0。 a"11b輸出:示例輸入:輸入:a="1010",b="輸出:問題：不如用位數少的先和位數多（與位數少的相同的位數的部分）（有點繞蛤）的相加，然后將比位數多的多的部分看做0，再進行處理。舉個例子吧：1111101Day13：Day14：a1→a1→↘c1→c2→↗b1→b2→c1O(n)O(1)Day15：輸入：輸入：s= Day16：三角示例輸入輸入輸出[]n行的mC(n-1，m-1)n-1個不同元素中取m-1個元素的1行的第i個數等于第n行的第i-1個數和第i個數之和，這也是組合數的性質之一。即C(n+1,i)=C(n,i)+C(n,i-1)。2n+112n+232n+35個數……連成一42n-26個數……這些數之和是第4n-2個斐波那契數。11的n-1（n為行數）次方：1=11^011=11^12……當n>5時會不符合這一條性質，此時應把第n行的最右面的數字"1"放在個 的數為：1,10,45,120,210,252,210,120,45,10,1，結果為25937424601=1110。————百Day17：三角示例輸入輸入輸出解法二：還記得昨天寫 三角的性質嗎a例如，第4行：1464系數分別 在程序中我們用這個遞 來實現對組合數的求icost[i](索引01的元素作示例輸入輸入cost[1015輸出:示例輸入輸入cost[11001,1110011100輸出自下而上的動態規劃，讓dp[i]是到達第i層的最低成本比如：dp[0]=cost[0],dp[1]=cost[1]DP：dp[i]=cost[i]+min(dp[i-i],dp[i-2])細節：最頂層的樓梯n可以從第1階或者第2階樓梯到達Day19： 示例輸入輸入輸出示例輸入輸入輸出Day20：Nim石頭。拿掉最后一塊石頭的人就是獲勝者。你作為先手。示例輸入輸入輸出解釋:如果堆中有4塊石頭，那么 先上結論：第一個拿到4證明如下：如果n=4，根據題意，無論第一個玩家拿走多少個，最后一個石頭總會被第二個玩如果1*4<n<2*4,(n=5,6,7)4個，這樣的話第二個玩家一定會拿到數字4，即5,6,7都是取勝的數字在下一個回合，如果n=8，無論第一個玩家拿走多少，第二個玩家總是可以拿到取勝的數字（5,6,7）。所以，8%4=0，同樣是一個數字。在第2中情形下，同理可得：介于2*4=8<n<3*4之間的數字n，它們是9,10,11，第一個玩家可以拿走一定的石頭使剩下的石頭減少到數字8，所以還是第一個玩Day21：輸出規則：（1）根節點（2）前序遍歷左（3）前序遍歷右分為非遞歸和遞歸兩種方式：Day22：輸出規則：（1）中序遍歷左（2）根節點（3）中序遍歷右分為非遞歸和遞歸兩種方式：Day23：輸出規則：（1）后序遍歷左（2）后序遍歷右（3）根節點分為非遞歸和遞歸兩種方式：給定一個二叉樹，返回其按層次遍歷的節點值（即逐層地，從左到右所有節點例如給定二叉樹3/9/ []首先，將二叉樹的祖先結點入隊列然后，循環執行以下步驟，直到隊列為空。一：結點出隊列進行相應操作。二：該結點如果有左孩子結點，左孩子結點入隊列。三：該結點如果有右孩子結點，右孩子結點入隊列。33/9/ 法一：按照正常的層次I遍歷，最后通過reverse（）法二：DFS的應用Day26：:示例輸入輸入1 \5,百科中最近公共祖先的定義為：“對于有根樹T的兩個結點p、q，最近公共祖先表xxp、qx的深度盡可能大（一個節點也可以是它自例如，給定如下二叉樹:root /\/\/\608/ 示例輸入輸入root3,5,1,6,2,0,8,null,null,7,4p5q輸出解釋513示例輸入輸入root3,5,1,6,2,0,8,null,null,7,4p5q輸出解釋545。因為根據定義最近公共祖先節點可以為說明44 27/ / 3 44 72/ / 6 44 27/ / 3 非遞歸Day30：11/ /\/34411/ 算法關鍵：root1和root2的匹配順序應該是：root1root2進行匹配，若都為空，則相似，返回若任意一個空，另一個非空，返回false若root1root2兩者都非空，則遞歸root1->leftroot2->right進行匹配&&root1->right和root2->left進行匹配。即：根->左->右和根->右->左Day31：:示例33/9/ 返回它的最小深度Day32：:33/9/ Day33：大寬度。這個二叉樹與滿二叉樹（fullbinarytree）結構相同，但一些節點為空。每一層的寬度被定義為兩個端點（該層最左和最右的非空節點，兩端點間的null節點示例輸入輸入1 32/\ 9輸出解釋345,3,null,9)示例輸入輸入1/ 輸出解釋32(5,3)示例輸入輸入1/ 輸出解釋22(3,2)示例輸入輸入1/ /\59/\67輸出解決方法：如果節點的索引是i，它的的指數是2*i和2*i+1。其想法是使用兩個數組(start[]end[])分別記錄每個級別中最左邊和最右邊節點的索引。對于end[levelstart[level1。然后，我們只需要找pair<int,string>果創建pair的時候沒有對其進行初始化，則調用默認構造函數對其初始化。可以時候typedef簡化：普通的點操作符即可其成員pair<string,string>a("Lily",stringname=inta=stringm=pair<int,string>newone;newone=make_pair(a,Day34：11/ / 11\2\3\4\5\64444\5\6111//\\ 2 2/ \\\ 363\\\\Day35：相加作為節點合并后的新值，否則不為NULL的節點將直接作為新二叉樹的節點。示例輸入輸入TreeTree12// / 5 輸出3/ / 示例11/ / 3,[4,2,