LeetCode刷题--点滴记录004

4. 图解算法数据结构

数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。

常见的数据结构

线性数据结构 ： 数组(Array)；链表(Linked List)；栈(Stack)；队列(Queue)
非线性数据结构 ： 数(Tree)；堆(Heap)；散列表(Hashing)；图(Graph)

数组(Array)

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。
C++版本

#include 
using namespace std;
#include 

void printVector(vector& v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
template 
void printArray(T& array)
{
    for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
}
void test01()
{
    // 初始化一个长度为 5 的数组
    int array[5];
    // 元素赋值
    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
    array[4] = 4;

    printArray(array);
}

void test02()
{
    int array[] = { 0, 1, 2, 3, 4 };

    printArray(array);
}

void test03()
{
    // 初始化可变数组
    vector array;

    // 向尾部添加元素
    array.push_back(0);
    array.push_back(1);
    array.push_back(2);
    array.push_back(3);
    array.push_back(4);

    printVector(array);
}
int main()
{
    test01();
    cout << "------------------" << endl;
    test02();
    cout << "------------------" << endl;
    test03();

    system("pause");
    return 0;
}

Python版本

def test01():
    array = [1, 2, 3, 4, 5]
    print(array)
def test02():
    # 初始化可变数组
    array = []

    # 向尾部添加元素
    array.append(1)
    array.append(2)
    array.append(3)
    array.append(4)
    array.append(5)
    
    print(array)
    # 切片
    print(array[0:3])
    print(array[:3])
    print(array[1:4])
    print(array[2:])
    
def test03():
    array = list(range(1,6))
    print(array)
    arrayeven = list(range(2,6,2))
    print(arrayeven)
    arrayodd = list(range(1,6,2))
    print(arrayodd)
            
if __name__=="__main__":
    test01()
    print("--------------")
    test02()
    print("--------------")
    test03()

Java版本

package com.hailei_01;

import java.util.ArrayList;
import java.util.List;

public class array {
    public static void main(String[] args) {
        // 初始化一个长度为 5 的数组 array
        int[] array1 = new int[5];
        // 元素赋值
        array1[0] = 1;
        array1[1] = 2;
        array1[2] = 3;
        array1[3] = 4;
        array1[4] = 5;
        for(int i=0;i
            System.out.print(array1[i]+" ");
        }
        System.out.println("n------------");

        int[] array2 = {1, 2, 3, 4, 5};
        for(int a:array2) //增强for
        {
            System.out.print(a+" ");
        }
        System.out.println("n------------");

        // 初始化可变数组
        List array3 = new ArrayList<>();

        // 向尾部添加元素
        array3.add(1);
        array3.add(2);
        array3.add(3);
        array3.add(4);
        array3.add(5);

        System.out.println(array3);
    }
}

链表(Linked List)

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。
C++版本

struct ListNode {
    int val;        // 节点值
    ListNode* next; // 后继节点引用
    ListNode(int x) : val(x), next(NULL) {}
};
void print(ListNode* phead)//输出
{
    ListNode* p = phead;
    while (p != NULL)
    {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}
void test01()
{
    // 实例化节点
    ListNode* n1 = new ListNode(1); // 节点 head
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);

    // 构建引用指向
    n1->next = n2;
    n2->next = n3;
    //打印输出
    print(n1);
    cout << "----------" << endl;
    print(n2);
}
int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

#include 
using namespace std;
class ListNode:
    def __init__(self, x):
        self.val = x     # 节点值
        self.next = None # 后继节点引用
        
def print_ListNode(node):
    while node:
        print(node.val, end=' ')
        node = node.next
        
def test01():
    # 实例化节点
    n1 = ListNode(3) # 节点 head
    n2 = ListNode(2)
    n3 = ListNode(1)

    # 构建引用指向
    n1.next = n2
    n2.next = n3
    print_ListNode(n1)
    print("n--------------") 
    print_ListNode(n2)

if __name__=="__main__":
    test01()

Java版本

package com.hailei_02;

public class listNode {
    public static void main(String[] args) {
        // 实例化节点
        ListNode n1 = new ListNode(9); // 节点 head
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(6);

        // 构建引用指向
        n1.next = n2;
        n2.next = n3;

        printListNode(n1);
        System.out.println("n-------------");
        printListNode(n3);

    }

    public static class ListNode {
        int val;       // 节点值
        ListNode next; // 后继节点引用
        ListNode(int x) { val = x; }
    }

    public static void printListNode(ListNode headNode) {
        ListNode listNode = headNode;
        while(listNode!=null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

栈(Stack)

栈是一种具有 先入后出 特点的抽象数据结构，可使用数组或链表实现。

C++版本

#include 
using namespace std;
#include 
void test01()
{
    stack stk;

    stk.push(1); // 元素 1 入栈
    stk.push(2); // 元素 2 入栈
    cout << "栈顶元素为：" << stk.size() << endl;
    stk.push(3); // 元素 3 入栈
    stk.push(4); // 元素 4 入栈
    cout << "栈顶元素为：" << stk.size() << endl;
    stk.pop();   // 出栈 -> 元素 4
    stk.pop();   // 出栈 -> 元素 3
    cout << "栈顶元素为：" << stk.size() << endl;
    stk.pop();   // 出栈 -> 元素 2
    stk.pop();   // 出栈 -> 元素 1
    cout << "栈顶元素为：" << stk.size() << endl;

}
int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

def test01():
    stack = [] # Python 可将列表作为栈使用
    stack.append(1) # 元素 1 入栈
    stack.append(2) # 元素 2 入栈
    print(stack)
    stack.append(3) # 元素 3 入栈
    stack.append(4) # 元素 4 入栈
    print(stack)
    stack.pop()     # 出栈 -> 元素 4
    stack.pop()     # 出栈 -> 元素 3
    print(stack)
    stack.pop()     # 出栈 -> 元素 2
    stack.pop()     # 出栈 -> 元素 1
    print(stack)

if __name__=="__main__":
    test01()

Java版本

package com.hailei_03;

import java.util.LinkedList;

public class stack {
    public static void main(String[] args) {
        LinkedList stack = new LinkedList<>();

        stack.addLast(1);   // 元素 1 入栈
        stack.addLast(2);   // 元素 2 入栈
        stack.addLast(3);   // 元素 3入栈
        stack.addLast(4);   // 元素 4 入栈
        System.out.println("第一个元素："+stack.getFirst());
        System.out.println("最后一个元素："+stack.getLast());
        stack.removeLast(); // 出栈 -> 元素 4
        stack.removeLast(); // 出栈 -> 元素 3
        System.out.println("第一个元素："+stack.getFirst());
        System.out.println("最后一个元素："+stack.getLast());
        stack.removeLast(); // 出栈 -> 元素 2
        stack.removeLast(); // 出栈 -> 元素 1
    }
}

队列(Queue)

队列是一种具有 先入先出 特点的抽象数据结构，可使用链表实现。

C++版本

#include 
using namespace std;
#include 
void test01()
{
    queue que;

    que.push(1); // 元素 1 入队
    que.push(2); // 元素 2 入队
    que.push(3); // 元素 3 入队
    que.push(4); // 元素 4 入队
    cout << "队头元素为：" << que.front() << endl;
    cout << "队尾元素为：" << que.back() << endl;
    que.pop();   // 出队 -> 元素 1
    que.pop();   // 出队 -> 元素 2
    cout << "队头元素为：" << que.front() << endl;
    cout << "队尾元素为：" << que.back() << endl;
    que.pop();   // 出队 -> 元素 3
    que.pop();   // 出队 -> 元素 4
    cout << "队列元素为：" << que.size() << endl;
}
int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

from collections import deque


def test01():
    que = deque()
    que.append(1) # 元素 1 入队
    que.append(2) # 元素 2 入队
    que.append(3) # 元素 3 入队
    que.append(4) # 元素 4 入队
    print(que)
    que.popleft() # 出队 -> 元素 1
    que.popleft() # 出队 -> 元素 2
    print(que)
    que.popleft() # 出队 -> 元素 3
    que.popleft() # 出队 -> 元素 4
    print(que)
    
if __name__=="__main__":
    test01()

Java版本

package com.hailei_04;

import java.util.LinkedList;
import java.util.Queue;

public class queue {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();
        queue.offer(1); // 元素 1 入队
        queue.offer(2); // 元素 2 入队
        System.out.println(queue);
        queue.offer(3); // 元素 3 入队
        queue.offer(4); // 元素 4 入队
        System.out.println(queue);
        queue.poll();   // 出队 -> 元素 1
        queue.poll();   // 出队 -> 元素 2
        System.out.println(queue);
        queue.poll();   // 出队 -> 元素 3
        queue.poll();   // 出队 -> 元素 4
        System.out.println(queue);
    }
}

树(Tree)

树是一种非线性数据结构，根据子节点数量可分为 二叉树 和 多叉树，最顶层的节点称为根节点 root。
二叉树，每个节点包含三个成员变量：值 val、左子节点 left、右子节点 right 。

C++版本

#include 
using namespace std;
struct TreeNode {
    int val;         // 节点值
    TreeNode* left;  // 左子节点
    TreeNode* right; // 右子节点
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void printTree(TreeNode * tree)
{
    TreeNode* n = tree;
    if (n != NULL)
    {
        cout << n->val <<" ";
        printTree(n->left);
        cout << endl;
        printTree(n->right);
    }
}

void test01()
{
    // 初始化节点
    TreeNode* n1 = new TreeNode(1); // 根节点 root
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    TreeNode* n4 = new TreeNode(4);
    TreeNode* n5 = new TreeNode(5);

    // 构建引用指向
    n1->left = n2;
    n1->right = n3;
    n2->left = n4;
    n2->right = n5;

    printTree(n1);
}

int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

class TreeNode:
    def __init__(self, x):
        self.val = x      # 节点值
        self.left = None  # 左子节点
        self.right = None # 右子节点
        
def printTree(tree):
    if tree:
        print(tree.val,end=' ')
        printTree(tree.left)
        print()
        printTree(tree.right) 
        
def test01():
    # 初始化节点
    n1 = TreeNode(1) # 根节点 root
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)

    # 构建引用指向
    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    
    printTree(n1)
    
if __name__=="__main__":
    test01()

Java版本

package com.hailei_05;

public class tree {
    public static void main(String[] args) {
        // 初始化节点
        TreeNode n1 = new TreeNode(1); // 根节点 root
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);

        // 构建引用指向
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        printTree(n1);
    }

    public static class TreeNode {
        int val;        // 节点值
        TreeNode left;  // 左子节点
        TreeNode right; // 右子节点
        TreeNode(int x) { val = x; }
    }

    public static void printTree(TreeNode tree)
    {
        TreeNode n = tree;
        if (n != null)
        {
            System.out.print(n.val+" ");
            printTree(n.left);
            System.out.println();
            printTree(n.right);
        }
    }
}

图(Graph)

图是一种非线性数据结构，由 节点（顶点）vertex 和 边 edge 组成，每条边连接一对顶点。根据边的方向有无，图可分为 有向图 和 无向图。
顶点集合： vertices = {1, 2, 3, 4, 5}
边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}
表示图的方法通常有两种：邻接矩阵和邻接表。

C++版本

#include 
using namespace std;
void test01()
{
    int vertices[5] = { 1, 2, 3, 4, 5 };
    int edges[5][5] = { {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} };
    int count = sizeof(vertices) / sizeof(vertices[0]);
    for (int i = 0;i < count; i++)
    {
        for (int j = 0; j < count; j++)
        {
            if (edges[i][j] == 0)
                cout << "顶点" << i << "和顶点" << j << "不连通" << endl;
            else
                cout << "顶点" << i << "和顶点" << j << "连通" << endl;
        }
    }
}

int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

def relationship(vertices,edges):

        count = len(vertices)
        adjlist = edges
        for i in range(count):
            for j in range(count):
                if adjlist[i][j] == 0:
                    print("顶点{}和{}不连通".format(i,j))
                else:
                    print("顶点{}和{}连通".format(i,j))

            
def test01():
    vertices = [1, 2, 3, 4, 5]
    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]]
    relationship(vertices,edges)
    
