30Day LeetCoding Callenge — Week2

前端野人
·
·
IPFS
·

這禮拜多了幾題Linked List,Linked List 在js是用nested object 取代的,

如果要做Linked List 的運算則還要考慮到遞迴的用法。

這禮拜的重點技巧:

  1. Linked List (鏈結串列)
  2. Recursion (遞迴)

LinkedList

LinkedListjavascript的呈現為:

{
  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!

6! = 720

看起來就是在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
}
CC BY-NC-ND 2.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!