108_1 Data Structure and Algorithm

巨資三B-資料結構與演算法
06170244 吳宜璇

這個學期過的迅速且充實，演算法為我原本枯燥乏味的生活帶來一線生機，讓我時刻思考著當週的作業脈絡，撇除一些不愉快的溝通，我認爲這是一堂受益良多的課程，很開心能遇見這位老師，不能說我的筆記做得多完整多完美，至少我覺得很有成就感，「哇！」感嘆我一學期的成果，原來我也可以做到。-Yuni

• Content
  • Homework
  • Practicing
  • Class Lesson
• Notes
  • Linked List
  • Stack & Queue
  • Set Mismatch
  • Insertion Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort
  • Binary Tree
  • Red Black Tree
  • Hash
  • Breadth First Search
  • Depth First Search
  • Minimum Spanning Tree
  • Shortest Path

Content

Homework

• HW1
• HW2
• HW3
• HW4
• HW5
• HW6

Practicing

• Leetcode
• CS50
• CodeSignal

Class Lesson

• Week1

  2019.09.13 Moon Festival
  

• Week2

  • Linked List
  • Lesson2-Linked List
  • Leetcode-Design Linked List

• Week3

  • Stack & Queue
  • Lesson3-MinStack
  • Leetcode-MinStack

• Week4

  • Set Mismatch
  • Lesson4-Set Mismatch
  • Leetcode-Set Mismatch
  • Insertion Sort
  • Lesson5-Insertion Sort
  • Leetcode-Insertion Sort List

• Week5

  2019.10.10 Double Tenth Day
  

• Week6

  • Quick Sort
  • Heap Sort
  • Lesson6-Heap Sort
  • Leetcode-Univalued Binary Tree
  • Leetcode-Sort an Array
  • HW1-Quick Sort

• Week7

  • Merge Sort
  • HW2-Heap Sort & Merge Sort

• Week8

  • Binary Tree

• Week9

  • HW3-Binary Search Tree

• Week10

  • Red Black Tree

• Week11

  • Hash
  • Lesson8-Hash Set
  • Leetcode-Design HashSet
  • HW4-Hash Table

• Week12

  • Breadth-First Search

• Week13

  • Depth-First Search
  • HW5-BFS & DFS

• Week14

  • Searching a maze using DFS and BFS in Python 3
  • Minimum Spanning Tree

• Week15

  • Shortest Path
  • HW6-Dijkstra & Kruskal

• Week16

  • Overview

• Week17

  • Final Test

• Week18

  Waiting  2020.01.11 
  

Notes

Linked List

• Learning

  • Intro

    • Linked-list是由一連串的節點Node所構成，每個節點指向下一個節點，而最後一個節點則指向None，因此，每個節點本身應該要有兩種屬性（attribute），一個是本身帶有的值或者是資料，另一個則是指向下一個節點的指標->（pointer）。

  • Linked List & Array

    • Linked List屬於鏈式儲存結構，可以快速插入、刪除和移動，因此不會浪費太多記憶體的空間；Array是順序儲存結構，優點：無需為表中元素之間的邏輯關係而增加額外的儲存空間；可以快速的存取表中任一位置的元素缺點：插入和刪除操作需要移動大量元素；當線性表長度變化較大時，難以確定儲存空間的容量。
    • Linked List 每一個節點都是個體，Array牽一髮動全身。

• Reading

  • 用python實作linked-list
  • Linked List - 鏈表
  • Python 数据结构入门 - 链表（Linked List）

• Additional

  • 時間複雜度：衡量演算法執行好壞的工具，不是以秒來計算，而是以步驟次數來計算。
    • 👉Link

Stack and Queue

• Learning

  • Intro

    • Stack : Last-in-First-out
      • pop(-1)
    • Queue : First-in-First-out
      • pop(0)
    • 可以應用在BFS&DFS上，下面會介紹這兩個演算法
    • Stack是具有「Last-In-First-Out」的資料結構(可以想像成一種裝資料的容器)，「最晚進入Stack」的資料會「最先被取出」，「最早進入Stack」的資料則「最晚被取出」。
    • 找到Stack中的最小值。
    • Push(data)：把資料放進Stack。 Pop：把「最上面」的資料從Stack中移除。 Top：回傳「最上面」的資料，不影響資料結構本身。 IsEmpty：確認Stack裡是否有資料，不影響資料結構本身。 getSize：回傳Stack裡的資料個數，不影響資料結構本身。

  

  • Reading

    • Stacks and Queues
    • Stack: Intro(簡介)
    • Stack: 能夠在O(1)取得最小值的MinStack

Set Mismatch

