---
title: '核心技巧 - 基礎'
disqus: kyleAlien
---

核心技巧 - 基礎
===

## OverView of Content

大部分考得演算法都是 Tree 的尋訪問題

[TOC]

## 演算法 - 概念框架

演算法的解題是有 `概念框架`（也就是技巧），去除細節我們主要關注 **++問題的本質++**

### 資料結構 - 基礎

* **資料結構的底層其實只分為 2 兩種**，不管是 Stack、Queue、Heap、Tree、Hashmap、Graph... 等等數據結

1. Array：陣列，記憶體的連續結構

| 優點 | 缺點 |
| -------- | -------- |
| 訪問速度快（隨機存取） | 擴容、縮容耗費時間 |

> 

:::info
* BIG O
Arrry 的主要缺點是在擴容：擴容時（可能發生在插入、刪除操作），都需要將資料複製到新 Array，有 N 個資料就會花費 N 個時間 (花費 O(N) 時間)
:::

2. LinkedList：不同記憶體區塊的連接

| 優點 | 缺點 |
| -------- | -------- |
| 插入、移除速度快 | 要花費更多的空間儲存數據，訪問速度較慢 |

花費更多的空間儲存數據：主要是因為每個節點都需要儲存下一個節點的訪問數據（不管是指針還是物件）
> 

:::success
Array & LinkedList 兩者個優缺點是相反的
:::

### Stack、Queue

* Stack、Queue 兩種數據結構都可以用 Array、LinkedList 來實現，其特性就是 Array、LinkedList 兩種特性

1. **Stack** `先進先後` (FILO)：像是一個罐子的結構，只有一個出入口
> 

2. **Queue** `先進先出` (FIFO)：有兩個出入口，一個負責進入、另一個負責輸出
> 

### HaspMap

* HashMap 是一種 Key & Value 對應的結構，由 Array、LinkedList 兩個數據結構 **共同** 實現
1. **Key**：每個儲存的數據都有一個對應的 Key，而 **這個 Key 用 Array 儲存**

2. **Value**：**一個 Key 可以對應到多個 Value**，當一個 Key 已經有 Value 的時候就會產生 **雜湊衝突**，而解決滑動衝突的方式有兩種

| 雜湊衝突 | 結構 |
| -------- | -------- |
| 拉鍊法 | LinkedList |
| 線性法 | Array |

### Tree

* Tree 同樣也可以用 Array、LinkedList 來實現

| 結構 | Tree 實現 | 特性 |
| -------- | -------- | - |
| Array | Heap (**完全二元樹**) | 不需要結構指標，較為簡單 |
| LinkedList | 各種樹的實現 | 二元樹、AVL、紅黑樹 |

> 

## 基礎操作

基礎操作 - 圓圈圖
> 

* 資料結構 - 操作：無非是在不同的情況下盡可能有效的，對資料進行 **增、刪、改、查** 的操作行為

* 資料結構 - 訪問 or 存取：只有分為 **線性**、**非線性**

| 線性（**依照順序**） | 非線性（**不照順序**） |
| -------- | -------- |
| for/while 迭代 | LinkedList、二元樹遞迴 |

> 

1. 陣列 Array 尋訪

        // for 迭代

            public void forTraverse(int[] array) {
                for(int item : array) {
                    System.out.println("Item: " + item);
                }
            }
        
        // ------------------------------------------------------------------
        // while 迭代

            public void whileTraverse(int[] array) {
                int index = 0;
                // close
                while (index++ < array.length) {
                    System.out.println("Item: " + array[index]);
                }
            }

2. LinkedList 可以兼具 **迭代** ＆ **遞迴** 兩種結構

        // LinkedList 迭代

            public void traverse(Node node) {
                Node tmp = node;

                while (tmp != null) {
                    System.out.println("Value: " + tmp.value);
                    tmp = tmp.next;            // 按照順序
                }
            }

        // ------------------------------------------------------------------
        // 遞迴

            public void recursive(Node node) {
                if(node == null) {
                    return;
                }
                // forward value
                recursive(node.next);        // 不按照順序
                // behind value
            }

:::success
**鏈結串列也有分為 ==前序==、==後序== 訪問**
:::

        public static final class TreeNode {
            TreeNode left, right;
            int value;
        }

        public void treeRecursive(TreeNode treeNode) {
            // forward
            treeRecursive(treeNode.left);
            // middle
            treeRecursive(treeNode.right);
            // behind
        }

### Array & LinkedList 常用數據結夠

* 上面有說過最基礎的數據結構其實就兩個 Array、LinkedList，我們這邊用 **多氣泡圖** 來表達 (當然不代表一定要用這些數據結構)

> 

### 框架概念

* 框架概念 就是 **解題概念、技巧、範本**，但不論是增刪改查這些行為都不會脫離框架結構

> 

:::info
試著從框架看問題，先不要糾結於細節 (這不代表細節不重要，細節也是很重要的)
:::

### 資料結構 & 演算法

* 資料結構：**工具**

* 演算法：透過適合的工具（資料結構），解決 **特定** 問題的方法

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`