当前位置：首页 > 行业知识 > 数据结构与算法(数组,栈,队列,链表,哈希表,搜索算法,排序算法,查找算法,策略算法,递归算法,二叉搜索树BST,动态规划算法)

行业知识

数据结构与算法(数组,栈,队列,链表,哈希表,搜索算法,排序算法,查找算法,策略算法,递归算法,二叉搜索树BST,动态规划算法)

2026-11-01 08:07:48 来源：互联网转载

文章目录

1 课程介绍

1.1 前置知识
1.2 为什么要学习算法
1.3 大厂面试常见数据结构题目(基础)
1.4 数据结构和算法的关系
2 数据结构

2.1 数据结构概述

2.1.1 数据结构是什么
2.1.2 数据结构分类

2.1.2.1 线性结构
2.1.2.2 非线性结构
2.1.2.3 小总结
2.1.3 数据结构范围
2.2 数组Array

2.2.1 基础知识
2.2.2 数组优缺点

2.2.2.1 优点
2.2.2.2 缺点
2.2.2.3 数组内存分配
2.2.3 数据练习

2.2.3.1 热身课堂小练习，正序+反序打印数组
2.2.3.2 架构设计一个通用数组
2.2.3.4 普通版步骤V1
2.3.4.5 泛型版步骤V2
2.2.3.6 课堂练习，规范的定制化接口IMyArray
3.4.7 (泛型版++)步骤V3(解决扩缩容)
2.2.4 leetcode数组练习经典题
2.2.5 稀疏数组

2.2.5.1 什么是稀疏数组
2.2.5.2 实际应用
2.2.5.3 代码
2.2.5.4 作业
2.3 栈Stack

2.3.1 基础知识

2.3.1.1 先进后出/后进先出最经典的案例-子弹弹夹
2.3.1.2 是什么
2.3.1.3 还有吗？
2.3.1.4 小口诀
2.3.2 栈相关操作
2.3.3 架构设计一个通用栈，考虑封装的思想

2.3.3.1 判断条件
2.3.3.2 IStackDesc栈接口
2.3.3.3 MyStack
2.3.3.4 对象游离(loitering)
2.3.4 leetcode栈经典题
2.4 队列Queue

2.4.1 基础知识

2.4.1.1 先进先出最经典的案例-排队打饭
2.4.1.2 是什么
2.4.1.3 还有吗？
2.4.1.4 小口诀
2.4.2 架构设计一个队列，考虑封装问题

2.4.2.1 判断
2.4.2.2 队列接口IQueueDesc
2.4.2.3 MyQueue
2.5 链表

2.5.1 基础知识

2.5.1.1 最经典的案例-火车挂车厢
2.5.1.2 是什么
2.5.2 链表优缺点

2.5.2.1 优点
2.5.2.2 缺点
2.5.3 单链表

2.5.3.1 如何构造Node节点？

**内嵌**自定义
**外部**自定义
2.5.3.2 单链表-MyLinkedListV1
2.5.3.4 MyLinkedListV1-(增-过渡版本)
2.5.3.5 MyLinkedListV2-(增改进版本)
2.5.3.6 MyLinkedListV2-(改+查+含+印)
2.5.3.7 MyLinkedListV3-(删)
2.5.3.8 小总结
2.5.4 leetcode链表练习经典题，课堂练习

2.5.4.1 反向遍历打印单链表
2.5.4.2 反转链表
2.5.4.3 链表中倒数第k个节点
2.5.5 家庭作业，提交到leecode

2.5.5.1 接口IStackDesc
2.5.5.2 链表模拟-栈
2.5.5.3 链表模拟-队列
2.5.5.4 leecode203 移除链表元素
2.5.5.5 leecode24 两两交换链表中的节点
2.5.5.6 leecode19 删除链表的倒数第N个节点
2.5.6 双向链表

2.5.6.1 分析
2.5.6.2 实现
2.6 哈希表

2.6.1 基础知识

2.6.1.1 是什么
2.6.1.2 关键一句话
2.6.1.3 通过一个生活案例来学习哈希表这一数据结构
2.6.2 筑牢基础，课前HashMap源码小复习10分钟
2.6.3 请写一个hash冲突的案例
2.6.4 哈希表性能分析
2.6.5 架构设计一个哈希表，考虑的封装问题

6.5.1 数据结构说明
6.5.2 MyHashTable
2.6.6 leetcode哈希表练习经典题

2.6.6.1 查找字符串中第一个只出现一次的字符

hash存储频数：
hash存储索引：
2.6.6.2 两数之和

暴力法
哈希(更优解法)
All-idea
3 算法

3.1 算法概述

3.1.1 算法是什么
3.1.2 算法分类

3.1.2.1 常见搜索算法
3.1.2.2 常见排序算法
3.1.2.3 常见查找算法
3.1.2.4 常见实现策略算法
3.2.3 如何评价一个算法的好坏
3.2.4 高中数学：对数函数vs指数函数复习

3.2.4.1 补充说明
3.2.5 复杂度的大欧O(X)表示法
3.2.6 常见时间复杂度
3.2 递归算法

3.2.1 基础知识

3.2.1.1 是什么?何为递归?
3.2.1.2 关键一句话
3.2.1.3 构成递归需具备的2个条件
3.2.1.4 能干嘛
3.2.2 递归编码的基本功(套路+模板)

3.2.2.1 没有退出机制，栈溢出
3.2.2.2 课堂小练习
3.2.3 递归经典案例

3.2.3.1 斐波那契数列
3.2.3.2 阶乘

普通阶乘
大数阶乘
3.2.4 小总结
3.3 二叉搜索树BST

3.3.1 先来看看面试题
3.3.2 树(Tree)
3.3.3 二叉搜索树(Binary Search Tree)基础知识
3.3.4 架构设计一个二叉搜索树(Binary Search Tree)

3.3.4.1 二叉树编码操作基本功 (套路+模板)
3.3.4.2 第1版BSTV1(初始化+增)
3.3.4.3 第2版BSTV2(改进增+查)
3.3.4.4 修改不用考虑，想想为啥？
3.3.4.5 第3版BSTV3(V2+印【递归版】(前中后)+测试)
3.3.4.6 上面二叉树递归遍历的问题，请谈谈
3.3.5 深度优先 VS 广度优先

3.3.5.1 二叉树【非递归】遍历之DFS

前序：根-左-右，非递归算法
中序：左-根-右，非递归算法
后序：左-右-根，非递归算法
代码参考AllCode——非递归
3.3.5.2 二叉树【非递归】遍历之BFS
3.3.5.3 DFS+BFS小总结
3.3.6 架构设计一个二叉搜索树(Binary Search Tree)，二次优化++

3.3.6.1 寻找二分搜索树的最小元素、删除最小元素
3.3.6.2 家庭作业、找最大元素，删最大元素
3.3.6.3 删除二分搜索树的任意元素理论

难在哪里？？？
待删除节点，只有左子树
待删除节点，只有右子树
待删除节点，两边都有树(Hibbard delete)
上位图示
3.3.6.4 删除任意节点实操BSTRemoveNodeDemo
3.3.7 LeetCode课堂练习

226. 翻转二叉树

破题——递归+交换铁三角
3.3.8 递归+非递归+DFS+BFS全家福大总结(家庭作业)
3.3.9 LeetCode(家庭作业)

144.二叉树的前序遍历(必须做)
94.二叉树的中序遍历(必须做)
145.二叉树的后序遍历(必须做)
102.二叉树的层序遍历(必须做)
104.二叉树的最大深度(必须做)
199.二叉树的右视图
3.3.10 家庭作业+课后练习，选做不强制

111.二叉树的最小深度
101.对称二叉树
103.二叉树的锯齿形层序遍历
515.在每个树行中找最大值
429.N 叉树的层序遍历
3.4 经典排序算法

3.4.1 排序算法复杂度
3.4.2 排序算法编码实现落地说明
3.4.3 冒泡排序（Bubble Sort）

3.4.3.1 说明
3.4.3.2 动画
3.4.3.3 code
3.4.4 选择排序

3.4.4.1 说明
3.4.4.2 动画
3.4.4.3 code
3.4.5 快速排序
3.4.6 学有余力，面试资料(上课不讲)

3.4.6.1 插入排序
3.4.6.2 归并排序(MergeSort)
3.4.6.3 希尔排序
3.5 常见查找算法

3.5.1 顺序查找
3.5.2 二分查找

3.5.2.1 前提
3.5.2.2 半讲半练习
3.6 动态规划算法

3.6.1 说明
3.6.2 大厂面试题

322.零钱兑换
53.最大子数组和
300.最长递增子序列
120.三角形最小路径和
64.最小路径和
198.打家劫舍
3.6.3 能干嘛
3.6.4 入门
3.6.5 动态规划之LeetCode经典入门

**3.6.5.1 leecode70. 爬楼梯**

1、问题分析
2、推导过程分析
3、 code
3.6.5.2 心法小口诀
3.6.5.3 剑指 Offer 10- II. 青蛙跳台阶问题

1、问题分析
2、步骤
3、 All
3.6.5.4 动态规划思路总结
3.6.6 leetcode经典动态规划题目讲解

3.6.6.1 322. 零钱兑换

V1，递归穷举
V2，递归穷举+小本本，记下来避免低效和重复
V3，状态转移方程+DP
3.6.6.2 198.打家劫舍
3.6.6.3 最大子数组和
3.6.6.4 作业
4 总结

4.1 数据结构

4.2 ��法

1 课程介绍

1.1 前置知识

Java8

Java17

1.2 为什么要学习算法

为了求职面试，面试重灾区+大厂必考题
程序 = 数据结构 + 算法
求职面试难，继续卷出新高度
算法可以衡量程序员的技术功底
算法可以体现程序员的学习能力和成长潜力
学习算法有助于提高分析解决问题的能力

学习算法是做性能优化、成长为架构师的必经之路

1.3 大厂面试常见数据结构题目(基础)

数组
栈
队列
链表
树(二分搜索树)

堆

。。。

刷题地址：

力扣：https://leetcode.cn/

1.4 数据结构和算法的关系

程序 = 数据结构 + 算法

数据结构是算法的基础，好的算法也离不开数据结构