• Learning

  • Intro

    • 找出重複值和缺失值
    • 設一個Count的數組，Count的下標對應nums的值，Count的元素代表nums中元素出現的次數。

Insertion Sort

• Learning

  • Intro

    • 插入排序法
    • 一個個以插入的方式將Node排序
    • 下面是每個sort的時間複雜度

  • Reading

    • Comparison Sort: Insertion Sort(插入排序法)

Quick Sort

• Learning

  • Intro

    • 快速排序法
    • 先用Partition以基準點分出左邊和右邊
    • 再以呼叫quicksort的方式，以二分法方式將兩邊排列，最後就會由小到大排列array裡的元素

  • Reading

    • Comparison Sort: Quick Sort(快速排序法)

Merge Sort

• Learning

  • Intro

    • 合併排序法
    • 先將array裡的元素拆開(devide)成為各一個
    • 再以mergesort的function呼叫，將每個元素合併
    • 設一個空的array[]，將左邊和右邊互相比大小，由小到大排列

  • Reading

    • Comparison Sort: Merge Sort(合併排序法)

Heap Sort

• Learning

  • Intro

    • 堆積排序法
    • 先用heapify將最大值往最頂點放
    • 再呼叫heapsort函式，將最頂點的值和array中的最後一個值交換，然後把這個交換到最後一個位置的值取出放在新的array裡
    • 持續呼叫heapify再繼續上一步

  • Reading

    • Comparison Sort: Heap Sort(堆積排序法)

Binary Tree

• Learning

  • Intro

    • 限制node只能有兩個child，等價於「樹上的每一個node之degree皆為2」，此即稱為Binary Tree(二元樹)，並稱兩個child pointer為left child和right child。
    • root(i=0)/parent(i//2)/left child(2i+1)/right child(2i+2)
    • 若一棵樹的node按照Full Binary Tree的次序排列(由上至下，由左至右)，則稱此樹為Complete Binary Tree。

  • Reading

    • Binary Tree: Intro(簡介)

Red Black Tree

• Learning

  • Intro

    • 在BST中的操作，不論是Insert(新增資料)或是Delete(刪除資料)，皆需要先做Search(搜尋)，而Search(搜尋)的效率，取決於BST的height(樹高)

    • RBT的node比BST多加了「顏色」(紅色或黑色)

    • RBT可以被視為如同Complete Binary Tree的BST，所有與Search(搜尋)有關的操作(Leftmost、Successor、Insert、Delete等等)，都能夠在O(logN)內完成

    • 藉由控制顏色，能夠保證在RBT中，最長path(路徑)不會超過最短path的兩倍(若最短的path是5，最長的path至多只能是10)，如此，RBT便能夠近似地視為平衡

    • RBT的五項特徵：

      1. RBT中的每一個node不是黑色就是紅色。
      2. root一定是黑色。
      3. 每一個leaf node(也就是NULL)一定是黑色。
      4. 如果某個node是紅色，那麼其兩個child必定是黑色，不能有兩個紅色node相連，如圖中的node(17)、node(30)。
      5. 若某個node為黑色，其child之顏色沒有限制，如圖中的node(38)、node(26)、node(21)。
      6. 站在任何一個node上，所有從該node走到其任意descendant leaf的path上之黑色node數必定相同。

  • Reading

    • Red Black Tree: Intro(簡介)

Hash

• Learning

  • Intro

    • Hash 是一種加密函數，將字元轉換成散列值

  • Reading

    • HashTable 的 Python 实现

Breadth First Search

• Learning

  • Intro

    • 廣度優先搜尋
    • 各個node相對於root有其對應的level，按照level由小到大依序對node進行Visiting

  • Reading

    • Graph: Breadth-First Search(BFS，廣度優先搜尋)

Depth First Search

• Learning

  • Intro

    • 深度優先搜尋
    • 先遇到的node就先Visiting

  • Reading

    • Graph: Depth-First Search(DFS，深度優先搜尋)

Minimum Spanning Tree

• Learning

  • Intro

    • MST，最小生成樹
    • 因為是樹，所以沒有cycle
    • 因為是樹，若Graph有V個vertex，Spanning Tree只有|V|−1條edge
    • Graph具有weight，因此，不同的Spanning Tree，可能有不同的weight總和，而其中，具有最小weight總和的樹，稱為Minimum Spanning Tree(MST)

  • Reading

    • Minimum Spanning Tree：Intro(簡介)

Shortest Path

• Learning

  • Intro

    • 以單一vertex為起點，抵達Graph中的其餘所有vertex之最短路徑
    • 起點vertex即為root
    • 從root到其餘vertex的path必定是唯一的最短路徑。

    

  • Reading

    • Shortest Path：Intro(簡介)

---

2019 Data Structure and Algorithm by Yuni