Java-全網最詳細資料結構
2023-10-10 12:02:58
數構&演演算法：資料結構
- 資料結構是計算機儲存、組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下，精心選擇的資料結構可以帶來更高的執行或者儲存效率。資料結構往往同高效的檢索演演算法和索引技術有關，以下是各種資料結構的詳細說明。
線性結構：陣列、佇列、連結串列、棧
順序儲存（地址連續）
鏈式儲存（地址不一定連續）
非線性結構：二維陣列、多維陣列、廣義表、樹、圖
①陣列
❶稀疏陣列
- 稀疏陣列是一種用來壓縮資料量的資料結構，簡而言之，就是記錄特殊值，然後剩下大量重複的資料可以消減。
例如下方是一個普通二維陣列
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 2 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
這麼一個二維陣列，化成稀疏陣列可以表示為：
行 列 值
0 6 6 2
1 1 2 1
2 2 3 2
1. 稀疏陣列第一行表示原陣列有多少行，多少列，有多少個非零元素（有效值）
2. 稀疏陣列是從0開始的
3. 稀疏陣列的行數等於有效值+1，列數固定都為3
二維陣列轉稀疏陣列的步驟：
- 遍歷二維陣列，得到有效值個數 sum
- 根據 sum 建立稀疏陣列 sparseArr = int [sum+1][3]
- 將有效值存入稀疏陣列
還原稀疏陣列步驟：
- 建立一個新的陣列，其行和列等於稀疏陣列首行資料
- 遍歷稀疏陣列，將對應數值賦值給新的陣列
- 最後可以驗證一下原始的陣列和還原後的陣列是否相等
//稀疏陣列：用來減少資料量
public class SparseArray {
public static void main(String[] args) {
// 一、構建原始陣列
// 建立一個二維陣列6*6 0：沒有棋子，1：黑棋 2：白棋
int[][] chessArr = new int[6][6];
chessArr[1][2] = 1;
chessArr[2][3] = 2;
System.out.println("原始陣列:");
for (int[] row : chessArr) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
System.out.println("====================");
// 二、轉換成稀疏陣列
int sum = 0;
//1.先遍歷二維陣列，獲取有效值的個數
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[0].length; j++) {
if(chessArr[i][j] != 0) {
sum++;//有效值的個數
}
}
}
//2.建立對應稀疏陣列
int [][]sparseArr = new int[sum+1][3];
//第一行賦值
sparseArr[0][0] = chessArr.length;
sparseArr[0][1] = chessArr[0].length;
sparseArr[0][2] = sum;
//3.遍歷初始的二維陣列，將非零的值，存放到稀疏陣列中
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
for (int j = 0; j < chessArr[0].length; j++) {
if (chessArr[i][j] != 0){
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
}
}
}
//4.輸出稀疏陣列
System.out.println("稀疏陣列:");
for (int i = 0; i < sparseArr.length; i++) {
System.out.println(sparseArr[i][0]+"\t"+sparseArr[i][1]+"\t"+sparseArr[i][2]+"\t");
}
// 三、還原陣列
int [][] ChessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
ChessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
System.out.println("=======================");
//列印還原的陣列
System.out.println("輸出還原後的陣列：");
for (int[] row : ChessArr2) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
//四、驗證兩個陣列是否相等，可用Arrays工具類
int flag = 0;
for (int i = 0; i < chessArr.length; i++) {
if (!Arrays.equals(chessArr[i],ChessArr2[i])){
flag++;
}
}
if (flag==0){
System.out.println("初始陣列和還原後的陣列相等");
}
}
}
❷陣列模擬佇列
佇列本身是有序列表，若使用陣列的結構來儲存佇列的資料，則佇列陣列的宣告如下圖
maxSize 是該佇列的最大容量，兩個變數 front 及 rear 分別記錄佇列前後端的下標
class ArrayQueue {
private int MaxSize; // 佇列大小
private int front; // 佇列頭
private int rear; // 佇列尾
private int[] arr; // 陣列存放資料
// 一、建立佇列的構造器
public ArrayQueue(int MaxSize) {
this.MaxSize = MaxSize;
arr = new int[this.MaxSize];
front = -1;
rear = -1;
}
//二、判斷佇列是否滿
public boolean isFull() {
return rear == MaxSize - 1;
}
//三、判斷佇列是否空
public boolean isEmpty() {
return rear == front;
}
//四、入隊
public void addQueue(int num) {
if (isFull()) {
System.out.println("佇列已滿，無法在進行入隊操作");
return;
}
arr[++rear] = num;
}
//五、出隊
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("佇列為空，無法出隊");
}
return arr[++front];
}
//六、顯示佇列資料
public void showQueue() {
if (isEmpty()) {
throw new RuntimeException("佇列為空，無法遍歷");
}
for (int i = front+1; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
//七、顯示佇列頭資料
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("佇列為空，沒有資料");
}
return arr[front + 1];
}
}
測試
public class ArrayQueueDemo {
public static void main(String[] args) {
// 構造佇列
ArrayQueue queue = new ArrayQueue(5);
// 入隊
queue.addQueue(1);
queue.addQueue(2);
queue.addQueue(3);
queue.addQueue(4);
queue.addQueue(5);
// 出隊
System.out.println(queue.getQueue());
// 遍歷佇列
queue.showQueue();
// 隊首
System.out.println(queue.headQueue());
}
}
②連結串列
❶單向連結串列
特點
- 連結串列是以節點的方式來儲存，是鏈式儲存
- 每個節點包含 data 域 （儲存資料），next 域（指向下一個節點）
- 連結串列的各個節點不一定是連續儲存的
- 連結串列分帶頭節點的連結串列和沒有頭節點的連結串列，根據實際的需求來確定
/**
* 定義節點
*/
class StudentNode {
int id;
String name;
StudentNode next;
public StudentNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
/**
* 建立連結串列
*/
class singleLinkedList {
//頭節點，防止被修改，設定為私有的
private StudentNode head = new StudentNode(0, "");
//插入節點
public void addNode(StudentNode node) {
//因為頭節點不能被修改，所以建立一個輔助節點
StudentNode temp = head;
//找到最後一個節點
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
//按id順序插入節點
public void addByOrder(StudentNode node) {
//如果沒有首節點，就直接插入
if (head.next == null) {
head.next = node;
return;
}
//輔助節點，用於找到插入位置和插入操作
StudentNode temp = head;
//節點的下一個節點存在，且它的id小於要插入節點的id，就繼續下移
while (temp.next != null && temp.next.id < node.id) {
temp = temp.next;
}
//如果temp的下一個節點存在，則執行該操作
//且插入操作，順序不能換
if (temp.next != null) {
node.next = temp.next;
}
temp.next = node;
}
//遍歷連結串列
public void traverseNode() {
if (head.next == null) {
System.out.println("連結串列為空");
}
StudentNode temp = head;
while (temp.next != null) {
System.out.println(temp.next);
temp = temp.next;
}
}
//根據id來修改節點資訊
public void changeNode(StudentNode node) {
if (head == null) {
System.out.println("連結串列為空，請先加入該學生資訊");
return;
}
StudentNode temp = head;
//遍歷連結串列，找到要修改的節點
while (temp.next != null && temp.id != node.id) {
temp = temp.next;
}
//如果temp已經是最後一個節點，判斷id是否相等
if (temp.id != node.id) {
System.out.println("未找到該學生的資訊，請先建立該學生的資訊");
return;
}
//修改資訊
temp.name = node.name;
}
//刪除節點
public void deleteNode(StudentNode node) {
if (head.next == null) {
System.out.println("連結串列為空");
return;
}
StudentNode temp = head;
//遍歷連結串列，找到要刪除的節點
while (temp.next != null && temp.next.id != node.id) {
temp = temp.next;
}
if(temp.next == null){
System.out.println("要刪除的節點不存在");
return;
}
//刪除該節點
temp.next = temp.next.next;
}
//得到第index個的節點
public StudentNode getNodeByIndex(int index) {
if (head.next == null) {
System.out.println("連結串列為空!");
}
StudentNode temp = head;
int length = 0;
while (temp.next != null) {
temp = temp.next;
length++;
}
if (index > length) {
throw new RuntimeException("連結串列越界");
}
temp = head;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
//逆序遍歷
public void reverseTraverse() {
if (head == null) {
System.out.println("連結串列為空");
}
StudentNode temp = head;
//建立棧，用於存放遍歷到的節點
Stack<StudentNode> stack = new Stack<>();
while (temp.next != null) {
stack.push(temp.next);
temp = temp.next;
}
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
public class SingleLinkedListDemo {
public static void main(String[] args) {
singleLinkedList linkedList = new singleLinkedList();
//建立學生節點，並插入連結串列
System.out.println("插入節點1和3：");
StudentNode student1 = new StudentNode(1, "Jack");
StudentNode student3 = new StudentNode(3, "Tom");
linkedList.addNode(student1);
linkedList.addNode(student3);
linkedList.traverseNode();
//按id大小插入
System.out.println("有序插入節點2：");
StudentNode student2 = new StudentNode(2, "Jerry");
linkedList.addByOrder(student2);
linkedList.traverseNode();
//按id修改學生資訊
System.out.println("修改節點1資訊：");
student2 = new StudentNode(1, "Jack2");
linkedList.changeNode(student2);
linkedList.traverseNode();
//獲得第2個節點
System.out.println("獲得第2個節點：");
System.out.println(linkedList.getNodeByIndex(2));
//根據id刪除學生資訊
System.out.println("刪除學生資訊：");
student2 = new StudentNode(1, "Jack2");
linkedList.deleteNode(student2);
linkedList.traverseNode();
//倒敘遍歷連結串列
System.out.println("倒序遍歷連結串列：");
linkedList.reverseTraverse();
}
}
連結串列為空
插入節點1和3：
StudentNode{id=1, name='Jack'}
StudentNode{id=3, name='Tom'}
有序插入節點2：
StudentNode{id=1, name='Jack'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
修改節點1資訊：
StudentNode{id=1, name='Jack2'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
獲得第2個節點：
StudentNode{id=2, name='Jerry'}
刪除學生資訊：
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
倒序遍歷連結串列：
StudentNode{id=3, name='Tom'}
StudentNode{id=2, name='Jerry'}
❷雙向連結串列
/**
* 定義節點
*/
class HeroNode {
int id;
String name;
HeroNode next;
HeroNode pre;
public HeroNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "HeroNode{id=" + id + ", name=" + name + "}";
}
}
/**
* 建立一個雙向連結串列的類
*/
class DoubleLinkedList {
//初始化一個頭節點，頭節點不動，不存放具體的資料
HeroNode head = new HeroNode(0, "");
//初始化一個尾節點，指向最後一個元素，預設等於head
HeroNode tail = head;
//遍歷列印雙向連結串列的方法
public void list() {
if (head.next == null) {
System.out.println("連結串列為空");
return;
}
HeroNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
//新增節點
public void add(HeroNode heroNode) {
tail.next = heroNode;
heroNode.pre = tail;
tail = heroNode;
}
//有序新增節點
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
// 標記新增的編號是否已經存在
boolean flag = false;
while (temp.next != null && temp.next.id <= heroNode.id) {
if (temp.next.id == heroNode.id) {
flag = true;
}
temp = temp.next;
}
// 判斷flag
if (flag) {
System.out.printf("英雄編號【%d】已經存在了\n", heroNode.id);
} else {
// 插入到連結串列中
// 1、將【heroNode的next】設定為【temp的next】
heroNode.next = temp.next;
// 判斷是不是加在連結串列最後
if (temp.next != null) {
// 2、將【temp的next的pre】設為為【heroNode】
temp.next.pre = heroNode;
}
// 3、將【temp的next】設定為【heroNode】
temp.next = heroNode;
// 4、將【heroNode的pre】設定為【temp】
heroNode.pre = temp;
}
}
//修改節點
public void update(HeroNode heroNode) {
// 判斷是否為空
if (head.next == null) {
System.out.println("連結串列為空~~");
return;
}
// 找到需要修改的節點
HeroNode temp = head.next;
// 表示是否找到這個節點
boolean flag = false;
while (temp != null) {
if (temp.id == heroNode.id) {
flag = true;
break;
}
temp = temp.next;
}
// 根據flag判斷是否找到要修改的節點
if (flag) {
temp.name = heroNode.name;
} else { // 沒有找到
System.out.printf("沒有找到編號為 %d 的節點，不能修改\n", heroNode.id);
}
}
//刪除節點
public void delete(int id) {
// 判斷當前連結串列是否為空
if (head.next == null) {
System.out.println("連結串列為空，無法刪除");
return;
}
HeroNode temp = head;
// 標誌是否找到刪除節點
boolean flag = false;
while (temp.next != null) {
// 已經找到連結串列的最後
if (temp.id == id) {
// 找到待刪除節點
flag = true;
break;
}
temp = temp.next;
}
// 判斷flag，此時找到要刪除的節點就是temp
if (flag) {
// 可以刪除，將【temp的pre的next域】設定為【temp的next域】
temp.pre.next = temp.next;
// 如果是最後一個節點，就不需要指向下面這句話，否則會出現空指標 temp.next.pre = null.pre
if (temp.next != null) {
temp.next.pre = temp.pre;
}
}
}
}
public class DoubleLinkedListDemo {
public static void main(String[] args) {
System.out.println("雙向連結串列:");
// 建立節點
HeroNode her1 = new HeroNode(1, "宋江");
HeroNode her2 = new HeroNode(2, "盧俊義");
HeroNode her3 = new HeroNode(3, "吳用");
HeroNode her4 = new HeroNode(4, "林沖");
// 建立一個雙向連結串列物件
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(her1);
doubleLinkedList.add(her2);
doubleLinkedList.add(her3);
doubleLinkedList.add(her4);
doubleLinkedList.list();
// 修改
HeroNode newHeroNode = new HeroNode(4, "公孫勝");
doubleLinkedList.update(newHeroNode);
System.out.println("修改節點4:");
doubleLinkedList.list();
// 刪除
doubleLinkedList.delete(3);
System.out.println("刪除節點3");
doubleLinkedList.list();
// 測試有序新增
System.out.println("測試有序增加連結串列：");
DoubleLinkedList doubleLinkedList1 = new DoubleLinkedList();
doubleLinkedList1.addByOrder(her3);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her4);
doubleLinkedList1.addByOrder(her4);
doubleLinkedList1.addByOrder(her2);
doubleLinkedList1.addByOrder(her1);
doubleLinkedList1.list();
}
}
雙向連結串列:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=盧俊義}
HeroNode{id=3, name=吳用}
HeroNode{id=4, name=林沖}
修改節點4:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=盧俊義}
HeroNode{id=3, name=吳用}
HeroNode{id=4, name=公孫勝}
刪除節點3
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=盧俊義}
HeroNode{id=4, name=公孫勝}
測試有序增加連結串列：
英雄編號【2】已經存在了
英雄編號【4】已經存在了
英雄編號【2】已經存在了
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=盧俊義}
HeroNode{id=3, name=吳用}
HeroNode{id=4, name=公孫勝}
❸迴圈連結串列
③棧&佇列&堆
❶普通佇列-Queue
佇列是一種先進先出的資料結構，元素從後端入隊，然後從前端出隊。
Queue<> queue = new LinkedList<>();
常用方法
| 函數 | 功能 |
|---|---|
| add(E e)/offer(E e) | 壓入元素 |
| remove()/poll() | 彈出元素 |
| element()/peek() | 獲取隊頭元素 |
| isEmpty() | 用於檢查此佇列是「空」還是「非空」 |
| size() | 獲取佇列長度 |
❷雙端佇列-Deque
Java集合提供了介面Deque來實現一個雙端佇列，它的功能是：
- 既可以新增到隊尾，也可以新增到隊首；
- 既可以從隊首獲取，又可以從隊尾獲取。
Deque有三種用途
- 普通佇列(一端進另一端出):
Deque<> queue = new LinkedList<>();
// 等價
Queue<> queue = new LinkedList<>();
| Queue方法 | 等效Deque方法 |
|---|---|
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
- 雙端佇列(兩端都可進出)
//底層：ArrayDeque（動態陣列）和 LinkedList（連結串列）
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque = new LinkedList<>();
| 第一個元素 (頭部) | 最後一個元素 (尾部) | |
|---|---|---|
| 插入 | addFirst(e)/offerFirst(e) | addLast(e)/offerLast(e) |
| 刪除 | removeFirst()/pollFirst() | removeLast()/pollLast() |
| 獲取 | getFirst()/peekFirst() | getLast()/peekLast() |
- 堆疊(先進後出)
//底層：ArrayDeque（動態陣列）和 LinkedList（連結串列）
Deque<Integer> stack = new LinkedList<>();
Deque<Integer> stack = new ArrayDeque<>(); //速度更快
// 等價
Stack<String> stack=new Stack<>();
| 堆疊方法 | 等效Deque方法 |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
Deque所有方法
| 方法 | 描述 |
|---|---|
| 新增功能 | |
| push(E) | 向佇列頭部插入一個元素,失敗時丟擲異常 |
| addFirst(E) | 向佇列頭部插入一個元素,失敗時丟擲異常 |
| addLast(E) | 向佇列尾部插入一個元素,失敗時丟擲異常 |
| offerFirst(E) | 向佇列頭部加入一個元素,失敗時返回false |
| offerLast(E) | 向佇列尾部加入一個元素,失敗時返回false |
| 獲取功能 | |
| peek() | 獲取佇列頭部元素,佇列為空時丟擲異常 |
| getFirst() | 獲取佇列頭部元素,佇列為空時丟擲異常 |
| getLast() | 獲取佇列尾部元素,佇列為空時丟擲異常 |
| peekFirst() | 獲取佇列頭部元素,佇列為空時返回null |
| peekLast() | 獲取佇列尾部元素,佇列為空時返回null |
| 刪除功能 | |
| removeFirstOccurrence(Object) | 刪除第一次出現的指定元素,不存在時返回false |
| removeLastOccurrence(Object) | 刪除最後一次出現的指定元素,不存在時返回false |
| 彈出功能 | |
| pop() | 彈出佇列頭部元素,佇列為空時丟擲異常 |
| removeFirst() | 彈出佇列頭部元素,佇列為空時丟擲異常 |
| removeLast() | 彈出佇列尾部元素,佇列為空時丟擲異常 |
| pollFirst() | 彈出佇列頭部元素,佇列為空時返回null |
| pollLast() | 彈出佇列尾部元素,佇列為空時返回null |
❸優先佇列-PriorityQueue
優先順序佇列其實就是一個披著佇列外衣的堆，因為優先佇列對外介面只是從隊頭取元素，從隊尾新增元素，再無其他取元素的方式，看起來就是一個佇列。
PriorityQueue 是具有優先順序別的佇列，優先順序佇列的元素按照它們的自然順序排序，或者由佇列構造時提供的 Comparator 進行排序，這取決於使用的是哪個建構函式
| 建構函式 | 描述 |
|---|---|
| PriorityQueue() | 使用預設的容量（11）建立一個優佇列，元素的順序規則採用的是自然順序 |
| PriorityQueue(int initialCapacity) | 使用預設指定的容量建立一個優佇列，元素的順序規則採用的是自然順序 |
| PriorityQueue(Comparator<? super E> comparator) | 使用預設的容量佇列，元素的順序規則採用的是 comparator |
//預設按自然順序（升序）檢索的
PriorityQueue<Integer> numbers = new PriorityQueue<>();
PriorityQueue<Integer> numbers = new PriorityQueue<>(3); //大小為3
//使用Comparator介面自定義此順序
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
常用方法
peek()//返回隊首元素
poll()//返回隊首元素，隊首元素出佇列
add()//新增元素
size()//返回佇列元素個數
isEmpty()//判斷佇列是否為空，為空返回true,不空返回false
❹棧-Stack/Deque
棧是一種後進先出的資料結構，元素從頂端入棧，然後從頂端出棧。
注意：Java 堆疊 Stack 類已經過時，Java 官方推薦使用 Deque 替代 Stack 使用。Deque 堆疊操作方法：push()、pop()、peek()。
建立棧
//方法一，棄用
Stack<E> stack=new Stack<>();
Stack<String> stack=new Stack<>();
//方法二：推薦使用
//底層：ArrayDeque（動態陣列）和 LinkedList（連結串列）
Deque stack = new ArrayDeque<String>();
Deque stack = new LinkedList<String>();
stack.push("a");
stack.pop();
stack.push("b");
System.out.println(stack);
常用方法
| 函數 | 功能 |
|---|---|
| push(T t) | 壓棧（向棧頂放入元素） |
| pop() | 出棧（拿出棧頂元素，並得到它的值） |
| peek() | 將棧頂元素返回，但是不從棧中移除它 |
| search(Object o) | 返回物件在此堆疊上的從1開始的位置。 |
| isEmpty() | 判斷棧是否為空 |
| size() | 獲取棧長度 |
❺堆-Heap
堆通常可以被看做是一棵完全二元樹的陣列物件。
堆的特性：
- 1.堆是完全二元樹，除了樹的最後一層結點不需要是滿的，其它的每一層從左到右都是滿的，如果最後一層結點不是滿的，那麼要求左滿右不滿。
- 2.堆通常用陣列來實現。將二元樹的結點按照層級順序放入陣列中，根結點在位置1，它的子結點在位置2和3，而子結點的子結點則分別在位置4,5,6和7，以此類推。(0被廢棄)
如果一個結點的位置為k，則它的父結點的位置為[k/2]，而它的兩個子結點的位置則分別為2k和2k+1。
這樣，在不使用指標的情況下，我們也可以通過計算陣列的索引在樹中上下移動：從a[k]向上一層，就令k等於k/2,向下一層就令k等於2k或2k+1。
- 3.每個結點都大於等於它的兩個子結點。這裡要注意堆中僅僅規定了每個結點大於等於它的兩個子結點，但這兩個子結點的順序並沒有做規定，跟我們之前學習的二叉查詢樹是有區別的。
堆的API設計
public class Heap<T extends Comparable<T>> {
//儲存堆中的元素
private T[] items;
//記錄堆中元素的個數
private int N;
public Heap(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.N = 0;
}
//判斷堆中索引i處的元素是否小於索引j處的元素
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
//交換堆中i索引和j索引處的值
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
//往堆中插入一個元素
public void insert(T t) {
items[++N] = t;
swim(N);
}
//使用上浮演演算法，使索引k處的元素能在堆中處於一個正確的位置
private void swim(int k) {
//通過迴圈，不斷的比較當前結點的值和其父結點的值，如果發現父結點的值比當前結點的值小，則交換位置
while (k > 1) {
//比較當前結點和其父結點
if (less(k / 2, k)) {
exch(k / 2, k);
}
k = k / 2;
}
}
//刪除堆中最大的元素,並返回這個最大元素
public T delMax() {
T max = items[1];
//交換索引1處的元素和最大索引處的元素，讓完全二元樹中最右側的元素變為臨時根結點
exch(1, N);
//最大索引處的元素刪除掉
items[N] = null;
//元素個數-1
N--;
//通過下沉調整堆，讓堆重新有序
sink(1);
return max;
}
//使用下沉演演算法，使索引k處的元素能在堆中處於一個正確的位置
private void sink(int k) {
//迴圈對比k結點和其左子結點2k以及右子結點2k+1處中的較大值的元素大小，如果當前結點小，則需要交換位置
while (2 * k <= N) {
//獲取當前結點的子結點中的較大結點
int max;//記錄較大結點所在的索引
if (2 * k + 1 <= N) {
if (less(2 * k, 2 * k + 1)) {
max = 2 * k + 1;
} else {
max = 2 * k;
}
} else {
max = 2 * k;
}
//比較當前結點和較大結點的值
if (!less(k, max)) {
break;
}
//交換k索引處的值和max索引處的值
exch(k, max);
//變換k的值
k = max;
}
}
public static void main(String[] args) {
Heap<String> heap = new Heap<String>(20);
heap.insert("A");
heap.insert("B");
heap.insert("C");
heap.insert("D");
heap.insert("E");
heap.insert("F");
heap.insert("G");
String del;
//迴圈刪除
while ((del = heap.delMax()) != null) {
System.out.print(del + ",");
}
}
}
④雜湊表
❶基礎知識
雜湊表(Hash table)，是根據關鍵碼值(Key value)而直接進行存取的資料結構。也就是說，它通過把關鍵碼值對映到表中一個位置來存取記錄，以加快查詢的速度。這個對映函數叫做雜湊函數，存放記錄的陣列叫做雜湊表。
常見的三種雜湊結構
- 陣列
int[] hashTable = new int[26]; //存26字母索引
//hashTable[s.charAt(i) - 'a']++; 字母存在則在對應位置加1
- set （集合）
Set<Integer> set = new HashSet<>();
//set.add(num) 插入元素
//set.contains(num) 查詢鍵是否存在
- map（對映）
Map<Integer, Integer> map = new HashMap<>();
//map.put(key,value) 插入元素
//map.getOrDefault(ch, 0); 查詢map是否存在ch,不存在設定預設值0
//map.values() 返回所有value
//map.containsKey(key) 查詢鍵是否存在
//map.isEmpty() 判斷是否為空
//map.get() 根據鍵獲取值
//map.remove() 根據鍵刪除對映關係
⑤字串
雙指標：344. 反轉字串
編寫一個函數，其作用是將輸入的字串反轉過來。輸入字串以字元陣列 s 的形式給出。
不要給另外的陣列分配額外的空間，你必須原地修改輸入陣列、使用 O(1) 的額外空間解決這一問題。
範例 1：
輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
範例 2：
輸入：s = ["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //構造 a ^ b 的結果，並放在 a 中
s[r] ^= s[l]; //將 a ^ b 這一結果再 ^ b ，存入b中，此時 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的結果再 ^ a ，存入 a 中，此時 b = a, a = b 完成交換
l++;
r--;
}
}
}
雙指標： 541. 反轉字串 II
給定一個字串 s 和一個整數 k，從字串開頭算起，每計數至 2k 個字元，就反轉這 2k 字元中的前 k 個字元。
- 如果剩餘字元少於
k個，則將剩餘字元全部反轉。 - 如果剩餘字元小於
2k但大於或等於k個，則反轉前k個字元，其餘字元保持原樣。
範例 1：
輸入：s = "abcdefg", k = 2
輸出："bacdfeg"
範例 2：
輸入：s = "abcd", k = 2
輸出："bacd"
題意：每隔2k個反轉前k個，尾數不夠k個時候全部反轉
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
// 1. 每隔 2k 個字元的前 k 個字元進行反轉
for (int i = 0; i < n; i += 2 * k) {
// 2. 剩餘字元小於 2k 但大於或等於 k 個，則反轉前 k 個字元
if (i + k <= n) {
reverse(arr, i, i + k - 1);
continue;
}
// 3. 剩餘字元少於 k 個，則將剩餘字元全部反轉
reverse(arr, i, n - 1);
}
return new String(arr);
}
// 定義翻轉函數
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for (int i = 0; i < n; i += 2 * k) {
// 1. 每隔 2k 個字元的前 k 個字元進行反轉
// 2. 剩餘字元小於 2k 但大於或等於 k 個，則反轉前 k 個字元
reverse(arr, i, Math.min(i + k, n) - 1);
}
return String.valueOf(arr);
}
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
雙指標：345. 反轉字串中的母音字母
給你一個字串 s ，僅反轉字串中的所有母音字母，並返回結果字串。
母音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小寫兩種形式出現不止一次。
範例 1：
輸入：s = "hello"
輸出："holle"
範例 2：
輸入：s = "leetcode"
輸出："leotcede"
class Solution {
public String reverseVowels(String s) {
//定義兩個哨兵
int l = 0, r = s.length() - 1;
char[] arr = s.toCharArray();
while (l < r) {
//從左往右找母音字母，找到就停止，沒找到就繼續右移
while (!"aeiouAEIOU".contains(String.valueOf(arr[l])) && l < r) l++;
//從右往左找母音字母，找到就停止，沒找到就繼續左移
while (!"aeiouAEIOU".contains(String.valueOf(arr[r])) && l < r) r--;
//兩邊都找到就交換它們
if (l < r) {
char temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
}
return new String(arr);
}
}
雙指標：1768. 交替合併字串
給你兩個字串 word1 和 word2 。請你從 word1 開始，通過交替新增字母來合併字串。如果一個字串比另一個字串長，就將多出來的字母追加到合併後字串的末尾。
返回 合併後的字串 。
範例 1：
輸入：word1 = "abc", word2 = "pqr"
輸出："apbqcr"
解釋：字串合併情況如下所示：
word1： a b c
word2： p q r
合併後： a p b q c r
範例 2：
輸入：word1 = "ab", word2 = "pqrs"
輸出："apbqrs"
解釋：注意，word2 比 word1 長，"rs" 需要追加到合併後字串的末尾。
word1： a b
word2： p q r s
合併後： a p b q r s
範例 3：
輸入：word1 = "abcd", word2 = "pq"
輸出："apbqcd"
解釋：注意，word1 比 word2 長，"cd" 需要追加到合併後字串的末尾。
word1： a b c d
word2： p q
合併後： a p b q c d
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int m = word1.length(), n = word2.length();
int i = 0, j = 0;
while(i < m && j < n){
sb.append(word1.charAt(i));
sb.append(word2.charAt(j));
i++;
j++;
}
while(i < m){
sb.append(word1.charAt(i));
i++;
}
while(j < n){
sb.append(word2.charAt(j));
j++;
}
return sb.toString();
}
}
class Solution {
public String mergeAlternately(String word1, String word2) {
StringBuilder sb = new StringBuilder();
int m = word1.length(), n = word2.length();
int i = 0, j = 0;
while(i < m || j < n){
if(i < m){
sb.append(word1.charAt(i));
i++;
}
if(j < n){
sb.append(word2.charAt(j));
j++;
}
}
return sb.toString();
}
}
⑥雙指標
344. 反轉字串
編寫一個函數，其作用是將輸入的字串反轉過來。輸入字串以字元陣列 s 的形式給出。
不要給另外的陣列分配額外的空間，你必須原地修改輸入陣列、使用 O(1) 的額外空間解決這一問題。
範例 1：
輸入：s = ["h","e","l","l","o"]
輸出：["o","l","l","e","h"]
範例 2：
輸入：s = ["H","a","n","n","a","h"]
輸出：["h","a","n","n","a","H"]
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
class Solution {
public void reverseString(char[] s) {
int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //構造 a ^ b 的結果，並放在 a 中
s[r] ^= s[l]; //將 a ^ b 這一結果再 ^ b ，存入b中，此時 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的結果再 ^ a ，存入 a 中，此時 b = a, a = b 完成交換
l++;
r--;
}
}
}
27. 移除元素
給你一個陣列 nums 和一個值 val，你需要原地移除所有數值等於 val 的元素，並返回移除後陣列的新長度。
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間並原地修改輸入陣列。
元素的順序可以改變。你不需要考慮陣列中超出新長度後面的元素。
範例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數應該返回新的長度 2, 並且 nums 中的前兩個元素均為 2。你不需要考慮陣列中超出新長度後面的元素。例如，函數返回的新長度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也會被視作正確答案。
範例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋：函數應該返回新的長度 5, 並且 nums 中的前五個元素為 0, 1, 3, 0, 4。注意這五個元素可為任意順序。你不需要考慮陣列中超出新長度後面的元素。
//雙指標
class Solution {
public int removeElement(int[] nums, int val) {
//快慢指標解法
int slow = 0; //慢指標
//快指標，無論與val值是否相同每遍歷一次都要移動一位
for(int fast = 0; fast < nums.length; fast++){
//快指標先走，判斷快指標指向的元素是否等於val
if(nums[fast] != val){
nums[slow] = nums[fast];
slow++; //只有當快指標不等於val的時候，慢指標才和快指標一起移動一位
}
}
return slow;
}
}
//通用解法
class Solution {
public int removeElement(int[] nums, int val) {
int idx = 0;
for (int x : nums) {
if (x != val) nums[idx++] = x;
}
return idx;
}
}
283. 移動零
給定一個陣列 nums，編寫一個函數將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序。
請注意 ，必須在不復制陣列的情況下原地對陣列進行操作。
範例 1:
輸入: nums = [0,1,0,3,12]
輸出: [1,3,12,0,0]
範例 2:
輸入: nums = [0]
輸出: [0]
class Solution {
public void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0
// 返回去除 0 之後的陣列長度
int p = removeElement(nums, 0);
// 將 p 之後的所有元素賦值為 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 雙指標技巧，複用 [27. 移除元素] 的解法。
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
快排思想，用 0 當做這個中間點，把不等於 0的放到中間點的左邊，等於 0 的放到其右邊。使用兩個指標 i 和 j，只要 nums[i]!=0，我們就交換 nums[i] 和 nums[j]
class Solution {
public void moveZeroes(int[] nums) {
if(nums == null) return;
//兩個指標i和j
int j = 0;
for(int i = 0; i < nums.length; i++) {
//當前元素!=0，就把其交換到左邊，等於0的交換到右邊
if(nums[i] != 0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j++] = tmp;
}
}
}
}
⑦二元樹
二元樹基礎知識
- 二元樹（Binary tree）是樹形結構的一個重要型別。許多實際問題抽象出來的資料結構往往是二元樹形式，即使是一般的樹也能簡單地轉換為二元樹，而且二元樹的儲存結構及其演演算法都較為簡單，因此二元樹顯得特別重要。二元樹特點是每個節點最多隻能有兩棵子樹，且有左右之分
- 二元樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根（root）的元素及兩個不相交的、被分別稱為左子樹和右子樹的二元樹組成，是有序樹。當集合為空時，稱該二元樹為空二元樹。在二元樹中，一個元素也稱作一個節點
//Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
我們有一棵二元樹：
根
/ \
左 右
棧是一種 先進後出的結構，那麼入棧順序必須調整為倒序
- 前序遍歷，出棧順序：根左右; 入棧順序：右左根
- 中序遍歷，出棧順序：左根右; 入棧順序：右根左
- 後序遍歷，出棧順序：左右根; 入棧順序：根右左
❶二元樹遍歷
144. 二元樹的前序遍歷
先輸出父節點，再遍歷左子樹和右子樹
1.遞迴
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res;
}
public void dfs(TreeNode root, List<Integer> res){
if(root == null){
return;
}
res.add(root.val);
dfs(root.left, res);
dfs(root.right, res);
}
}
2.迭代
- 彈棧頂入列表
- 如有右，先入右
- 如有左，再入左
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();// 用棧來實現迭代
stack.push(root);
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
res.add(tmp.val);
if(tmp.right != null){ //先進右節點，後出
stack.push(tmp.right);
}
if(tmp.left != null){ //後進左節點，先出
stack.push(tmp.left);
}
}
return res;
}
}
94. 二元樹的中序遍歷
先遍歷左子樹，再輸出父節點，再遍歷右子樹
1.遞迴
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res;
}
public void dfs(TreeNode root, List<Integer> res){
if(root == null){
return;
}
dfs(root.left, res);
res.add(root.val);
dfs(root.right, res);
}
}
2.迭代
- 根結點不為空，入棧並向左走。整條界依次入棧
- 根結點為空，彈棧頂列印，向右走。
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
while (root != null) { // 將根和左子樹入棧
stack.push(root);
root = root.left;
}
//當前節點為空，說明左邊走到頭了，從棧中彈出節點並儲存
TreeNode tmp = stack.pop();
res.add(tmp.val);
//然後轉向右邊節點，繼續上面整個過程
root = tmp.right;
}
return res;
}
}
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
TreeNode tmp = stack.pop();
res.add(tmp.val);
root = tmp.right;
}
}
return res;
}
}
145. 二元樹的後序遍歷
先遍歷左子樹，再遍歷右子樹，最後輸出父節點
1.遞迴
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res;
}
public void dfs(TreeNode root ,List<Integer> res){
if(root == null){
return;
}
dfs(root.left, res);
dfs(root.right, res);
res.add(root.val);
}
}
2.迭代
- 彈棧頂輸出
- 如有左，壓入左
- 如有右，壓入右
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode prev = null;
while (!stack.isEmpty() || root != null) {
while (root != null) { // 將左子樹全部入棧
stack.push(root);
root = root.left;
}
root = stack.pop(); // 拿取棧頂節點
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
// 重新把根節點入棧，處理完右子樹還要回來處理根節點
stack.push(root);
// 當前節點為右子樹
root = root.right;
}
}
return res;
}
}
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
if(root == null){
return res;
}
// 如果當前處理節點不為空或者棧中有資料則繼續處理
stack.push(root);
while (!stack.isEmpty()) {
TreeNode tmp = stack.pop();
res.add(tmp.val);
if(tmp.left != null) stack.push(tmp.left);
if(tmp.right != null) stack.push(tmp.right); //出棧根右左
}
Collections.reverse(res);//反轉之後：左右根
return res;
}
}
102. 二元樹的層序遍歷
1.遞迴
/**
*時間：O(n)
*空間：O(h)
**/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
dfs(root, 0, res);
return res;
}
public void dfs(TreeNode root, Integer level, List<List<Integer>> res) {
if (root == null) return;
if (res.size() <= level) {
//如果res.size() <= level說明下一層的集合還沒建立，所以要先建立下一層的集合
List<Integer> item = new ArrayList<Integer>();
res.add(item);
}
//遍歷到第幾層我們就操作第幾層的資料
List<Integer> list = res.get(level);
list.add(root.val);
//分別遍歷左右兩個子節點，到下一層了，所以層數要加1
dfs(root.left, level + 1, res);
dfs(root.right, level + 1, res);
}
}
2.迭代
/**
*時間：O(n)
*空間：O(n)
**/
//藉助佇列
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
//Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 0; i < currentLevelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
res.add(level);
}
return res;
}
}
103. 二元樹的鋸齒形層序遍歷
給你二元樹的根節點 root ，返回其節點值的 鋸齒形層序遍歷 。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。
範例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[20,9],[15,7]]
範例 2：
輸入：root = [1]
輸出：[[1]]
範例 3：
輸入：root = []
輸出：[]
遞迴
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
dfs(root, 0, res);
return res;
}
public void dfs(TreeNode root, Integer level, List<List<Integer>> res) {
if (root == null) return;
if (res.size() <= level) {
//如果res.size() <= level說明下一層的集合還沒建立，所以要先建立下一層的集合
List<Integer> item = new ArrayList<>();
res.add(item);
}
//遍歷到第幾層我們就操作第幾層的資料
List<Integer> list = res.get(level);
if (level % 2 == 0){
list.add(root.val); //根節點是第0層，偶數層相當於從左往右遍歷，所以要新增到集合的末尾
} else {
list.add(0, root.val); //如果是奇數層相當於從右往左遍歷，要把資料新增到集合的開頭
}
//分別遍歷左右兩個子節點，到下一層了，所以層數要加1
dfs(root.left, level + 1, res);
dfs(root.right, level + 1, res);
}
}
迭代
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean flag = true; // 為 true 時從左開始，false 時從右開始，第一步先從左邊開始列印
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int n = queue.size();
for(int i = 0; i < n; i++){
TreeNode node = queue.poll();
if (flag){
list.add(node.val);
} else {
list.add(0, node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
flag = !flag; // 切換方向
res.add(list);
}
return res;
}
}
⑧圖
圖這種資料結構有一些比較特殊的演演算法，比如二分圖判斷，有環圖無環圖的判斷，拓撲排序，以及最經典的最小生成樹，單源最短路徑問題，更難的就是類似網路流這樣的問題。
參考：圖論基礎及遍歷演演算法、二分圖判定演演算法、環檢測和拓撲排序、圖遍歷演演算法、名流問題、並查集演演算法計算連通分量、Dijkstra 最短路徑演演算法
圖論基礎
「圖」的兩種表示方法，鄰接表（連結串列），鄰接矩陣（二維陣列）。
鄰接矩陣判斷連通性迅速，並可以進行矩陣運算解決一些問題，但是如果圖比較稀疏的話很耗費空間。
鄰接表比較節省空間，但是很多操作的效率上肯定比不過鄰接矩陣。
 |
 |
