30Day LeetCoding Callenge — Week3

前端野人
·
·
IPFS
·
Photo by Guido Hofmann on Unsplash

這週的難度有點高了,主要是在考資料結構的問題,這週我歸納出兩個技巧

  1. Dynamic Programming (動態規劃)
  2. 二元搜尋樹

Dynamic Programming

動態規劃的用法,就像是在走訪陣列時就在元素中累計運算,這個很難意會,所以我拿範例來舉例。

使用dp運算階乘

30Day LeetCoding Callenge — Week2 ,有用過recursion 做過階乘,但recursion 只能得到結果,而dynamic programming 則是列出1~6階的階乘,這特性的應用在本週有很大的應用,我們拿 1.Product of Array Except Self 做舉例。

題目說可以用O(n)的方式解決,題目的思維在於如何將該元素以外的元素相乘,即可以得出結果。而解題分析可得到如何將元素以外的元素相成,其實就是做出元素左邊跟元素右邊的所有值相乘。

用程式碼來看就是,分別將該元素的左邊跟右邊所有元素乘裡來,只要在兩邊在相乗就可以得到答案,而陣列中可以發現每個值剛好都是左邊或右邊乘起來的積,所以蒐集到特定索引值時,就是該元素得左邊/右邊的乘積。

let L = [1] //因為最右跟最左沒東西所以為1
for(let i = 0 ; i < nums.length-1; i++){
    L[i+1] = (L[i+1-1] * nums[i])
}
let numsR = nums.reverse()
let R = [1] // R為了方便運算所以還需要反轉
for(let i = nums.length ; i  nums.length-1 ; i++){
    R[i+1] = R[i+1-1] * numsR[i]
}
R = R.reverse()

再來有一題也是很精彩的Dynamic Programming 的應用:

3.Minimum Path Sum

這題解法厲害的點在於,使用Dynamic Programming 將第一列跟第一行累加起來變成:

[1,4,5]
[2,5,1]
[6,2,1]

這時候路徑和第一行跟第一列已經有部分處理好了。剩下有可能會走過任一個第一行或第一列的中間的值運算,舉例來說,grid[1][1] 運算時就是加相鄰的最小路徑和也就是grid[0][1] grid[1][0],而這兩個元素又代表的走到這個元素的路徑和,所以繼續累加的話就可以得到終點grid[i][j]的最小路徑和,我認為這題是Week3裡面Dynamic Programming的經典應用。

  for(let i = 1 ; i < row ; i++){
      for(let j = 1 ; j < col ; j++){
          grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1])
      }
  } 

二元搜尋樹

其實這週二元搜尋樹的應用只有一題,但這是經典的資料結構運算,所以還是要了解二元搜尋樹的醍醐味,下面是一顆二元搜尋樹:

Binary Search Tree - geeksforgeeks.org

二元搜尋樹的特點:

  1. 每個節點的左節點會小於節點
  2. 每個節點的右節點會大於節點

二元搜尋樹的遍歷,也就是走訪的順序:

  1. Preorder Traversal 前序遍歷,中 -> 左 -> 右
  2. Inorder Traversal 中序遍歷,左 -> 中 -> 右
  3. Postorder Traversal 後序遍歷 左-> 右 ->中
http://www.csie.ntnu.edu.tw/~u91029/BinaryTree.html

上面簡單介紹,二元搜尋樹的定義及遍歷方式。

題目中我們常看到的二元搜尋樹的陣列二元堆積,先了解在js中怎麼處理二元堆積通常leetcode會將需要用的function提供出來,以下是二元樹的Tree Node,其實跟LinkedList的List Node 很像。

 function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
 }

這週題目剛好就是將陣列轉成二元堆積,所以我們直接看 6.Construct Binary Search Tree from Preorder Traversal ,這題就是將陣列轉成二元搜尋數的前序遍歷的二元堆積。

首先我們先想一下從二元搜尋數的最上層節點開始做,如果要放進Tree Node 的話就要想第一個節點及他的左跟右節點是什麼。

8開始所以第一個比8小的就是55就是8的左子樹,第一個比8大的是10所以108的右子樹,所以程式碼就有一個判斷可以參考了:

slice是切掉第一個元素後過濾出後面小於preorder[0]的陣列。
left =  preorder.slice(1).filter(ele => ele < preorder[0])
right = preorder.slice(1).filter(ele => ele > preorder[0])

所以第一個根節點8後就可以切出小於8的左子樹陣列跟大於8的右子樹陣列,之後就是再用遞迴重新指向新的根節點,然後再切出左子樹陣列跟右子樹陣列,直到null。

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}
var bstFromPreorder = function(preorder) {
    if(preorder.length === 0) return null
    if(preorder.length === 1) return new TreeNode(preorder[0])
    let root =  new TreeNode(preorder[0])
    let left  = bstFromPreorder(preorder.slice(1).filter(ele => ele < preorder[0]))
    let right = bstFromPreorder(preorder.slice(1).filter(ele => ele > preorder[0]))
    if(root) root.left = left
    if(root) root.right = right
    return root
};

詳細題解在:https://ithelp.ithome.com.tw/articles/10231122

CC BY-NC-ND 2.0 授权

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