数据结构
线性结构：数组、队列、链表、栈
- 顺序存储（地址连续）
- 链式存储（地址不一定连续）
非线性结构：二维数组、多维数组、广义表、树、图
数组
稀疏数组
稀疏数组是一种用来压缩数据量的数据结构，简而言之，就是记录特殊值，然后剩下大量重复的数据可以消减。
例如下方是一个普通二维数组
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
您的支持是我不断前进的动力，如果您恰巧财力雄厚，又感觉本文对您有所帮助的话，可以考虑打赏一下本文，用以维持本博客的运营费用，拒绝白嫖，从你我做起！🥰🥰🥰
| 支付宝支付 | 微信支付 |
 |
 |