if __name__=="__main__":
    test01()

Java版本

package com.hailei_06;

public class graph {
    public static void main(String[] args) {
        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}};

        for(int i=0;i
            for(int j=0;j
                if (edges[i][j]==0)
                    System.out.println("顶点"+i+"和顶点"+j+"不连通");
                else
                    System.out.println("顶点"+i+"和顶点"+j+"连通");
            }
        }
    }
}

散列表(Hashing)

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的键 key映射至对应的值 value，以实现高效的元素查找。

C++版本

#include 
using namespace std;
#include 
#include 
void test01()
{
    // 初始化散列表
    unordered_map dic;

    // 添加 key -> value 键值对
    dic["qwe"] = 0001;
    dic["asd"] = 0002;
    dic["zxc"] = 0003;

    // 从姓名查找学号
    cout << "qwe的学号是：" << setw(4) << setfill('0') << dic.find("qwe")->second << endl;
    cout << "asd的学号是：" << setw(4) << setfill('0') << dic.find("asd")->second << endl;
    cout << "zxc的学号是：" << setw(4) << setfill('0') << dic.find("zxc")->second << endl;

}
int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

def test01():
    # 初始化散列表
    dic = {}
    # 添加 key -> value 键值对
    dic["qwe"] = 10001
    dic["asd"] = 10002
    dic["zxc"] = 10003

    # 从姓名查找学号
    print("qwe的学号是：{}".format(dic["qwe"]))
    print("asd的学号是：{}".format(dic["asd"]))
    print("zxc的学号是：{}".format(dic["zxc"]))

    
