30Day LeetCoding Callenge — Week2
這禮拜多了幾題Linked List,Linked List 在js是用nested object 取代的,
如果要做Linked List 的運算則還要考慮到遞迴的用法。
這禮拜的重點技巧:
- Linked List (鏈結串列)
- Recursion (遞迴)
LinkedList
LinkedList在javascript的呈現為:
{ val:0, next:{ val:1, next:null } }
如果JS要做鏈結串列的話就必須自己建立function製造
要先有Node節點,每個節點會要的資料,如果有需要可以多塞value進去
class Node{ constructor(data, next = null){ this.data = data, this.next = next } }
建立LinkedList 的開頭
class LinkedList{ constructor(){ this.head = null; } }
在設計塞入節點的function,執行後會發現最後一個是陣列最開始的值,這是正常的,因為程式是把現有的 this.head 塞進 nweNode.next 合併在蓋回原本的this.head。
詳細可再參考:Linked Lists in JavaScript (ES6 code)
LinkedList.prototype.insertAtBeginning = function(data){ let newNode = new Node(data); newNode.next = this.head; this.head = newNode; return this.head; }
題目
1. Middle of the Linked List
說明:找出Linked List 的中間節點,抓出中間節點以後的Linked List
思維:找出Linked List 中間的節點然後回傳節點往後的LinkedList。這題目是應用如何從LinkedList 取得資料,這邊就會先暫存當下的節點,然後取的資料後再把next的資料蓋到暫存得值,直到拿到符合的答案。
var middleNode = function(head) { let listLength = 1 let a = 0 let test = head while(test.next){ test = test.next listLength += 1 } let mid = Math.floor(listLength / 2) + 1 let answer = head while(mid > 0 && head){ answer = head head = head.next mid-- } return answer };
Recusion
recusion 是一個不好懂的演算法,但也是一個常見的基本技巧,我們先用階乘(factorail) 6! Demo!
看起來就是在function內重複呼叫自己,但要注意需要下判斷是終止回調(callback)
所以在 num - 1 = 1 的時候就回傳 1 這樣最會在 2 * 1 的時候結束。
題目
以下有幾題是有相關應用的題目,詳細解題思路可以參考
4.Diameter of Binary Tree
說明:算出二元樹的兩端節點最遠距離
Example:
Given a binary tree 1 / \ 2 3 / \ 4 5 ans :3
思維:這題依照資料結構的答案思路,就是計算左邊的最深度及右邊的最深度,所以會用Recusion 跑到node == null 也就是節點的終點結束,因為不知道多長不能假設迴圈的index所以用Recusion是最適合的。
Answer:
let max var diameterOfBinaryTree = function(root) { max = 1 dfs(root) return max -1 }; const dfs = node =>{ if(node === null) return 0 let left = dfs(node.left) let right = dfs(node.right) max = Math.max(max,left + right + 1) return Math.max(left,right) + 1 }
喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!
- 来自作者
- 相关推荐