2 数据结构

2.1 数据结构概述

编程中遇到的问题：下图情形如何实现存档功能？

2.1.1 数据结构是什么

数据结构是为了高效访问数据而设计出的一种数据的组织和存储方式。更具体的说，一个数据结构包含一个数据元素的集合、数据元素之间的关系以及访问和操作数据的方法。

一般而言，数据结构针对的是内存中的数据。所以在学习数据结构之前，需要先对内存有一个简单的了解。

内存由许多存储单元组成，每个存储单元可以存储一个固定大小的数据块，通常以字节（Byte）为单位。每个存储单元都有一个唯一的地址，操作系统正是根据这一地址去访问内存中的数据的。我们讨论的数据结构中的数据元素就保存在这些一个个的内存单元中，这些数据元素或存储在连续的内存单元中，或存储在分散的内存单元中。

2.1.2 数据结构分类

2.1.2.1 线性结构

数据元素按照顺序排列，强调数据元素的前后或升降顺序

数组
链表
栈

队列

2.1.2.2 非线性结构

树

所有数据元素按照层次结构进行组织，强调元素之间的父子关系
图

由顶点和边组成，顶点对应数据元素，边连接两个顶点，表示两个数据元素之间的关系。图形结构用于表达元素之间复杂的网络关系

其它

二维数组

多维数组

…

2.1.2.3 小总结

2.1.3 数据结构范围

数组
栈
队列
链表
哈希表
树
堆

图

…

2.2 数组Array

2.2.1 基础知识

数组是具有相同类型的数据的集合，也就是说数组的所有元素的类型都是相同的，在所有的数据结构中，

数组算是最常见也是最简单的一种数据结构，我们最常见的也就是一维数组，当然还有二维，三维……，

数组需要先声明才能使用，数组的大小一旦确定就不可以再变了。比如我们声明一个长度为10的数组

int[] array = new int[10];

数组的下标是从零开始的，比如上面数组的第一个元素是array[0]，最后一个元素是array[9]。

2.2.2 数组优缺点

2.2.2.1 优点

查找快

使用下标位置索引(index)十分高效的访问任意元素，修改快

2.2.2.2 缺点

插入和删除操作开销大

说明

由于数组的内存连续性，插入和删除元素可能需要移动其他元素，导致开销较大。

特别是在数组的开头或中间插入/删除元素时，需要进行大量的数据搬移操作。

2.2.2.3 数组内存分配

引入依赖

    org.openjdk.jol    jol-core    0.17

测试：

