数据结构与算法


数据结构

线性结构:数组、队列、链表、栈

  • 顺序存储(地址连续)
  • 链式存储(地址不一定连续)

非线性结构:二维数组、多维数组、广义表、树、图

数组

稀疏数组

稀疏数组是一种用来压缩数据量的数据结构,简而言之,就是记录特殊值,然后剩下大量重复的数据可以消减。

例如下方是一个普通二维数组

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());

    }
}

数组LeetCode

704. 二分查找

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
        return -1;
    }
}

27. 移除元素

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;
    }
}

队列

普通队列-Queue

常用方法

函数 功能
add(E e)/offer(E e) 压入元素
remove()/poll() 弹出元素
element()/peek() 获取队头元素
pop() 出栈(拿出栈顶元素,并得到它的值)
peek() 将栈顶元素返回,但是不从栈中移除它
search(Object o) 返回对象在此堆栈上的从1开始的位置。
isEmpty() 用于检查此队列是“空”还是“非空”
size() 获取队列长度

双端队列-Deque

Java集合提供了接口Deque来实现一个双端队列,它的功能是:

  • 既可以添加到队尾,也可以添加到队首;
  • 既可以从队首获取,又可以从队尾获取。

Deque有三种用途

  • 普通队列(一端进另一端出):
Deque deque = new LinkedList() 
// 等价 
Queue queue = new LinkedList()
  • 双端队列(两端都可进出)
Deque deque = new LinkedList()
  • 堆栈
Deque deque = new LinkedList()
// 等价  
Stack<String> stack=new Stack<>();   
方法 描述
添加功能
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

注意:Java 堆栈 Stack 类已经过时,Java 官方推荐使用 Deque 替代 Stack 使用。Deque 堆栈操作方法:push()、pop()、peek()。

创建栈

Stack<E> stack=new Stack<>();
Stack<String> stack=new Stack<>();

常用方法

函数 功能
isEmpty() 判断栈是否为空
size() 获取栈长度
push(T t) 压栈(向栈顶放入元素)
pop() 出栈(拿出栈顶元素,并得到它的值)
peek() 将栈顶元素返回,但是不从栈中移除它
search(Object o) 返回对象在此堆栈上的从1开始的位置。

二叉树

前序

中序

后序

层序

算法

DFS

BFS

回溯

关系:回溯 < DFS < 递归

递归

迭代

动态规划

❤️Sponsor

您的支持是我不断前进的动力,如果您恰巧财力雄厚,又感觉本文对您有所帮助的话,可以考虑打赏一下本文,用以维持本博客的运营费用,拒绝白嫖,从你我做起!🥰🥰🥰

支付宝支付 微信支付

文章作者: 简简
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 简简 !
评论
填上邮箱会收到评论回复提醒哦!!!
 上一篇
《网络攻击与防御技术》学习笔记 《网络攻击与防御技术》学习笔记
前言由于本校所用教材为:张玉清主编,清华大学出版社出版的《网络攻击与防御技术》,因此本文是基于此书进行学习及总结的,本文章着重于理论知识,没有实战应用。 《网络攻击与防御技术》PDF 下载地址:蓝奏云 第一章 网络安全概述1.网络安全基础知
2020-03-31
下一篇 
Drozer-Android安全测试 Drozer-Android安全测试
1.Drozer简介 drozer是一款针对Android系统的安全测试框架。drozer可以帮助App和设备变得更安全,其提供了很多Android平台下的渗透测试exploit供你使用和分享。对于远程的exploit,它可以生成shell
2020-03-23
  目录