|---|---|
鄰接表把每個節點 x 的鄰居都存到一個列表裡，然後把 x 和這個列表關聯起來，這樣就可以通過一個節點 x 找到它的所有相鄰節點。
鄰接矩陣則是一個二維布林陣列，我們權且稱為 matrix，如果節點 x 和 y 是相連的，那麼就把 matrix[x][y] 設為 true（上圖中綠色的方格代表 true）。如果想找節點 x 的鄰居，去掃一圈 matrix[x][..] 就行了。
如果用程式碼的形式來表現，鄰接表和鄰接矩陣大概長這樣：
// 鄰接表
// graph[x] 儲存 x 的所有鄰居節點
List<Integer>[] graph;
// 鄰接矩陣
// matrix[x][y] 記錄 x 是否有一條指向 y 的邊
boolean[][] matrix;
鄰接表建立
//把圖轉化成鄰接表
List<Integer>[] buildGraph(int x, int[][] edges) {
// 圖中共有 x 個節點
List<Integer>[] graph = new LinkedList[x];
for (int i = 0; i < x; i++) {
graph[i] = new LinkedList<>();
}
// edges = [[1,0],[0,1]]
for (int[] edge : edges) {
// from = 0, to = 1
int from = edge[1], to = edge[0];
// 新增一條從 from 指向 to 的有向邊
graph[from].add(to);
}
return graph;
}
圖遍歷
圖和多叉樹最大的區別是，圖是可能包含環的，你從圖的某一個節點開始遍歷，有可能走了一圈又回到這個節點，而樹不會出現這種情況，從某個節點出發必然走到葉子節點，絕不可能回到它自身。
所以，如果圖包含環，遍歷框架就要一個 visited 陣列進行輔助：
// 記錄被遍歷過的節點
boolean[] visited;
// 記錄從起點到當前節點的路徑
boolean[] onPath;
/* 圖遍歷框架 */
void traverse(Graph graph, int s) {
if (visited[s]) return; // 已被遍歷
// 經過節點 s，標記為已遍歷
visited[s] = true;
// 做選擇：標記節點 s 在路徑上
onPath[s] = true;
for (int neighbor : graph[s] {
traverse(graph, neighbor);
}
// 復原選擇：節點 s 離開路徑
onPath[s] = false;
}
環檢測
類比貪吃蛇遊戲，visited 記錄蛇經過過的格子，而 onPath 僅僅記錄蛇身。onPath 用於判斷是否成環，類比當貪吃蛇自己咬到自己（成環）的場景。
// 記錄一次遞迴路徑中的節點
boolean[] onPath;
// 記錄遍歷過的節點，防止走回頭路
boolean[] visited;
// 記錄圖中是否有環
boolean hasCycle = false;
void traverse(List<Integer>[] graph, int s) {
// 出現環
if (onPath[s]) {
hasCycle = true;
}
// 如果已經找到了環，也不用再遍歷了
if (visited[s] || hasCycle) {
return;
}
// 前序程式碼位置
visited[s] = true; // 將當前節點標記為已遍歷
onPath[s] = true; // 開始遍歷節點 s
for (int neighbor : graph[s]) {
traverse(graph, neighbor);
}
// 後序程式碼位置
onPath[s] = false; // 節點 s 遍歷完成
}