public class Demo01 {    public static void main(String[] args) {        Object obj = new Object();        Object[] objs = new Object[5];        objs[0] = 1;        objs[1] = new Object();        int[] ints = new int[5];        long[] longs = new long[5];        //ClassLayout.parseInstance 用来查看对象内存布局        System.out.println(ClassLayout.parseInstance(obj).toPrintable());        System.out.println(ClassLayout.parseInstance(objs).toPrintable());        System.out.println(ClassLayout.parseInstance(ints).toPrintable());        System.out.println(ClassLayout.parseInstance(longs).toPrintable());    }}

java.lang.Object object internals:OFF  SZ   TYPE DESCRIPTION               VALUE  0   8        (object header: mark)     0x0000000000000001 (non-biasable; age: 0)  8   4        (object header: class)    0x00000d58 12   4        (object alignment gap)    Instance size: 16 bytesSpace losses: 0 bytes internal + 4 bytes external = 4 bytes total[Ljava.lang.Object; object internals:OFF  SZ               TYPE DESCRIPTION               VALUE  0   8                    (object header: mark)     0x0000000000000001 (non-biasable; age: 0) //对象头  8   4                    (object header: class)    0x00001528// ClassPointer指针 12   4                    (array length)            5 // 数组长度 16  20   java.lang.Object Object;.        N/A// 数组元素 36   4                    (object alignment gap)    // Padding对齐Instance size: 40 bytes// 对象总大小Space losses: 0 bytes internal + 4 bytes external = 4 bytes total[I object internals:OFF  SZ   TYPE DESCRIPTION               VALUE  0   8        (object header: mark)     0x0000000000000001 (non-biasable; age: 0)  8   4        (object header: class)    0x00006b18 12   4        (array length)            5 16  20    int [I.             N/A 36   4        (object alignment gap)    Instance size: 40 bytesSpace losses: 0 bytes internal + 4 bytes external = 4 bytes total[J object internals:OFF  SZ   TYPE DESCRIPTION               VALUE  0   8        (object header: mark)     0x0000000000000001 (non-biasable; age: 0)  8   4        (object header: class)    0x00001160 12   4        (array length)            5 16  40   long [J.             N/AInstance size: 56 bytesSpace losses: 0 bytes internal + 0 bytes external = 0 bytes total

**面试题：**ArrayList底层源码(扩容)

public static void main(String[] args) {    ArrayList list = new ArrayList();    //初始化：数组长度为0    System.out.println(ClassLayout.parseInstance(list).toPrintable());    //第一次添加元素时长度扩容到10    list.add(1);    System.out.println(ClassLayout.parseInstance(list).toPrintable());    for (int i = 2; i         list.add(i);    }    System.out.println(ClassLayout.parseInstance(list).toPrintable());    //长度超过10，添加元素触发扩容  原理：数组浅拷贝    list.add(11);    System.out.println(ClassLayout.parseInstance(list).toPrintable());}    public static void main(String[] args) {        int[] ints = new int[]{1, 2, 3, 4, 5};        for (int i = 0; i  2.2.3.2 架构设计一个通用数组
 考虑封装的思想
 2.2.3.4 普通版步骤V1

定义属性：int[] data，int size
初始化capacity容量

构造注入对数组进行初始化，主要是最大容量capacity赋值
简单的辅助，getSize+getCapacity+isEmpty+isFull

增

头增，往数组第一位置新增一个元素：addFirst(int e)
中增，指定索引下标位置，插入元素：add(int index,int e)
尾增，往数组最后新增一个元素：addLast(int e)

删

头删，往数组第一位置删除一个元素，并返回元素：removeFirst()
中删，指定索引下标位置，删除元素，并返回元素：remove(int index)
尾删，往数组最后删除一个元素，并返回元素：removeLast()
修改，按照下标index设置元素，并返回元素：set(int index,int e)
查询，按照下标index取得元素：get(int index)
包含，数组中是否包含某个元素：contain(int v)

输出

打印，按照正序打印：print()
逆印，按照逆序打印：printReverse()

code实例

package com.atguigu.study.datastruct.arrays;/** * V1版：增删改查含，扩缩正反印 */public class MyArray {    //1.定义属性    int[] data;    int size;    //2.构造对象    public MyArray() {        this(5);    }    public MyArray(int capacity) {        data = new int[capacity];        size = 0;    }    //3.基础函数    public int getSize() {        return size;    }    public int getCapacity() {        return data.length;    }    public boolean isEmpty() {        return size == 0;    }    public boolean isFull() {        return size == data.length;    }    //4.增    public void addFirst(int e) {        add(0, e);    }    public void add(int index, int e) {        if (isFull())            throw new RuntimeException("数组满了,不能增加元素;后面考虑扩容问题");        if (index  size) {            throw new RuntimeException("索引不在范围边界内");        }        for (int i = size - 1; i >= index; i--) {            data[i + 1] = data[i];        }        data[index] = e;        size++;    }    public void addLast(int e) {        add(size, e);    }    //5.删    public int removeFirst() {        return remove(0);    }    public int remove(int index) {        if (isEmpty()) {            throw new RuntimeException("数组为空，不能删除元素");        }        if (index = size) {            throw new RuntimeException("索引不在范围边界内");        }        int result = data[index]; //先获取要删除的索引对应的元素，方法返回        for (int i = index + 1; i  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index] = e;    }    //7.查    public int get(int index) {        if (index  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index];    }    //8.含    public boolean contain(int e) {        for (int i = 0; i = 0; i--) {            System.out.println("data[i] = " + data[i]);        }    }    //13.主方法测试    public static void main(String[] args) {        MyArray myArray = new MyArray();        myArray.addFirst(2);        myArray.add(1, 3);        myArray.add(2, 4);        myArray.addLast(77);        myArray.addLast(999);        myArray.print();        myArray.printReverse();        System.out.println();        System.out.println("removeFirst: " + myArray.removeFirst());        System.out.println("removeLast: " + myArray.removeLast());        myArray.print();        System.out.println("myArray.set: " + myArray.set(1, 1111));        myArray.print();        System.out.println("myArray.get(1): " + myArray.get(1));        System.out.println("myArray.contain(1111): " + myArray.contain(1111));        System.out.println("-----------------------------");        myArray.print();        System.out.println("-----------------------------");        myArray.printReverse();        System.out.println("-----为什么正向打印有两个999，反向打印无?，引出游离对象");    }}

2.3.4.5 泛型版步骤V2

内部封装好遍历整个数组对外暴露方法
泛型基础知识https://www.bilibili.com/video/BV1PY411e7J6?p=164

轻奢复习

泛型版MyArrayGeneric第2版

package com.atguigu.study.datastruct.arrays;/** * V2版(带泛型)：增删改查含，扩缩正反印 */public class MyArrayGeneric {    //1.定义属性    E[] data;    int size;    //2.构造对象    public MyArrayGeneric() {        this(5);    }    public MyArrayGeneric(int capacity) {        //data = new int[capacity];        data = (E[]) new Object[capacity];        size = 0;    }    //3.基础函数    public int getSize() {        return size;    }    public int getCapacity() {        return data.length;    }    public boolean isEmpty() {        return size == 0;    }    public boolean isFull() {        return size == data.length;    }    //4.增    public void addFirst(E e) {        add(0, e);    }    public void add(int index, E e) {        if (isFull())            throw new RuntimeException("数组满了,不能增加元素;后面考虑扩容问题");        if (index  size) {            throw new RuntimeException("索引不在范围边界内");        }        for (int i = size - 1; i >= index; i--) {            data[i + 1] = data[i];        }        data[index] = e;        size++;    }    public void addLast(E e) {        add(size, e);    }    //5.删    public E removeFirst() {        return remove(0);    }    public E remove(int index) {        if (isEmpty()) {            throw new RuntimeException("数组为空，不能删除元素");        }        if (index = size) {            throw new RuntimeException("索引不在范围边界内");        }        E result = data[index]; //先获取要删除的索引对应的元素，方法返回        for (int i = index + 1; i  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index] = e;    }    //7.查    public E get(int index) {        if (index  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index];    }    //8.含    public boolean contain(E e) {        for (int i = 0; i = 0; i--) {            System.out.println("data[i] = " + data[i]);        }    }    //13.主方法测试    public static void main(String[] args) {        MyArrayGeneric myArray = new MyArrayGeneric();        myArray.addFirst(2);        myArray.add(1, 3);        myArray.add(2, 4);        myArray.addLast(77);        myArray.addLast(999);        myArray.print();        myArray.printReverse();        System.out.println();        System.out.println("removeFirst: " + myArray.removeFirst());        System.out.println("removeLast: " + myArray.removeLast());        myArray.print();        System.out.println("myArray.set: " + myArray.set(1, 1111));        myArray.print();        System.out.println("myArray.get(1): " + myArray.get(1));        System.out.println("myArray.contain(1111): " + myArray.contain(1111));        System.out.println("-----------------------------");        myArray.print();        System.out.println("-----------------------------");        myArray.printReverse();        System.out.println("-----为什么正向打印有两个999，反向打印无?，引出游离对象");    }}

2.2.3.6 课堂练习，规范的定制化接口IMyArray

package com.atguigu.study.datastruct.arrays;public interface IMyArray {    //3.基础函数    int getSize();    int getCapacity();    boolean isEmpty();    boolean isFull();    void addFirst(E e);    void add(int index, E e);    public void resize(int newCapacity);    void addLast(E e);    //5.删    E removeFirst();    E remove(int index);    E removeLast();    //6.改    E set(int index, E e);    //7.查    E get(int index);    //8.含    boolean contain(E e);    //11.正打印    void print();    //12.反打印    void printReverse();}

3.4.7 (泛型版++)步骤V3(解决扩缩容)

扩容

缩容（可以不写）

对象游离(loitering)

定义：数组实现中有对象的引用，而我们并没有真正使用它，所以当减小N时，在数组中仍然有我们已经删除的对象的指针。

尽管程序员知道不再使用它了，但是Java系统JVM不知道

**解决：**最好将去除元素对应的项设为null，这样就不会剩下。

看看我们的remove方法，后续用，_

代码演示

package com.atguigu.study.datastruct.arrays;/** * V3版(带泛型++)：增删改查含，扩缩正反印 */public class MyArrayGenericPlus implements IMyArray {    //1.定义属性    E[] data;    int size;    //2.构造对象    public MyArrayGenericPlus() {        this(5);    }    public MyArrayGenericPlus(int capacity) {        //data = new int[capacity];        data = (E[]) new Object[capacity];        size = 0;    }    //3.基础函数    @Override    public int getSize() {        return size;    }    @Override    public int getCapacity() {        return data.length;    }    @Override    public boolean isEmpty() {        return size == 0;    }    @Override    public boolean isFull() {        return size == data.length;    }    //4.增    @Override    public void addFirst(E e) {        add(0, e);    }    /*    @Override    public void add(int index, E e) {        if (isFull())            throw new RuntimeException("数组满了,不能增加元素;后面考虑扩容问题");        if (index  size) {            throw new RuntimeException("索引不在范围边界内");        }        for (int i = size - 1; i >= index; i--) {            data[i + 1] = data[i];        }        data[index] = e;        size++;    }*/    @Override    public void add(int index, E e) {        if (isFull()) {            //---------扩容----------------------------            resize(getCapacity() * 2);        }        if (index  size) {            throw new RuntimeException("索引不在范围边界内");        }        for (int i = size - 1; i >= index; i--) {            data[i + 1] = data[i];        }        data[index] = e;        size++;    }    //---------扩容----------------------------    public void resize(int newCapacity) {        E[] newData = (E[]) new Object[newCapacity];        for (int i = 0; i = size) {            throw new RuntimeException("索引不在范围边界内");        }        E result = data[index]; //先获取要删除的索引对应的元素，方法返回        for (int i = index + 1; i  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index] = e;    }    //7.查    @Override    public E get(int index) {        if (index  size) {            throw new RuntimeException("索引不在边界范围");        }        return data[index];    }    //8.含    @Override    public boolean contain(E e) {        for (int i = 0; i = 0; i--) {            System.out.println("data[i] = " + data[i]);        }    }    //13.主方法测试    public static void main(String[] args) {        IMyArray myArray = new MyArrayGenericPlus();        myArray.addFirst(2);        myArray.add(1, 3);        myArray.add(2, 4);        myArray.addLast(77);        myArray.addLast(999);        myArray.print();        myArray.printReverse();        System.out.println();        System.out.println("removeFirst: " + myArray.removeFirst());        System.out.println("removeLast: " + myArray.removeLast());        myArray.print();        System.out.println("myArray.set: " + myArray.set(1, 1111));        myArray.print();        System.out.println("myArray.get(1): " + myArray.get(1));        System.out.println("myArray.contain(1111): " + myArray.contain(1111));        System.out.println("-----------------------------");        myArray.print();        System.out.println("-----------------------------");        myArray.printReverse();        System.out.println("-----为什么正向打印有两个999，反向打印无?，引出游离对象");    }}

问题

正确

2.2.4 leetcode数组练习经典题

反转字符串

https://leetcode.cn/problems/reverse-string/

package com.atguigu.study.datastruct.arrays;/** * https://leetcode.cn/problems/reverse-string/ *  * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 * 
 * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 */public class LeetCode344ReverseString {    public void reverseString(char[] s) {        int left = 0;        int right = s.length - 1;        while (left

图解说明

2.2.5 稀疏数组

回到2.1章节开始遇到的问题，如何完成棋盘的存档功能呢？

分析：我们可以将棋盘每个位置初始值为看做0，黑子值为1，蓝子值为2。存档时可以将所有的值按照顺序记录，读档时可以直接还原。

问题：棋盘没有下子的位置非常多，因此存了非常多没有意义的0

解决：稀疏数组

2.2.5.1 什么是稀疏数组

稀疏数组实际上是一个典型的二维数组，它描述的是一个标准二维数组的有效数据。

当一个数组中大部分元素为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组存储数据的方式是:

第一行记录数组一共有几行几列，有多少个非默认的值

其他行把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组只适合有效数据少，但是数组较大的情况。

2.2.5.2 实际应用

上图棋盘可以使用稀疏数组保存：

解释：

11(行数) 11(列数) 2(有效元素个数)1(行索引)      2(列索引)     1(值)      -- 第1个元素信息2(行索引)  3(列索引)     2(值)-- 第2个元素信息

2.2.5.3 代码

二维数组转稀疏数组

public class SparseArray {public static void main(String[] args) {// 创建一个原始的二维数组 11 * 11// 0: 表示没有棋子， 1 表示 黑子 2 表蓝子int chessArr1[][] = new int[11][11];chessArr1[1][2] = 1;chessArr1[2][3] = 2;chessArr1[4][5] = 2;// 输出原始的二维数组System.out.println("原始的二维数组~~");for (int[] row : chessArr1) {for (int data : row) {System.out.printf("%d\t", data);}System.out.println();}// 将二维数组 转 稀疏数组的思// 1. 先遍历二维数组 得到非0数据的个数int sum = 0;for (int i = 0; i  2.2.5.4 作业
 使用稀疏数组保存一下数据
  2.3 栈Stack
 2.3.1 基础知识
 2.3.1.1 先进后出/后进先出 最经典的案例-子弹弹夹
 栈也是一种特殊的线性表，他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作，他就好
 像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的
 时候不允许从中间放进去，拿书的时候也是先从最上面开始拿，不允许从下边或中间抽出来。
  2.3.1.2 是什么
  2.3.1.3 还有吗？
 数组的子集
 2.3.1.4 小口诀
 入栈addLast()+出栈removeLast()
 2.3.2 栈相关操作
 Push：压栈操作或入栈操作
 Pop：弹栈或出栈操作
 Peek：查看栈顶数据，但不出栈
 2.3.3 架构设计一个通用栈，考虑封装的思想
 2.3.3.1 判断条件

初容大于零
满了不能加

空了不能取

2.3.3.2 IStackDesc栈接口

package com.atguigu.study.datastruct.stack;public interface IStackDesc {    void push(E e);    E pop();    E peek();    int getSize();    boolean isFull();    boolean isEmpty();    void print();}

2.3.3.3 MyStack

package com.atguigu.study.datastruct.stack;public class MyStack implements IStackDesc {    E[] data;    int size;    public MyStack() {        this(5);    }    public MyStack(int capacity) {        if (capacity         if (isFull()) {            throw new IllegalArgumentException("栈满了");        }        data[size] = e;        size++;    }    @Override    public E pop() {        if (isEmpty())            throw new IllegalArgumentException("栈空了");        E result = data[size - 1];        size--;        data[size] = null;        return result;    }    @Override    public E peek() {        return data[size - 1];    }    @Override    public int getSize() {        return size;    }    @Override    public boolean isFull() {        return size == data.length;    }    @Override    public boolean isEmpty() {        return size == 0;    }    @Override    public void print() {        for (int i = 0; i = size) { //注意            throw new RuntimeException("索引不在有效边界");        }        Node currentNode = virtualHead.next;        for (int i = 0; i = size) throw new RuntimeException("索引不在有效边界");        Node currentNode = virtualHead.next;        for (int i = 0; i ");            curentNode = curentNode.next;        }        stringBuffer.append("NULL");        System.out.println("stringBuffer = " + stringBuffer.toString());    }        public void print2() {        StringBuffer stringBuffer = new StringBuffer();        //for (int i = 0; i ");        }        stringBuffer.append("NULL");        System.out.println(stringBuffer);    }    //测试    public static void main(String[] args) {        MyLinkedListV2 test = new MyLinkedListV2();        for (int i = 0; i  2.5.3.7 MyLinkedListV3-(删)

MyLinkedListV2+删

package com.atguigu.study.datastruct.linkedlists;/** * V2: 在V1上实现增加 、 改 查 含 印 测试 * V3: 实现删除 */public class MyLinkedListV3 {    ......            //删除    public E removeFirst() {        return remove(0);    }    public E remove(int index) {        if (index = size) {            throw new RuntimeException("索引不在边界内");        }        Node prev = virtualHead;        for (int i = 0; i  2.5.3.8 小总结
 链表推荐使用虚拟节点

增删取前置节点

public void add(int index,E e){    //省略判断    Node prev = virtualHead;    for (int i = 0; i  public E remove(int index){    //省略判断    Node prev = virtualHead;    for (int i = 0; i

改查取当前节点

public void set(int index,E e){    Node currentNode = virtualHead.next;    for (int i = 0; i  public E get(int index){    Node currentNode = virtualHead.next;    for (int i = 0; i  2.5.4 leetcode链表练习经典题，课堂练习
 2.5.4.1 反向遍历打印单链表
 https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/
 单链表先进后出打印，反转单链表会破坏链表结构，可以使用栈实现需求。
 在2.5.3.7章节中添加方向遍历打印单链表方法
 private void printReverse() {    if(head.next==null){        return;    }    //新建栈    MyStack stack = new MyStack(getSize());    Node current = head.next;    //链表所有节点入栈    while(current!=null){        stack.push(current);        current = current.next;    }//出栈并打印：先进后出    for (int i = 0; i  2.5.4.2 反转链表
 https://leetcode.cn/problems/reverse-linked-list/
 一句话：玩的就是指针

结果

图解说明

给同学们演示步骤，一步步来，细致讲解清楚

、

package com.atguigu.study.leetcode;/** * 反转链表 * https://leetcode.cn/problems/reverse-linked-list/ */public class LeetCode206ReverseLinkedList {    private static class ListNode {        public E e;        public ListNode next;        public ListNode() {            this(null, null);        }        public ListNode(E e) {            this(e, null);        }        public ListNode(E e, ListNode next) {            this.e = e;            this.next = next;        }        @Override        public String toString() {            return "ListNode{" +                    "e=" + e +                    '}';        }    }    /**     * 反转链表     */    public ListNode reverseListNode(ListNode head) {        //上一个节点        ListNode prevHead = null;        //正在遍历的节点        ListNode currentNode = head;        //缓存下一个节点        ListNode tempNode = null;        while (currentNode != null) {            //缓存下一个节点            tempNode = currentNode.next;            //设置正在遍历的节点的next指向上一个节点            currentNode.next = prevHead;            //接收当前节点：下一次遍历时使用            prevHead = currentNode;            //获取下一个遍历的节点            currentNode = tempNode;        }        //返回最后一个节点        return prevHead;    }    public static void print(ListNode head) {        while (head != null) {            System.out.print(head.e + "->");            head = head.next;        }        System.out.println("NULL");    }    public static void main(String[] args) {        LeetCode206ReverseLinkedList test = new LeetCode206ReverseLinkedList();        ListNode n4 = new ListNode(4, null);        ListNode n3 = new ListNode(3, n4);        ListNode n2 = new ListNode(2, n3);        ListNode n1 = new ListNode(1, n2);        ListNode head = n1;        print(head);        System.out.println(" =======反转========= ");        ListNode reverseHeadNode = test.reverseListNode(head);        print(reverseHeadNode);    }}

2.5.4.3 链表中倒数第k个节点

https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/

方法1：顺序查找

首先求出链表的长度 n，然后顺序遍历到链表的第 n−k个节点返回即可。

public static void main(String[] args) {    MyLinkedListV3 v3 = new MyLinkedListV3();    v3.add(0,1);    v3.add(0,2);    v3.add(0,3);    v3.add(0,4);    v3.add(0,5);    v3.add(0,6);    v3.add(0,7);    v3.print();    int n = v3.size;    int k = 1;    Node node = v3.head.next;    for (int i = 0; i  方法2：双指针(快慢指针)
 快慢指针的思想。
 第一个指针 fast 指向链表的第 k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针 fast走到链表的尾部空节点时，则此时slow 指针刚好指向链表的倒数第k个节点。
 public static void main(String[] args) {    MyLinkedListV3 v3 = new MyLinkedListV3();    v3.add(0,1);    v3.add(0,2);    v3.add(0,3);    v3.add(0,4);    v3.add(0,5);    v3.add(0,6);    v3.add(0,7);    v3.print();    //链表长度    int n = v3.size;    //查找倒数第几个节点    int k = 1;    //快指针    Node fast = node;    //慢指针    Node slow = node;    while(k!=0){        fast = fast.next;        k--;    }    while(fast!=null){        slow = slow.next;        fast = fast.next;    }    System.out.println(slow.data);}
 2.5.5 家庭作业，提交到leecode
 2.5.5.1 接口IStackDesc
 package com.atguigu.study.datastruct.linkedlists;public interface IStackDesc {    void push(E e);    E pop();    E peek();    int getSize();    boolean isEmpty();}
 2.5.5.2 链表模拟-栈

MyLinkedList4Stack

package com.atguigu.study.datastruct.linkedlists;/** * 链表模拟 - 栈    后进先出 */public class MyLinkedList4Stack implements IStackDesc {    MyLinkedListV3 linkedListV3;    public MyLinkedList4Stack() {        linkedListV3 = new MyLinkedListV3();    }    @Override    public void push(E e) {        linkedListV3.addFirst(e);    }    @Override    public E pop() {        return linkedListV3.removeFirst();    }    @Override    public E peek() {        return linkedListV3.getFirst();    }    @Override    public int getSize() {        return linkedListV3.getSize();    }    @Override    public boolean isEmpty() {        return linkedListV3.isEmpty();    }    @Override    public String toString() {        linkedListV3.print();        return super.toString();    }    public static void main(String[] args) {        MyLinkedList4Stack test = new MyLinkedList4Stack();        for (int i = 0; i  2.5.5.3 链表模拟-队列

MyLinkedList4Queue

package com.atguigu.study.datastruct.linkedlists;/** * 链表模拟 - 队列         先进先出 */public class MyLinkedList4Queue implements IQueueDesc {    private class Node {        public E e;        public Node next;                public Node() {            this(null, null);        }        public Node(E e) {            this(e, null);        }        public Node(E e, Node next) {            this.e = e;            this.next = next;        }        @Override        public String toString() {            return "Node{" + "e=" + e + '}';        }    }    private Node head;    private Node tail;    private int size;    public MyLinkedList4Queue() {        this.head = null;        this.tail = null;        this.size = 0;    }    @Override    public void enqueue(E e) {        if (null == tail) {            tail = new Node(e);            head = tail;        } else {            tail.next = new Node(e);            tail = tail.next;        }        size++;    }    @Override    public E dequeue() {        if (isEmpty()) {            throw new RuntimeException("队列为空,不能出队啦");        }        Node result = head;        head = result.next;        result.next = null;        if (head == null) {            tail = null;//如果head和tail都为null说明队列空了。        }        size--;        return result.e;    }    @Override    public E getFront() {        if (isEmpty()) {            throw new RuntimeException("空队列");        }        return head.e;    }    @Override    public int getSize() {        return size;    }    @Override    public boolean isEmpty() {        return size == 0;    }    @Override    public String toString() {        StringBuffer stringBuffer = new StringBuffer();        stringBuffer.append("head: ");        Node currentNode = head;        while (currentNode != null) {            stringBuffer.append(currentNode.e + "->");            currentNode = currentNode.next;        }        stringBuffer.append("null tail");        return stringBuffer.toString();    }    public static void main(String[] args) {        MyLinkedList4Queue test = new MyLinkedList4Queue();        for (int i = 1; i             test.enqueue(i);            System.out.println(test);            if (i % 3 == 2) {                test.dequeue();                System.out.println(test);                System.out.println();            }        }    }}    private class Node        Node            this.data = data;        }    }    //头节点    private Node        //初始化头尾节点        head = new Node        add(0,e);    }    public void addLast(E e){        add(size-1 , e);    }    public void add(int index, E e){        //        if(index            return;        }        //添加        Node            node = node.next;        }        //node的下一个为新元素        Node            nextNode.prev = newNode;            newNode.next = nextNode;        }        size++;    }    public E removeFirst(){        return remove(0);    }    public E removeLast(){        return remove(size-1);    }    public E remove(int index){        if(index            System.out.println("删除失败,索引越界");            return null;        }        if(head.next==null){            return null;        }        Node            delNode = delNode.next;        }        //要删除节点的上个节点        Node            prev.next = next;        }        if(next!=null){            next.prev = prev;        }        delNode.prev = null;        delNode.next = null;        size--;        return delNode.data;    }    public void print(){        Node            System.out.print(current.data+"\t");            current = current.next;        }        System.out.println();    }    public void printReverse(){        Node            System.out.print(current.data+"\t");            current = current.prev;        }        System.out.println();    }    public static void main(String[] args) {        MyDoubleLinkedList    public static void main(String[] args) {        //hashcode是通过hash函数对转为正数的对象物理地址计算得到的(在hash表中的位置)        System.out.println("AA".hashCode());        System.out.println("BB".hashCode());        System.out.println("----------------");        System.out.println("Aa".hashCode());        System.out.println("BB".hashCode());        System.out.println("----------------");        System.out.println("柳柴".hashCode());        System.out.println("柴柕".hashCode());        System.out.println("----------------");        System.out.println(new Object().hashCode());        System.out.println(new Object().hashCode());        System.out.println(new Object().hashCode());        System.out.println("----------------");        Set set = new HashSet();        int hashCodeValue;        //第10.5万次左右会出现hashCode冲突，每加1万差不多就多一次冲突。但不是固定的。        for (int i = 1; i             hashCodeValue = new Object().hashCode();            if (set.contains(hashCodeValue)) {                System.out.println("发生hash冲突，第" + i + "次，hashCodeValue " + hashCodeValue);                continue;            } else {                set.add(hashCodeValue);            }        }        System.out.println("size=" + set.size());    }}    //1.内嵌式形成我们KV键值对的Node节点    private static class Node        K key;        V value;        Node            this.key = key;            this.value = value;            this.next = next;        }        //链表内容展示形式为：[(k1:v1)-(k2:v2)-(k3:v3)-null]        @Override        public String toString() {            StringBuffer stringBuffer = new StringBuffer();            stringBuffer.append("[");            Node currentNode = this;            while (currentNode != null) {                stringBuffer.append("(").append(currentNode.key).append(":").append(currentNode.value).append(")->");                currentNode = currentNode.next;            }            stringBuffer.append("null]");            return stringBuffer.toString();        }    }    //2.Field + Constant    private static final int DEFAULT_INITIAL_CAPACITY = 1         this.array = new Node[DEFAULT_INITIAL_CAPACITY];        this.size = 0;    }    //4.基础操作    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    //5.增+改    public void put(K key, V value) {        //计算这个key的hash值，进入初始化16个大小的数组中        int index = hash(key, array.length);        System.out.println("index = " + index);        Node            if (currentNode.key.equals(key)) {                currentNode.value = value;                return;            }            currentNode = currentNode.next;        }//新建节点，并把原开始节点挂到自己的后面        Node DEFAULT_LOAD_FACTOR) {            grow();            System.out.println("扩容后容量 - array.length = " + array.length);        }    }    //6.删除    public V remove(K key) {        V result = null;        int index = hash(key, array.length);        Node currentNode = array[index];        if (currentNode == null) {            throw new RuntimeException(key + "对应的节点为空，无法删除");        }        //恰好第一个head节点        if (currentNode.key.equals(key)) {            result = currentNode.value;            array[index] = currentNode.next;            currentNode.next = null;            size--;        } else {            //从第2个节点开始遍历            Node prev = currentNode;            while (prev.next != null) {                if (prev.next.key.equals(key)) {                    Node deleteNode = prev.next;                    result = deleteNode.value;                    prev.next = prev.next.next;                    deleteNode.next = null; //help GC                    size--;                    break;                }                prev = prev.next;            }        }        return result;    }    //7.查    public V get(K key) {        int index = hash(key, array.length);        Node currentNode = array[index];        while (currentNode != null) {            if (currentNode.key.equals(key)) {                return currentNode.value;            }            currentNode = currentNode.next;        }        return null;    }    public V get2(K key) {        int index = hash(key, array.length);        for (Node currentNode = array[index]; currentNode != null; currentNode = currentNode.next) {            if (currentNode.key.equals(key)) {                return currentNode.value;            }        }        return null;    }    //自定义哈希函数，计算key对应的数组的索引值。    private int hash(K key, int length) {        //hashCode()方法的哈希值可能为负数        //与Integer.MAX_VALUE进行与操作可以保证是一个正数        //Integer.MAX_VALUE (0111 1111 1111 1111 1111 1111 1111 1111)        return (key.hashCode() & Integer.MAX_VALUE) % length;    }    //扩容    private void grow() {        Node[] newArray = new Node[array.length * 2];        for (int i = 0; i  2 = 9 - 7 *  * 所以返回 [0, 1] */public class LeetCode001TwoSum {    //暴力解法    /*public int[] twoSum(int[] nums,int target){        for (int i = 0; i  
3 算法
 3.1 算法概述
 3.1.1 算法是什么
 算法是一个用于解决特定问题的有限指令序列（计算可以执行的操作），可以取某个值或者值的集合作为输入并产生某个值或者值的集合作为输出。
 3.1.2 算法分类
 3.1.2.1 常见搜索算法

深度优先搜索

Depth-First Search，DFS：它从起始节点开始，沿着一条路径尽可能深入地探索，直到无法继续为止，然后回溯到前一节点，继续探索其他路径。这个过程一直持续到所有节点都被访问为止。

广度优先搜索

Breadth-First Search，BFS：它按照广度优先的顺序探索所有的顶点，即在移动到下一层级之前，先访问当前层级的所有顶点

3.1.2.2 常见排序算法

冒泡排序
选择排序
插入排序
快速排序
归并排序
堆排序
桶排序
基数排序
希尔排序
计数排序
位图排序

其它排序

3.1.2.3 常见查找算法

顺序查找
二分查找
插值查找
斐波那契查找
分块查找
哈希查找

其它查找

3.1.2.4 常见实现策略算法

暴力破解
增量
分治
动态规划
贪心算法

递归

3.2.3 如何评价一个算法的好坏

一个算法的好坏是通过【时间复杂度】与【空间复杂度】来衡量

简单来说

所花的时间与占用内存便是衡量一个算法好坏的标准

时间复杂度

就是执行算法的时间成本

空间复杂度

就是执行算法的内存空间成本

3.2.4 高中数学：对数函数vs指数函数复习

3.2.4.1 补充说明

在描述算法复杂度时，经常用到O(1)， O(n)， O(logn)， O(nlogn)来表示对应算法的时间复杂度，这是算法的时间复杂度的表示。

O后面的括号中有一个函数，指明某个算法的耗时与数据增长量之间的关系。其中的n代表输入数据的量。

O(n)：代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。

O(logn)：当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

O(nlogn)：n乘以logn，当数据增大256倍时，耗时增256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。

O(1)：最低的时空复杂度，也就是耗时与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

3.2.5 复杂度的大欧O(X)表示法

时间复杂度与空间复杂度都是用 “大O” 来表示(大欧表示法)，写作 O(*)

由于目前内存便宜，此刻我们谈论复杂度

一般谈论的都是时间复杂度

时间复杂度BigO，大欧表示法

量级增加时，时间增长的趋势。

常见时间复杂度的 “大O表示法” 描述有以下几种

3.2.6 常见时间复杂度

**面试题：**常见时间复杂度举例

常数阶O(1)

无复杂的循环结构，代码每次执行，时间复杂度都是O（1）

package com.atguigu.study.bigo;/** * O(1) * 常数阶 */public class T0 {    /**     * 无复杂的循环结构，不论代码多少行，每次执行，时间复杂度都是O(1)     */    public void compute() {        int i = 1;        int j = 1;        i++;        j++;        int temp;        temp = i + j;        System.out.println("temp = " + temp);    }    public static void main(String[] args) {        new T0().compute();    }}

对数阶O(logN)

package com.atguigu.study.bigo;/** * 对数阶  O(logN) * 从排序的数组中查找到目标 */public class T1 {    public static void main(String[] args) {        int[] arrays = new int[]{1, 11, 22, 33, 77, 99, 103, 108}; //length = 8      index  0~7        int target = 77;        int index = binarySearch(arrays, target);        System.out.println("index = " + index);    }    public static int binarySearch(int[] arraySorted, int target) {        int left = 0;        int right = arraySorted.length - 1;        while (left             int middle = left + (right - left) / 2;            if (arraySorted[middle] == target) {                return middle;            } else if (arraySorted[middle]  target) { // 要找的在左侧                right = middle - 1;            } else if (arraySorted[middle]

线性阶O(N)

package com.atguigu.study.bigo;/** * O(n)  线性阶 * 对所有的数据都执行一遍 */public class T2 {    public static void main(String[] args) {        circle(5);    }    private static void circle(int n) { //执行n次,n的值越大,时间越长        for (int j = 0; j

线性对数阶O(nlogN)

package com.atguigu.study.bigo;/** * 线性对数阶：O(NlogN) * 将一个复杂度O(logN)的的代码执行N次，那么，此时复杂度就是O(NlogN) */public class T3 {    public static void main(String[] args) {        logArithmetic(5);    }    private static void logArithmetic(int n) {        for (int i = 0; i  3.2.3.2 阶乘

学术定义

一个正整数的阶乘（英语：factorial）是所有小于及等于该数的正整数的积且有零的阶乘为1。自然数n的阶乘写作n!。亦即n!=1×2×3×…×n。

阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

请计算5的阶乘

    //先往下一层层传递，当碰到终止条件的时候会反弹，最终会反弹到起始调用处    public static int f5(int i) {        return i * f4(i - 1);    }    public static int f4(int i) {        return i * f3(i - 1);    }    public static int f3(int i) {        return i * f2(i - 1);    }    public static int f2(int i) {        return i * f1();    }    public static int f1() {        return 1;    }

小口诀：递推+回归

普通阶乘

package com.atguigu.study.algorithm.recursion;import java.math.BigInteger;/** * 一个正整数的阶乘（英语：factorial）是所有小于及等于该数的正整数的积且有零的阶乘为1。自然数n的阶乘写作n!。 *  * 亦即n!=1×2×3×...×n。 * 
 * 阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。 * 
 * 
 * 0! = 1 * 1! = 1 * 2! = 2 * 3! = 6 * 4! = 24 * 5! = 120 * 6! = 720 * 7! = 5040 * 8! = 40320 * 9! = 362880 * 10! = 3628800 */public class FactorialGeneralDemo {    public static int factorialNumber(int i) {        if (i             return i * factorialNumber(i - 1);        }    }    //Integer.MAX_VALUE = 2147483647,因此，当超过这个值时，int类型的阶乘就会变成负数。    //int类型的最大值是2147483647,最小值是-2147483648。    public static void main(String[] args) {        System.out.println(factorialNumber(12));//13? long 21?    }}    //如果number // 返回-1表示number小，0表示等于1        return BigInteger.ONE;    }    return number        .multiply(factorialBigNumber(number.subtract(BigInteger.ONE)));}public static void main(String[] args) {    System.out.println(factorialBigNumberCount(new BigInteger("12")));}

h43.2.4 小总结/h4 ulli p将复杂的大问题拆分多个较小的问题/p /lili p对诸多较小的问题进行总结归纳，形成相互独立且与原问题性质相同/p /lili p通过求子问题解的形式解决原问题/p h33.3 二叉搜索树BST/h3 h43.3.1 先来看看面试题/h4 ol start="144"li p二叉树的前序遍历(必须做)/p p遍历顺序：根节点 - 左孩子 - 右孩子/p /li/ol phttps://leetcode.cn/problems/binary-tree-preorder-traversal//p ol start="94"li p二叉树的中序遍历(必须做)/p p遍历顺序：左孩子-> 根节点 -> 右孩子

https://leetcode.cn/problems/binary-tree-inorder-traversal/

二叉树的后序遍历(必须做)

遍历顺序：左孩子-> 右孩子 -> 根节点

https://leetcode.cn/problems/binary-tree-postorder-traversal/

二叉树的层序遍历

遍历顺序：每一层从左向右

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

二叉树的右视图

https://leetcode-cn.com/problems/binary-tree-right-side-view/

找出每一层最右边的TreeNode

3.3.2 树(Tree)

树（Tree）由一系列具有层次关系的节点（Node）组成

树的相关术语

3.3.3 二叉搜索树(Binary Search Tree)基础知识

3.3.4 架构设计一个二叉搜索树(Binary Search Tree)

3.3.4.1 二叉树编码操作基本功 (套路+模板)

树特点

左小右大，你如何安放和比较？

两个比较接口：java.lang.Comparable、java.util.Comparator

再看看Integer用的哪一个？复习一下Comparable接口使用

package com.atguigu.study.datastruct.trees;public class ComparableDemo {    public static void main(String[] args) {        Node node1 = new Node(11);        Node node2 = new Node(11);        int result = node1.compareTo(node2);        System.out.println("result = " + result);    }}class Node implements Comparable {    int number;    public Node(int number) {        this.number = number;    }    @Override    public int compareTo(Node anNode) {//森        if (this.number > anNode.number) {            return 1;        } else if (this.number

口诀

数组找下标index
链表找头部head

二叉树找根root

3.3.4.2 第1版BSTV1(初始化+增)

定义TreeNode

初始化+增

package com.atguigu.study.datastruct.trees;/** * 第一版 */public class BSTV1 {    //1.内嵌式的封装树的子节点类    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    //2.field    private Node root;    private int size;    //3.constructor    public BSTV1() {        this.root = null;        this.size = 0;    }    //4.基础操作    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    //5.add    /**     * 实现原理：     * 1.无根新建,第一个node建立，此时root=null;如果是空的root就指向第一次新建的node     * 【有根新增】     * 2.同值退出，第一次Node建立，第二次还是同样值，和root冲突，直接退出     * 3.左叶/右叶节点为空，首次挂载，第一次挂左叶/右叶节点；     * 4.左叶/右叶节点不空,已经有了，需要遍历到左叶/右叶节点为空，枝繁叶茂     */    public void add(E e) {        if (null == this.root) {            this.root = new Node(e); //无根新建            size++;        } else {            add(this.root, e);        }    }    public void add(Node node, E inputValue) {        if (inputValue.compareTo(node.e) == 0) { //同值不加            return;        } else if (inputValue.compareTo(node.e)  0 && node.right == null) { //值大右空加右            node.right = new Node(inputValue);            size++;            return;        }        if (inputValue.compareTo(node.e)  0) {//值大右不空继续找            add(node.right, inputValue);        }    }    public static void main(String[] args) {        BSTV1 bstv1 = new BSTV1();        bstv1.add(5);        bstv1.add(7);        bstv1.add(1);        bstv1.add(2);        bstv1.add(2);        System.out.println("bstv1.size = " + bstv1.size);    }}

V1版本有啥问题？

如何优化？

只要node==null必然会new一个节点并size++，不是root就是叶子

3.3.4.3 第2版BSTV2(改进增+查)

BSTV2以Root为根基，初始化并开始插入节点形成树，V2要求递归有TreeNode返回

小口诀

**起步先判空，左右叶根加； **

递归左右移，return树形成

增V2+(查)

package com.atguigu.study.datastruct.trees;/** * 改进添加：+  含 * 添加+查询(含) */public class BSTV2 {    //1.内嵌式的封装树节点类    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    //2.field    Node root;    int size;    //3.contructor    public BSTV2() {        this.root = null;        this.size = 0;    }    //4.基础操作    public int getSize() {        return this.size;    }    public boolean isEmpty() {        return this.size == 0;    }    //5.add    //BSTV2版本以root为根，初始化并开始插入节点形成树，递归有返回    public void add(E inputValue) {        this.root = add(this.root, inputValue);    }//分析： 10 5 20 5 8 3 30 15    private Node add(Node node, E inputValue) {        if (null == node) { //根或叶子            size++;            return new Node(inputValue);        }        if (inputValue.compareTo(node.e) > 0) {            node.right = add(node.right, inputValue);        } else if (inputValue.compareTo(node.e)  0) {            return contain(node.right, e);        } else {            return true;        }    }    public static void main(String[] args) {        BSTV2 bstv2 = new BSTV2();        bstv2.add(5);        bstv2.add(3);        bstv2.add(4);        bstv2.add(8);        bstv2.add(4);        bstv2.add(2);        System.out.println("bstv2 = " + bstv2);        System.out.println("bstv2.get(4) = " + bstv2.get(9));    }}

3.3.4.4 修改不用考虑，想想为啥？

3.3.4.5 第3版BSTV3(V2+印【递归版】(前中后)+测试)

V2+印+测试

二叉树递归遍历

前序：根-左-右

先序遍历的操作过程如下：

1、如果二叉树为空树，则什么都不做；否则：

2、访问根结点。

3、先序遍历左子树。

4、先序遍历右子树。

中序：左-根-右

中序遍历的操作过程如下：

1、如果二叉树为空树，则什么都不做；否则：

2、中序遍历左子树。

3、访问根结点。

4、中序遍历右子树。

后序：左-右-根

后序遍历的操作过程如下：

1、如果二叉树为空树，则什么都不做；否则：

2、后序遍历左子树。

3、后序遍历右子树。

4、访问根结点。

小结：

三种遍历算法，都属于递归遍历。

其中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。

不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是 O(n)。

package com.atguigu.study.datastruct.trees;/** * 添加 + 含 + 印（前序+中序+后序）+ 测试 * 前序：根-左-右 * 中序：左-根-右 * 后序：左-右-根 */public class BSTV3 {    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    private Node root;    private int size;    public BSTV3() {        this.root = null;        this.size = 0;    }    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    public void add(E e) {        root = add(root, e);    }    private Node add(Node node, E e) {        if (null == node) {            size++;            return new Node(e);        }        if (e.compareTo(node.e) > 0) {            node.right = add(node.right, e);        } else if (e.compareTo(node.e)  0) {            return contain(node.right, e);        } else if (e.compareTo(node.e)  标配+前中后三种序
 3.3.4.6 上面二叉树递归遍历的问题，请谈谈

问题本质描述

在使用递归的时候，我们会在函数的某一部分，重复的调用某个函数自身，

直到触发终止条件时，递归才会停止，进而函数才会执行完毕。

递归可能会产生问题

如果终止条件有问题，那么递归将无法停止

如果递归无法停止，函数会不断的调用自身，抛出StackOverflowError异常

public static void main(String[] args) {    BSTV3 bstv3 = new BSTV3();    for (int i = 0; i

优化方法

限制递归次数

对于“限制递归次数”来说，就是在调用函数的时候，同时传入一个数字 N 作为递归的次数，

当递归次数大于 N 的时候，强制结束递归并返回结果，以实现二叉树的中序遍历为例。

    public List inorder(TreeNode root, int level) {        List ans = new ArrayList();        helper(root, ans, level);        return ans;    }     private void helper(TreeNode root, List ans, int level) {        if (level >= 0) {            if (root != null) {                if (root.left != null) {                    helper(root.left, ans, level - 1);                }                ans.add(root.val);                if (root.right != null) {                    helper(root.right, ans, level - 1);                }            }        }    }  //限制递归次数的方法是有瑕疵的，治标不治本，假如有5层，我只递归调用4层，防止击穿了但是得不到最终结果。

借助堆/栈将递归转化为非递归

小总结

递归的表达性很好，也很容易理解，不过如果层级过深，很容易导致栈溢出。

所以我们需要了解--------->非递归实现

3.3.5 深度优先 VS 广度优先

3.3.5.1 二叉树【非递归】遍历之DFS

非递归实现——栈

深度优先遍历DFS(Depth First Search深度优先搜索)

二叉树案例前序遍历（先遍历根节点，再遍历左节点，再遍历右节点）

1 对每个节点来说，先遍历当前节点，然后把右节点压栈，再压左节点(这样弹栈的时候会先拿到左节点遍历，符合深度优先遍历要求)

2 弹栈，拿到栈顶的节点，如果节点不为空，重复步骤 1，如果为空，结束遍历。

用栈来实现非递归DFS(Depth First Search深度优先搜索)动画演示

用栈来实现非递归DFS(Depth FirstSearch深度优先搜索)编码实战

前序：根-左-右，非递归算法

    /**     * 前序：根-左-右遍历以node为根的二分搜索树，非递归方式     */    public void preOrderWithOutRecursion() {        Stack stack = new Stack();        stack.push(root);        while (!stack.isEmpty()) {            Node curentNode = stack.pop();            System.out.println(curentNode.e);            if (curentNode.right != null) {                stack.push(curentNode.right);            }            if (curentNode.left != null) {                stack.push(curentNode.left);            }        }    }

上课不讲，家庭作业

中序：左-根-右，非递归算法

    /**     * 中序：左-根-右遍历以node为根的二分搜索树，非递归方式     */    public void midOrderWithOutRecursion() {        Stack stack = new Stack();        Node currentNode = root;        while (currentNode != null || !stack.isEmpty()) {            while (currentNode != null) {                stack.push(currentNode);                currentNode = currentNode.left;            }            currentNode = stack.pop();            System.out.print(currentNode.e + " ");            currentNode = currentNode.right;        }    }

后序：左-右-根，非递归算法

    /**     * 后序：左-右-根遍历以node为根的二分搜索树，非递归方式     243865     栈中存储顺序：[5 6 8 3 4 2]     */    public void postOrderWithOutRecursion() {        Stack stack = new Stack();        stack.push(root);        Stack stackTemp = new Stack();        while (!stack.isEmpty()) {            Node currentNode = stack.pop();            stackTemp.push(currentNode);            if (currentNode.left != null) {                stack.push(currentNode.left);            }            if (currentNode.right != null) {                stack.push(currentNode.right);            }        }        while (!stackTemp.isEmpty()) {            Node currentNode = stackTemp.pop();            System.out.print(currentNode.e + " ");        }    }

代码参考AllCode——非递归

package com.atguigu.study.datastruct.trees;import java.util.Stack;/** * 添加 + 含 + 印（前序+中序+后序）+ 测试 * 前序：根-左-右 * 中序：左-根-右 * 后序：左-右-根 */public class BSTV4NotRecursionDFS {    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    private Node root;    private int size;    public BSTV4NotRecursionDFS() {        this.root = null;        this.size = 0;    }    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    public void add(E e) {        root = add(root, e);    }    private Node add(Node node, E e) {        if (null == node) {            size++;            return new Node(e);        }        if (e.compareTo(node.e) > 0) {            node.right = add(node.right, e);        } else if (e.compareTo(node.e)  0) {            return contain(node.right, e);        } else if (e.compareTo(node.e)  3.3.5.2 二叉树【非递归】遍历之BFS
 BFS(Breadth First Search广度优先搜索)
 广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。动图如下，每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历，
 先遍历第一层（节点 1），
 再遍历第二层（节点 2，3，4），
 第三层（5，6，7，8），
 第四层（9，10）。
  定义
 按照层的概念进行搜索算法并利用Queue记录需要被展开的TreeNode
 广度优先遍历用的是队列
 //BSF按照层进行遍历public void levelOrder() {    Queue queue = new LinkedList();    queue.add(root);    while (!queue.isEmpty()) {        Node currentNode = queue.remove();        System.out.print(currentNode.e + " ");        if (currentNode.left != null) {            queue.add(currentNode.left);        }        if (currentNode.right != null) {            queue.add(currentNode.right);        }    }}
 3.3.5.3 DFS+BFS小总结
 DFS深度优先遍历用的是=====栈
 BFS广度优先遍历用的是=====队列
 3.3.6 架构设计一个二叉搜索树(Binary Search Tree)，二次优化++
 3.3.6.1 寻找二分搜索树的最小元素、删除最小元素
 package com.atguigu.study.datastruct.trees;public class BSTSearchMinMaxDemo {    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    private Node root;    private int size;    public BSTSearchMinMaxDemo() {        root = null;        size = 0;    }    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    public void add(E e) {        root = add(root, e);    }    private Node add(Node node, E inputVal) {        if (null == node) {            size++;            return new Node(inputVal);        } else if (inputVal.compareTo(node.e)  0) {            node.right = add(node.right, inputVal);        } else {            return node;        }        return node;    }    public void preOrder() {        preOrder(root);    }    private void preOrder(Node node) {        if (null == node) return;        System.out.print(node.e + " ");        preOrder(node.left);        preOrder(node.right);    }    //从root开始找到树的最小节点并返回值    public E getMinNode() {        if (isEmpty()) {            throw new RuntimeException("树为空,无法查找");        }        return getMinNode(root).e;    }    private Node getMinNode(Node node) {        if (node.left == null) {            return node;        } else {            return getMinNode(node.left);        }    }    public E removeMinNode() {        E minValue = getMinNode();        root = removeMinNode(root);//2.删最小后返回        return minValue;//1.最小节点即删除节点，数据返回    }    private Node removeMinNode(Node node) {        /*         * 根据左小右大建立的二叉树： 最左边叶子节点才是最小节点，才能删除         *  2种情况：         *      最小节点没有右节点，右节点为null         *      最小节点有右节点，         */        if (node.left == null) {            Node deleteNode_rightNode = node.right;            node.right = null;            size--;            return deleteNode_rightNode;        }        node.left = removeMinNode(node.left);        return node;    }    //使用双指针实现删除最小节点    public Node removeMinNode2(Node node){        Node prevNode = node;        while(node.left!=null){            prevNode = node;            node = node.left;        }        prevNode.left = node.right;        return node;    }        /    //      5      //    //    /   \    //    //   3    6    //    //  / \    \   //    // 2  4     8  //    /    public static void main(String[] args) {        BSTSearchMinMaxDemo test = new BSTSearchMinMaxDemo();        test.add(5);        test.add(3);        test.add(6);        test.add(8);        test.add(4);        //test.add(2);        test.preOrder();        System.out.println();        System.out.println("getMinNode: " + test.getMinNode());        System.out.println();        System.out.println("removeMinNode: " + test.removeMinNode());        test.preOrder();        System.out.println();    }}
 3.3.6.2 家庭作业、找最大元素，删最大元素
 public E getMaxNode() {    if (getSize() == 0) {        throw new RuntimeException("空树无效");    }    return getMaxNode(root).e;}public Node getMaxNode(Node node) {    if (node.right == null) {        return node;    } else {        return getMaxNode(node.right);    }}public E removeMaxNode() {    E maxValue = getMaxNode();    root = removeMaxNode(root);    return maxValue;}private Node removeMaxNode(Node node) {    if (node.right == null) {        Node deleteNode_leftNode = node.left;        node.left = null;        size--;        return deleteNode_leftNode;    }    node.right = removeMaxNode(node.right);    return node;}
 3.3.6.3 删除二分搜索树的任意元素理论
  450.删除二叉搜索树中的节点
 https://leetcode.cn/problems/delete-node-in-a-bst/
 
 难在哪里？？？
 删除某个节点后需要重新翻转构建一颗新树并填补以前空白
 理论支撑Hibbard
 Hibbard在1964年发表的论文，题目是《A New Kind of Data Structure for Operations on Trees》。这篇论文中，Hibbard介绍了二叉树的基本概念和操作，例如插入、删除和查找。他还提出了一些关于二叉树的重要结论，例如平衡二叉树的高度和直径之和之间的关系。
 
 待删除节点，只有左子树
 
  待删除节点，只有右子树
  
 待删除节点，两边都有树(Hibbard delete)
  理论支撑Hibbard delete
 理论说明
 问题：左右都有子树，需要找一个节点替代被删除的节点，如何找寻？
 
  删除节点，被删节点右子树中所对应的最小节点，用该最小节点替换被删除节点并形成新的树。
  一句话：待删除节点两边都有子树的话，右找最小的 或 左找最大的替代并上位。

全树全景

上位图示

结果

中序遍历

提起来是树，往下压是链表

3.3.6.4 删除任意节点实操BSTRemoveNodeDemo

package com.atguigu.study.datastruct.trees;public class BSTRemoveNodeDemo {    private class Node {        E e;        Node left;        Node right;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    private Node root;    private int size;    private BSTRemoveNodeDemo() {        root = null;        size = 0;    }    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    public void add(E e) {        root = add(root, e);    }    private Node add(Node node, E e) {        if (node == null) {            size++;            return new Node(e);//不是root就是叶子        }        if (e.compareTo(node.e) > 0) { //右加            node.right = add(node.right, e);        } else if (e.compareTo(node.e)  0) {//当前节点不是要删除的节点            //递归查找右子树删除，返回新上位的节点            node.right = remove(node.right, e);            return node;        } else if (e.compareTo(node.e)  3.3.7 LeetCode课堂练习
 226. 翻转二叉树
 https://leetcode.cn/problems/invert-binary-tree/
 package com.atguigu.study.leetcode;/** * 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; * } * } */public class Leetcode226InvertTree {    private static class TreeNode {        int val;        TreeNode left;        TreeNode right;        public TreeNode() {        }        public TreeNode(int val) {            this.val = val;        }        public TreeNode(int val, TreeNode left, TreeNode right) {            this.val = val;            this.left = left;            this.right = right;        }    }    public static TreeNode invertTree(TreeNode root) {        if (root == null) {            return null;        }        TreeNode leftNode = invertTree(root.left);        TreeNode rightNode = invertTree(root.right);        TreeNode tempNode = leftNode;        root.left = rightNode;        root.right = tempNode;        return root;    }        /    //      5      //    //    /   \    //    //   3    6    //    //  / \    \   //    // 2  4     8  //    /    /    //      5      //    //    /   \    //    //   6    3    //    //  /    / \   //    // 8    4   2  //    /    public static void main(String[] args) {        TreeNode root = new TreeNode(5);        root.left = new TreeNode(3);        root.left.left = new TreeNode(2);        root.left.right = new TreeNode(4);        root.right = new TreeNode(6);        root.right.right = new TreeNode(8);        preOrder(root);        System.out.println();        root = invertTree(root);        System.out.println();        preOrder(root);        System.out.println();    }    private static void preOrder(TreeNode root) {        if (root == null) {            return;        }        System.out.print(root.val + " ");        preOrder(root.left);        preOrder(root.right);    }}
 破题——递归+交换铁三角
  3.3.8 递归+非递归+DFS+BFS全家福大总结(家庭作业)
 TreeAllSummaryDemo
 package com.atguigu.study.datastruct.trees;import java.util.*;import java.util.concurrent.atomic.AtomicInteger;public class TreeAllSummaryDemo {    //1.定义内嵌式封装树的内部类    private class TreeNode {        Integer val;        TreeNode left;        TreeNode right;        public TreeNode() {        }        public TreeNode(Integer val) {            this.val = val;        }        public TreeNode(Integer val, TreeNode left, TreeNode right) {            this.val = val;            this.left = left;            this.right = right;        }    }    //2.field    private TreeNode root;    //3.添加    public void add(Integer val) {        root = add(root, val);    }    private TreeNode add(TreeNode treeNode, Integer val) {        if (treeNode == null) {            return new TreeNode(val);        }        if (val.compareTo(treeNode.val) > 0) {            treeNode.right = add(treeNode.right, val);        } else if (val.compareTo(treeNode.val)  3.3.9 LeetCode(家庭作业)
 144.二叉树的前序遍历(必须做)
 https://leetcode.cn/problems/binary-tree-preorder-traversal/
 94.二叉树的中序遍历(必须做)
 https://leetcode.cn/problems/binary-tree-inorder-traversal/
 145.二叉树的后序遍历(必须做)
 https://leetcode.cn/problems/binary-tree-postorder-traversal/
 102.二叉树的层序遍历(必须做)
 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
  //二叉树的层次遍历public List levelOrder(TreeNode root) {    //2.定义返回的结果，每一层从左到右封装成List，然后，将所有的层存放到ArrayList集合中。    List result = new ArrayList();    //1.如果节点为null则返回null    if (root == null) {        return null;    }    //3.临时队列    Queue queue = new LinkedList();    queue.offer(root); //在尾部添加元素，add()添加失败(队列已满)时会报运行时错误，而offer()在添加失败时会返回false    while (!queue.isEmpty()) {        //队列长度，根据队列长度处理每一层数据。        int currentLevelsize = queue.size();        List currentLevel = new ArrayList(); //存放每一个层的数据集合        //处理当前层的同时，将其下一层元素入队。        for (int i = 0; i  104.二叉树的最大深度(必须做)
 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
  //二叉树的最大深度public int maxDepth(TreeNode root) {    //如果树空，最大深度为0    if (root == null) {        return 0;    }    //定义整数值，初始化为0，用来记录树的深度    AtomicInteger maxDepth = new AtomicInteger(0);    Queue queue = new LinkedList();    queue.add(root);    while (!queue.isEmpty()) {        int currentLevelSize = queue.size();        //一次处理一层        for (int i = 0; i  199.二叉树的右视图
 https://leetcode-cn.com/problems/binary-tree-right-side-view/
 找出每一层最右边的TreeNode
      //二叉树的右视图    public List rightSideView(TreeNode root) {        //存放右视图节点数据。        List result = new ArrayList();        //树为空返回空        if (null == root) return result;        //定义临时队列，队列长度在迭代过程中可变        Queue queue = new LinkedList();        queue.offer(root);        while (!queue.isEmpty()) {            int currentLevelSize = queue.size();            result.add(queue.peek().val); //从队列中取头节点的值存放到列表中，暂不删除            for (int i = 0; i  3.3.10 家庭作业+课后练习，选做不强制
 111.二叉树的最小深度
 https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 101.对称二叉树
 https://leetcode-cn.com/problems/symmetric-tree/
 103.二叉树的锯齿形层序遍历
 https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
 515.在每个树行中找最大值
 https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
 429.N 叉树的层序遍历
 https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
 3.4 经典排序算法
 3.4.1 排序算法复杂度

n	数据规模个数
k	桶的个数
In-place	不占用额外内存
Out-place	占用额外内存，有额外内存成本

3.4.2 排序算法编码实现落地说明

3.4.3 冒泡排序（Bubble Sort）

3.4.3.1 说明

首先，拿第一个元素和后面的所有元素一个个两两比较，如果比后面的大就交换，所以始终会保证第一个元素是最小的;

然后，再从第二个第三个和后面的所有元素一个个两两比较，因为越小的元素会经由交换慢慢“浮”到数列的顶端，以此类推。

3.4.3.2 动画

3.4.3.3 code

package com.atguigu.study.algorithm.sort;/** * 冒泡排序（Bubble Sort） * 首先 * 拿第一个元素和后面的所有元素一个个两两比较，如果比后面的大就交换，所以始终会保证第一个元素是最小的; * 然后 * 再从第二个第三个和后面的所有元素一个个两两比较，因为越小的元素会经由交换慢慢“浮”到数列的顶端，以此类推。 */public class BubbleSort {    public static void main(String[] args) {        int[] sort = sort(new int[]{61, 17, 29, 34, 1});        for (int i = 0; i  ints[j + 1]) {//如果前一个元素大于后一个元素，则交换它们的位置                    int temp = ints[j];                    ints[j] = ints[j + 1];                    ints[j + 1] = temp;                }            }        }        return ints;    }}

3.4.4 选择排序

3.4.4.1 说明

是什么

选择排序和冒泡排序有一点点像(不是冒泡那样相邻两两比较)，

选择排序是默认前面队伍都是已经排序好的，然后从后面选择最小的放在前面已经排好序数组的后面。

步骤

首先第一轮循环的时候默认的排序好的数组为空，然后从后面选择最小的放到数组的第一个位置；

第二轮循环的时候默认第一个元素是已经排序好的，然后从剩下的找出最小的放到数组的第二个位置，

第三轮循环的时候默认前两个都是已经排序好的，然后再从剩下的选择一个最小的放到数组的第三个位置，以此类推。

算法描述：

N个记录的直接选择排序可经过(N-1)趟直接选择排序得到有序结果。具体算法描述如下：

3.4.4.2 动画

3.4.4.3 code

package com.atguigu.study.algorithm.sort;/** * 选择排序 * 选择排序和冒泡排序有一点点像(不是冒泡那样相邻两两比较)， * 选择排序是默认前面队伍都是已经排序好的，然后从后面选择最小的放在前面已经排好序数组的后面。 * 步骤： * 首先第一轮循环的时候默认的排序好的数组为空，然后从后面选择最小的放到数组的第一个位置； * 第二轮循环的时候默认第一个元素是已经排序好的，然后从剩下的找出最小的放到数组的第二个位置， * 第三轮循环的时候默认前两个都是已经排序好的，然后再从剩下的选择一个最小的放到数组的第三个位置，以此类推。 */public class SelectSort {    public static void main(String[] args) {        int[] nums = new int[]{93, 1, 5, 4, 2, 99};        nums = selectSort(nums);        for (int i = 0; i  3.4.5 快速排序

说明

动画

code

package com.atguigu.study.algorithm.sort;/** * 快排 */public class QuickSort {    public static int[] sort(int[] array) {        sort(array, 0, array.length - 1);        return array;    }    /**     * 对数组中的指定区域进行排序     *     * @param array 待排序数组     * @param start 待排序区间起点     * @param end   待排序区间重点     */    private static void sort(int[] array, int start, int end) {        //待排序区间长度为1，则直接返回        if (start >= end) {            return;        }        //移动基础元素到正确位置，并返回该元素        int pivotIndex = partition(array, start, end);        //对基准元素左侧区间进行排序        sort(array, start, pivotIndex - 1);        //对基准元素右侧区间进行排序        sort(array, pivotIndex + 1, end);    }    /**     * @param array 待排序数组     * @param start 待排序区间起点     * @param end   待排序区间终点     * @return 基准元素最终位置     */    private static int partition(int[] array, int start, int end) {        //选择待排序区间第一个元素作为基准元素，将其值保存到临时变量        int pivot = array[start];        //low从左向右移动        int low = start;        //high从右向左移动        int high = end;        while (low = pivot) {                high--;            }            array[low] = array[high];            while (low  current) {                nums[preIndex + 1] = nums[preIndex];                preIndex--;            }            nums[preIndex + 1] = current;        }        for (int element : nums) {            System.out.print(element + " ");        }    }    public static void main(String[] args) {        insertSort(new int[]{93, 1, 5, 4, 2, 99});    }}

3.4.6.2 归并排序(MergeSort)

说明
指的是将两个已经排好序的列表合并成一个有序列表的操作
- 概述
  - 原理
    - 动画

上一篇：蚂蚁英文发音宝典，轻松掌握蚂蚁的正确读音解析

下一篇：网站的资讯栏目怎么设置?

行业知识

数据结构与算法(数组,栈,队列,链表,哈希表,搜索算法,排序算法,查找算法,策略算法,递归算法,二叉搜索树BST,动态规划算法)

文章目录

1 课程介绍

1.1 前置知识

1.2 为什么要学习算法

1.3 大厂面试常见数据结构题目(基础)

1.4 数据结构和算法的关系

2 数据结构

2.1 数据结构概述

2.1.1 数据结构是什么

2.1.2 数据结构分类

2.1.2.1 线性结构

2.1.2.2 非线性结构

2.1.2.3 小总结

2.1.3 数据结构范围

2.2 数组Array

2.2.1 基础知识

2.2.2 数组优缺点

2.2.2.1 优点

2.2.2.2 缺点

2.2.2.3 数组内存分配

2.2.3.2 架构设计一个通用数组

2.2.3.4 普通版步骤V1

2.3.4.5 泛型版步骤V2

2.2.3.6 课堂练习，规范的定制化接口IMyArray

3.4.7 (泛型版++)步骤V3(解决扩缩容)

2.2.4 leetcode数组练习经典题

2.2.5 稀疏数组

2.2.5.1 什么是稀疏数组

2.2.5.2 实际应用

2.2.5.3 代码

2.2.5.4 作业

2.3 栈Stack

2.3.1 基础知识

2.3.1.1 先进后出/后进先出 最经典的案例-子弹弹夹

2.3.1.2 是什么

2.3.1.3 还有吗？

2.3.1.4 小口诀

2.3.2 栈相关操作

2.3.3 架构设计一个通用栈，考虑封装的思想

2.3.3.1 判断条件

2.3.3.2 IStackDesc栈接口

2.3.3.3 MyStack

2.5.3.7 MyLinkedListV3-(删)

2.5.3.8 小总结

2.5.4 leetcode链表练习经典题，课堂练习

2.5.4.1 反向遍历打印单链表

2.5.4.2 反转链表

2.5.4.3 链表中倒数第k个节点

2.5.5 家庭作业，提交到leecode

2.5.5.1 接口IStackDesc

2.5.5.2 链表模拟-栈

2.5.5.3 链表模拟-队列

3 算法

3.1 算法概述

3.1.1 算法是什么

3.1.2 算法分类

3.1.2.1 常见搜索算法

3.1.2.2 常见排序算法

3.1.2.3 常见查找算法

3.1.2.4 常见实现策略算法

3.2.3 如何评价一个算法的好坏

3.2.4 高中数学：对数函数vs指数函数复习

3.2.4.1 补充说明

3.2.5 复杂度的大欧O(X)表示法

3.2.6 常见时间复杂度

3.2.3.2 阶乘

普通阶乘

3.3.2 树(Tree)

3.3.3 二叉搜索树(Binary Search Tree)基础知识

3.3.4 架构设计一个二叉搜索树(Binary Search Tree)

3.3.4.1 二叉树编码操作基本功 (套路+模板)

3.3.4.2 第1版BSTV1(初始化+增)

3.3.4.3 第2版BSTV2(改进增+查)

3.3.4.4 修改不用考虑，想想为啥？

3.3.4.5 第3版BSTV3(V2+印【递归版】(前中后)+测试)

3.3.4.6 上面二叉树递归遍历的问题，请谈谈

3.3.5 深度优先 VS 广度优先

3.3.5.1 二叉树【非递归】遍历之DFS

2.3.1.1 先进后出/后进先出最经典的案例-子弹弹夹