力扣-圖解算法資料結構

常見的資料結構可分為「線性資料結構」與「非線性資料結構」，具體為：「數組」、「連結清單」、「棧」、「隊列」、「樹」、「圖」、「散清單」、「堆」。

力扣-圖解算法資料結構

數組

數組是将相同類型的元素存儲于連續記憶體空間的資料結構，其長度不可變。

如下圖所示，建構此數組需要在初始化時給定長度，并對數組每個索引元素指派，代碼如下：

public static void array() {
        // 初始化一個長度為5的數組 array
        int[] array=new int[5];
        //元素指派
        array[0]=2;
        array[1]=2;
        array[2]=2;
        array[3]=2;
        array[4]=2;
    }

力扣-圖解算法資料結構

「可變數組」是經常使用的資料結構，其基于數組和擴容機制實作，相比普通數組更加靈活。常用操作有：通路元素、添加元素、删除元素。

public static void arrayLen(){
        // 初始化可變數組
        List<Integer> array=new ArrayList<>();
        //向尾部添加元素
        array.add(2);
        array.add(2);
        array.add(2);
        array.add(2);
        array.add(2);
    }

連結清單

// 連結清單
    public  void linkedList(){
        //執行個體化節點
        ListNode n1=new ListNode(4);
        ListNode n2=new ListNode(5);
        ListNode n3=new ListNode(1);

        //建構引用指向
        n1.next=n2;
        n2.next=n3;
    }
    class ListNode{
        int val;    //節點值
        ListNode next;//後繼節點引用
        ListNode(int x){val=x;}
    }

力扣-圖解算法資料結構

棧

棧是一種具有「先入後出」特點的抽象資料結構，可使用數組或連結清單實作。

public void stack(){
        Stack<Integer> stack=new Stack<>();
        stack.push(1);//元素1 入棧
        stack.push(2);//元素2 入棧
        stack.pop(); //出棧--->元素2
        stack.pop();//出棧---->元素1

        //TODO 注意：通常情況下，不推薦使用Java的Vector以及其子類Stack，而一般将LinkedList作為棧來使用。
    }

如下圖所示，通過常用操作「入棧 push()」,「出棧 pop()」，展示了棧的先入後出特性。

力扣-圖解算法資料結構

注意：通常情況下，不推薦使用 Java 的 Vector 以及其子類 Stack ，而一般将 LinkedList 作為棧來使用。

public void stackflag(){
        LinkedList<Integer> stack=new LinkedList<>();

        stack.addLast(1); //元素1 入棧
        stack.addLast(2); //元素2 入棧
        stack.removeLast(); //出棧 -->元素2
        stack.removeLast();// 出棧--->元素1
    }

隊列

隊列是一種具有「先入先出」特點的抽象資料結構，可使用連結清單實作。

public void queue(){
        // 隊列是一種具有【先入先出】特點的抽象資料結構，可用連結清單實作
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(1);//元素1入隊
        queue.offer(2);//元素2入隊
        queue.poll();//出隊-->元素1
        queue.poll();//出隊-->元素2
    }

力扣-圖解算法資料結構

樹

樹是一種非線性資料結構，根據子節點數量可分為「二叉樹」和「多叉樹」，最頂層的節點稱為「根節點 root」。以二叉樹為例，每個節點包含三個成員變量：「值 val」、「左子節點 left」、「右子節點 right」。

class TreeNode{
        int val;    //節點值
        TreeNode left;//左子節點
        TreeNode right;//右子節點
        TreeNode(int x){val=x;}
    }
    
    public void treeNode(){
        //初始化節點
        TreeNode n1=new TreeNode(3); //根節點root
        TreeNode n2=new TreeNode(4);
        TreeNode n3=new TreeNode(5);
        TreeNode n4=new TreeNode(1);
        TreeNode n5=new TreeNode(2);

        //建構引用指向
        n1.left=n2;
        n1.right=n3;
        n2.left=n4;
        n2.right=n5;
    }

如下圖所示，建立此二叉樹需要執行個體化每個節點，并建構各節點的引用指向。

力扣-圖解算法資料結構

圖

圖是一種非線性資料結構，由「節點（頂點）vertex」和「邊 edge」組成，每條邊連接配接一對頂點。根據邊的方向有無，圖可分為「有向圖」和「無向圖」。本文以無向圖為例開展介紹。

如下圖所示，此無向圖的頂點和邊集合分别為：

頂點集合： vertices = {1, 2, 3, 4, 5}

邊集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

力扣-圖解算法資料結構

表示圖的方法通常有兩種：

鄰接矩陣：使用數組 verticesvertices 存儲頂點，鄰接矩陣 edgesedges 存儲邊； edges[i][j]edges[i][j] 代表節點 i + 1i+1 和節點 j + 1j+1 之間是否有邊。

力扣-圖解算法資料結構