if __name__=="__main__":
    test01()

Java版本

package com.hailei_07;

import java.util.HashMap;
import java.util.Map;

public class hashing {
    public static void main(String[] args) {
        // 初始化散列表
        Map dic = new HashMap<>();

        // 添加 key -> value 键值对
        dic.put("asd", 0001);
        dic.put("qwe", 0002);
        dic.put("zxc", 0003);

        // 从姓名查找学号
        System.out.println("qwe的学号是：" + String.format("%04d",dic.get("qwe")));
        System.out.println("asd的学号是：" + String.format("%04d",dic.get("asd")));
        System.out.println("zxc的学号是：" + String.format("%04d",dic.get("zxc")));
    }
}

堆(Heap)

堆是一种基于完全二叉树的数据结构，可使用数组实现。以堆为原理的排序算法称为堆排序，基于堆实现的数据结构为优先队列。堆分为大顶堆和小顶堆，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。
完全二叉树定义： 设二叉树深度为 k ，若二叉树除第 kk层外的其它各层（第 1 至 k-1 层）的节点达到最大个数，且处于第 k 层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

C++版本

#include 
using namespace std;
#include 
void test01()
{
    // 初始化小顶堆
    priority_queue, greater> heap;

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

    // 元素出堆（从小到大）
    for (int i = 0; i < 5; i++)
    {
        cout << heap.top() << " ";
        heap.pop();
    }
    cout << endl;

}