public void figure(){
        //領接矩陣
        int[] vertices={1,2,3,4,5};
        int[][]edges={{0,1,1,1,1},
                {1,0,0,1,0},
                {1,0,0,0,1},
                {1,1,0,0,1},
                {1,0,1,1,0}};
    }

鄰接表：使用數組 verticesvertices 存儲頂點，鄰接表 edgesedges 存儲邊。 edgesedges 為一個二維容器，第一維 ii 代表頂點索引，第二維 edges[i]edges[i] 存儲此頂點對應的邊集和；例如 edges[0] = [1, 2, 3, 4]edges[0]=[1,2,3,4] 代表 vertices[0]vertices[0] 的邊集合為 [1, 2, 3, 4][1,2,3,4] 。

力扣-圖解算法資料結構

public void figure2(){
        //鄰接表
        int[] vertices={1,2,3,4,5};
        List<List<Integer>>edges=new ArrayList<>();

        List<Integer> edge_1=new ArrayList<>(Arrays.asList(1,2,3,4));
        List<Integer> edge_2=new ArrayList<>(Arrays.asList(0,3));
        List<Integer> edge_3=new ArrayList<>(Arrays.asList(0,4));
        List<Integer> edge_4=new ArrayList<>(Arrays.asList(0,1,4));
        List<Integer> edge_5=new ArrayList<>(Arrays.asList(0,2,3));
        edges.add(edge_1);
        edges.add(edge_2);
        edges.add(edge_3);
        edges.add(edge_4);
        edges.add(edge_5);
    }

鄰接矩陣 VS 鄰接表：

鄰接矩陣的大小隻與節點數量有關，即 N2

，其中 N 為節點數量。是以，當邊數量明顯少于節點數量時，使用鄰接矩陣存儲圖會造成較大的記憶體浪費。

是以，鄰接表适合存儲稀疏圖（頂點較多、邊較少）；鄰接矩陣适合存儲稠密圖（頂點較少、邊較多）。

散清單

散清單是一種非線性資料結構，通過利用 Hash 函數将指定的「鍵 key」映射至對應的「值 value」，以實作高效的元素查找。

設想一個簡單場景：小力、小特、小扣的學号分别為 10001, 10002, 10003 。

現需求從「姓名」查找「學号」

public void simpleHash(){
        String[] names={"小力","小特","小扣"};

        System.out.println(names[hash(10001)]);
        System.out.println(names[hash(10002)]);
        System.out.println(names[hash(10003)]);
    }
    int hash(int id){
        int index=(id-1)%10000;
        return index;
    }

力扣-圖解算法資料結構

堆：

堆是一種基于「完全二叉樹」的資料結構，可使用數組實作。以堆為原理的排序算法稱為「堆排序」，基于堆實作的資料結構為「優先隊列」。堆分為「大頂堆」和「小頂堆」，大（小）頂堆：任意節點的值不大于（小于）其父節點的值。

完全二叉樹定義：設二叉樹深度為 kk ，若二叉樹除第 kk 層外的其它各層（第 11 至 k-1k−1 層）的節點達到最大個數，且處于第 kk 層的節點都連續集中在最左邊，則稱此二叉樹為完全二叉樹。

如下圖所示，為包含 1, 4, 2, 6, 8 元素的小頂堆。将堆（完全二叉樹）中的結點按層編号，即可映射到右邊的數組存儲形式。

力扣-圖解算法資料結構

public void heap(){
        //初始化小頂堆
        Queue<Integer> heap=new PriorityQueue<>();

        //元素入堆
        heap.add(1);
        heap.add(4);
        heap.add(2);
        heap.add(6);
        heap.add(8);

        //元素出堆(從小到大)
        heap.poll();//->1
        heap.poll();//->2
        heap.poll();//->4
        heap.poll();//->6
        heap.poll();//->8
    }

所有代碼

import java.util.*;

/**
 * @program: mydemo
 * @description: this is a class
 * @author: Mr.zeng
 * @create: 2021-03-04 10:44
 **/
public class DataStructure1 {
    public static void array() {
        // 初始化一個長度為5的數組 array
        int[] array=new int[5];
        //元素指派
        array[0]=2;
        array[1]=2;
        array[2]=2;
        array[3]=2;
        array[4]=2;
    }
    public static void arrayLen(){
        // 初始化可變數組
        List<Integer> array=new ArrayList<>();
        //向尾部添加元素
        array.add(2);
        array.add(2);
        array.add(2);
        array.add(2);
        array.add(2);
    }
    // 連結清單
    public  void linkedList(){
        //執行個體化節點
        ListNode n1=new ListNode(4);
        ListNode n2=new ListNode(5);
        ListNode n3=new ListNode(1);

        //建構引用指向
        n1.next=n2;
        n2.next=n3;
    }
    class ListNode{
        int val;    //節點值
        ListNode next;//後繼節點引用
        ListNode(int x){val=x;}
    }

    public void stack(){
        Stack<Integer> stack=new Stack<>();
        stack.push(1);//元素1 入棧
        stack.push(2);//元素2 入棧
        stack.pop(); //出棧--->元素2
        stack.pop();//出棧---->元素1

        //TODO 注意：通常情況下，不推薦使用Java的Vector以及其子類Stack，而一般将LinkedList作為棧來使用。

    }
    public void stackflag(){
        LinkedList<Integer> stack=new LinkedList<>();

        stack.addLast(1); //元素1 入棧
        stack.addLast(2); //元素2 入棧
        stack.removeLast(); //出棧 -->元素2
        stack.removeLast();// 出棧--->元素1
    }


    public void queue(){
        // 隊列是一種具有【先入先出】特點的抽象資料結構，可用連結清單實作
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(1);//元素1入隊
        queue.offer(2);//元素2入隊
        queue.poll();//出隊-->元素1
        queue.poll();//出隊-->元素2
    }

    class TreeNode{
        int val;    //節點值
        TreeNode left;//左子節點
        TreeNode right;//右子節點
        TreeNode(int x){val=x;}
    }
    public void treeNode(){
        //初始化節點
        TreeNode n1=new TreeNode(3); //根節點root
        TreeNode n2=new TreeNode(4);
        TreeNode n3=new TreeNode(5);
        TreeNode n4=new TreeNode(1);
        TreeNode n5=new TreeNode(2);

        //建構引用指向
        n1.left=n2;
        n1.right=n3;
        n2.left=n4;
        n2.right=n5;
    }
    // 表示圖的方法通常有兩種
    public void figure(){
        //領接矩陣
        int[] vertices={1,2,3,4,5};
        int[][]edges={{0,1,1,1,1},
                {1,0,0,1,0},
                {1,0,0,0,1},
                {1,1,0,0,1},
                {1,0,1,1,0}};
    }
    public void figure2(){
        //鄰接表
        int[] vertices={1,2,3,4,5};
        List<List<Integer>>edges=new ArrayList<>();

        List<Integer> edge_1=new ArrayList<>(Arrays.asList(1,2,3,4));
        List<Integer> edge_2=new ArrayList<>(Arrays.asList(0,3));
        List<Integer> edge_3=new ArrayList<>(Arrays.asList(0,4));
        List<Integer> edge_4=new ArrayList<>(Arrays.asList(0,1,4));
        List<Integer> edge_5=new ArrayList<>(Arrays.asList(0,2,3));
        edges.add(edge_1);
        edges.add(edge_2);
        edges.add(edge_3);
        edges.add(edge_4);
        edges.add(edge_5);
    }
    //鄰接矩陣 VS 鄰接表：
    //鄰接矩陣的大小隻與節點數量有關，即N^ ，其中N為節點數量。是以，當邊數量明顯少于節點數量時，使用鄰接矩陣存儲圖會造成較大的記憶體浪費


    public void hashTable(){
        //初始化散清單
        Map<String,Integer> dic=new HashMap<>();

        //添加key->value 鍵值對
        dic.put("小力",10001);
        dic.put("小特",10002);
        dic.put("小扣",10003);

        //從姓名查找學号
        dic.get("小力");//->10001
        dic.get("小特");//->10002
        dic.get("小扣");//->10003
    }

    public void simpleHash(){
        String[] names={"小力","小特","小扣"};

        System.out.println(names[hash(10001)]);
        System.out.println(names[hash(10002)]);
        System.out.println(names[hash(10003)]);
    }
    int hash(int id){
        int index=(id-1)%10000;
        return index;
    }

    public void heap(){
        //初始化小頂堆
        Queue<Integer> heap=new PriorityQueue<>();

        //元素入堆
        heap.add(1);
        heap.add(4);
        heap.add(2);
        heap.add(6);
        heap.add(8);

        //元素出堆(從小到大)
        heap.poll();//->1
        heap.poll();//->2
        heap.poll();//->4
        heap.poll();//->6
        heap.poll();//->8
    }

    public static void main(String[] args) {
        new DataStructure1().simpleHash();;
    }
}

力扣-圖解算法資料結構

繼續閱讀

<LeetCode>三道腦筋急轉彎程式設計題

求水窪的問題——深度優先算法

200. 島嶼的個數（深度優先搜尋）

dfs深度優先搜尋_圖的深度優先搜尋（DFS）

【算法提高班】貪婪政策

#每日一題力扣第28題采購方案

【python】：布爾運算

python學習日記01python學習筆記（01）

學習日記05（判斷和循環）python學習日記（05）

對角線周遊LeetCode–對角線周遊

查找算法之二分查找查找算法之二分查找

LeetCode-110-平衡二叉樹-C語言

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

LeetCode OJ Binary Tree Right Side View

leetcode809