int main()
{
    test01();

    system("pause");
    return 0;
}

Python版本

from heapq import heappush, heappop

def test01():
    # 初始化小顶堆
    heap = []

    # 元素入堆
    heappush(heap, 1)
    heappush(heap, 4)
    heappush(heap, 2)
    heappush(heap, 6)
    heappush(heap, 8)
    
    print(heap)
    heappop(heap)
    print(heap)
    heappop(heap)
    print(heap)
    heappop(heap)
    print(heap)
    heappop(heap)
    print(heap)
    heappop(heap)
    print(heap)

if __name__=="__main__":
    test01()

Java版本

package com.hailei_08;

import java.util.PriorityQueue;
import java.util.Queue;

public class heap {
    public static void main(String[] args) {
        // 初始化小顶堆
        Queue heap = new PriorityQueue<>();

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

        // 元素出堆（从小到大）
        System.out.println(heap);
        heap.poll(); // -> 1
        System.out.println(heap);
        heap.poll(); // -> 2
        System.out.println(heap);
        heap.poll(); // -> 4
        System.out.println(heap);
        heap.poll(); // -> 6
        System.out.println(heap);
        heap.poll(); // -> 8
        System.out.println(heap);

    }
}

希望本文对大家有帮助，上文若有不妥之处，欢迎指正

分享决定高度，学习拉开差距