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

行业知识

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

2026-11-02 04:35:31 来源：互联网转载

文章目录

Java全端课程之数据结构和算法

一、开篇闲聊

1.1 前置知识
1.2 为什么要学习算法
1.3 算法-大厂面试的必备主菜
1.4 刷题标准
1.5 大厂面试常见数据结构题目(基础)
1.6 学习算法好处
二、数据结构和算法概述

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 算法概述

2.2.1 算法是什么
2.2.2 算法分类

2.2.2.1 常见搜索算法
2.2.2.2 常见排序算法
2.2.2.3 常见查找算法
2.2.2.4 常见实现策略算法
2.2.3 如何评价一个算法的好坏
2.2.4 高中数学：对数函数vs指数函数复习

2.2.4.1 补充说明
2.2.5 复杂度的大欧O(X)表示法
2.2.6 为什么你学习算法比较难？

2.2.6.1 常见时间复杂度
三、数组Array

3.1 基础知识
3.2 筑牢基础，课前ArrayList源码浅谈
3.3 数组优缺点

3.3.1 优点
3.3.2 缺点
3.4 架构设计一个通用数组，考虑封装的思想

3.4.1 约定变量
3.4.2 热身课堂小练习，正序+反序打印数组
3.4.3 小口诀
3.4.4 普通版步骤V1
3.4.5 泛型版步骤V2
3.4.6 课堂练习，规范的定制化接口IMyArray
3.4.7 (泛型版++)步骤V3(解决扩缩容)

扩容
缩容（可以不写）
对象游离(loitering)
3.5 leetcode数组练习经典题
四、栈Stack

4.1 基础知识

4.1.1 先进后出/后进先出最经典的案例-子弹弹夹
4.1.2 是什么
4.1.3 还有吗？
4.1.4 小口诀
4.2 栈相关操作
4.3 架构设计一个通用栈,考虑封装的思想

4.3.1 判断条件
4.3.2 IStackDesc栈接口
4.3.3 MyStack
4.3.4 对象游离(loitering)
五、队列Queue

5.1 基础知识

5.1.1 先进先出最经典的案例-排队打饭
5.1.2 是什么
5.1.3 还有吗？
5.1.4 小口诀
5.2 架构设计一个队列，考虑封装问题

5.2.1 判断
5.2.2 队列接口IQueueDesc
5.2.3 MyQueue
六、链表

6.1 基础知识

6.1.1 最经典的案例-火车挂车厢
6.1.2 是什么
6.2 链表优缺点

6.2.1 优点
6.2.2 缺点
6.3 架构设计一个单链表，考虑的封装问题

6.3.1 如何构造Node节点？
6.3.2 初始化定义：MyLinkedListV1
6.3.4 第1版MyLinkedListV1增(过渡版本)
6.3.5 增(改进版本)
6.3.6 第2版MyLinkedListV2(改、查、含印、测试)
6.3.7 第3版MyLinkedListV3(删除)
6.3.8 小总结
6.4 leetcode链表练习经典题，课堂练习

206. 反转链表
6.5 家庭作业，做完并上传到自己Gitee账号

6.5.1 接口IStackDesc
6.5.2 链表模拟-栈
6.5.3 链表模拟-队列[底层也可以直接用前面的列表]
6.5.4 有效的括号:基于栈实现
七、哈希表

7.1 基础知识

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

7.5.1 数据结构说明
7.5.2 MyHashTable
7.6 leetcode哈希表练习经典题(课堂练习or家庭作业)

7.6.1 力扣第一题:两数之和

暴力法
哈希(更优解法)
All-idea
八、递归算法

8.1 基础知识

8.1.1 是什么?何为递归?
8.1.2 关键一句话
8.1.3 构成递归需具备的2个条件
8.1.4 能干嘛
8.2 递归编码的基本功(套路+模板)

8.2.1 没有退出机制，栈溢出
8.2.2 课堂小练习
8.3 递归经典案例

8.3.1 斐波那契数列
8.3.2 阶乘

普通阶乘
大数阶乘
8.4 小总结
九、二叉搜索树BST

9.1 先来看看面试题
9.2 树(Tree)

9.2.1 层次
9.2.2 宽度
9.2.3 深度
9.2.4 高度
9.3 二叉搜索树(Binary Search Tree)基础知识
9.4 架构设计一个二叉搜索树(Binary Search Tree)

9.4.1 二叉树编码操作基本功 (套路+模板)
9.4.2 第1版BSTV1(初始化+增)
9.4.3 第2版BSTV2(改进增+查)
9.4.4 第3版BSTV3(V2+印(前中后)+测试)
9.4.5 上面二叉树递归遍历的问题，请谈谈
9.5 深度优先 VS 广度优先

9.5.1 二叉树非递归遍历之DFS

前序：根-左-右遍历以node为根的二分搜索树, 非递归算法
中序：左-根-右遍历以node为根的二分搜索树, 非递归算法
后序：左-右-根，遍历以node为根的二分搜索树, 非递归算法
代码参考AllCode——非递归
9.5.2 二叉树非递归遍历之BFS
9.5.3 DFS+BFS小总结
9.6 架构设计一个二叉搜索树(Binary Search Tree)，二次优化++

9.6.1 寻找二分搜索树的最小元素或者最大元素

9.6.2.1 家庭作业、找最大，删最大
9.6.2 删除二分搜索树的任意元素

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

226. 翻转二叉树

破题——递归+交换铁三角
9.8 递归+非递归+DFS+BFS全家福大总结(家庭作业)
9.9 LeetCode(家庭作业)
9.10 家庭作业+课后练习，选做不强制
十、经典排序算法

10.1 排序算法复杂度
10.2 排序算法编码实现落地说明
10.3 冒泡排序（Bubble Sort）

10.3.1 说明
10.3.2 动画
10.3.3 code
10.4 选择排序

10.4.1 说明
10.4.2 动画
10.4.3 code
10.5 其它常见排序算法

10.5.2 插入排序
10.5.3 归并排序(MergeSort)
10.5.4 快速排序
10.6 分治思想(算法)

10.6.1 介绍
10.6.2 分治算法的步骤
10.6.3 分治算法练习-最大子数组和（力扣#53题）
十一、常见查找算法

11.1 顺序查找
11.2 二分查找

11.2.1 前提
11.2.2 半讲半练习
十二、动态规划算法

12.1 说明
12.2 能干嘛
12.3 动态规划之LeetCode70经典入门（70. 爬楼梯）

12.3.1 问题分析
12.3.2 推导过程分析
12.3.3 code
12.4 心法小口诀
12.5 剑指 Offer 10- II. 青蛙跳台阶问题

12.5.1 问题分析
12.5.2 步骤
12.5.3 All
12.5.4 动态规划思路初识
12.6 课堂练习
12.7 leetcode刷题，家庭作业，上课不讲

12.7.1 322. 零钱兑换

V1，递归穷举
V2，递归穷举+小本本，记下来避免低效和重复
V3，状态转移方程+DP
12.7.2 其它作业题
十三、串讲和总结复习

13.1 数据结构

13.2 ��法

Java全端课程之数据结构和算法

一、开篇闲聊

1.1 前置知识

Java8

Java17

1.2 为什么要学习算法

为了求职面试，面试重灾区+大厂必考题
程序 = 数据结构 + 算法

求职面试难，继续卷出新高度

1.3 算法-大厂面试的必备主菜

算法可以衡量程序员的技术功底
算法可以体现程序员的学习能力和成长潜力
学习算法有助于提高分析解决问题的能力

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

1.4 刷题标准

力扣：https://leetcode.cn/

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

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

堆

。。。

1.6 学习算法好处

考研必考，是学习的纽带
与算法有关的产品，竞争力都比较大
与算法有关的岗位，薪资和晋升潜力都比较大

转型大数据和AI，数据结构和算法常识也会让你更容易转型

二、数据结构和算法概述

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 算法概述

2.2.1 算法是什么

举个栗子，如何获得8这个结果？

算法是一个用于解决特定问题的有限指令序列（计算可以执行的操作）。

2.2.2 算法分类

2.2.2.1 常见搜索算法

深度优先搜索

广度优先搜索

2.2.2.2 常见排序算法

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

其它排序

2.2.2.3 常见查找算法

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

其它查找

2.2.2.4 常见实现策略算法

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

递归

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

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

简单来说

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

时间复杂度:统计：

就是执行算法的时间成本。两种统计方式：1、事后统计法[机器性能、数据规模] 2.大O计数法:反映随着数据规模不断增大，反映时间变化趋势的统计方式！

空间复杂度

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

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

逆运算

2.2.4.1 补充说明

O（n）是指：随着数据规模n的变化，反映算法耗时趋势的统计方式。

在描述算法复杂度时，经常用到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)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）

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

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

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

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

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

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

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

2.2.6 为什么你学习算法比较难？

基本功不扎实，只刷题不看母题+了解本质

2.2.6.1 常见时间复杂度

常数阶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++; t        j++; t        int temp;t        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 = 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();        //todo:这里没必要提游离对象，直接设置为空即可。        System.out.println("-----为什么正向打印有两个999，反向打印无?，引出游离对象");    }}

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，反向打印无?，引出游离对象");    }}

3.4.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，反向打印无?，引出游离对象");    }}

问题

正确

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，反向打印无?，引出游离对象");    }}

3.5 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

图解说明

四、栈Stack

4.1 基础知识

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

栈也是一种特殊的线性表，他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作，他就好

像我们把书一本本的摞起来，最先放的书肯定是摞在下边，最后放的书肯定是摞在了最上面，摞的

时候不允许从中间放进去，拿书的时候也是先从最上面开始拿，不允许从下边或中间抽出来。

4.1.2 是什么

4.1.3 还有吗？

数组的子集

4.1.4 小口诀

入栈addLast()+出栈removeLast()

4.2 栈相关操作

Push：压栈操作或入栈操作

Pop：弹栈或出栈操作

Peek：查看栈顶数据，但不出栈

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

4.3.1 判断条件

初容大于零
满了不能加

空了不能取

4.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();}

4.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  6.3.7 第3版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  6.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  6.4 leetcode链表练习经典题，课堂练习
 206. 反转链表
 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 reverseHead = null;        ListNode currentNode = head;        ListNode tempNode = null;                while (currentNode != null) {            tempNode = currentNode.next;            currentNode.next = reverseHead;            reverseHead = currentNode;            currentNode = tempNode;        }        return reverseHead;    }    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);    }}

6.5 家庭作业，做完并上传到自己Gitee账号

6.5.1 接口IStackDesc

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

6.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  6.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;    //1.初始化    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为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();            }        }    }}    //判断传进来的字符串，是否是有效字符串    public boolean isValid(String str){        Stack            char character = str.charAt(i);            //如果是左括号,则入栈            if (character == '(' || character == '{'|| character == '[' ){                stack.push(character);            }else {                if (stack.isEmpty()){                    return false; //栈为空，直接结束                }                //如果不是左括号，则出栈                Character popCharacter = stack.pop();                if (character == ')'){                    if (popCharacter != '('){ //只有不符合的时候才返回false,否则继续进入下次循环，进行下个字符匹配                        return false;                    }                }else if (character == '}'){                    if (popCharacter != '{'){                        return false;                    }                }else if (character == ']'){                    if (popCharacter != '['){                        return false;                    }                }            }        }       return stack.isEmpty(); //如果只有左边括号，也返回false    }    public static void main(String[] args) {        ValidParenthesesApplication validSolutionApplication=new ValidParenthesesApplication();          String str="(){}}{";         boolean isValid=validSolutionApplication.isValid(str)        System.out.println(isValid);    }}    public static void main(String[] args) {        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;        //第11万会出现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 {            //从第一个节点开始遍历            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;    }//    public static void main(String[] args) {//        long userId = 56800004874L;//        System.out.println(String.valueOf(userId).hashCode() );//        //   输出：-2082984168(hashcode值为负数)//    }    //扩容    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  
八、递归算法
 8.1 基础知识
 8.1.1 是什么?何为递归?
 递归就是有退出机制的自己调自己函数(方法)，直至求出结果的算法。
 其思路是把一个大问题转化为规模缩小了的子问题，通过解决小问题来解决最终的大问题。
 8.1.2 关键一句话

递归递归，自己调用自己递推+回归，终止退出必须有

8.1.3 构成递归需具备的2个条件

递归表达式(规律)

子问题须与原始问题为同样的事且更为简单

递归出口(终结递归的条件)

不能无限制地调用本身，须有个出口，化简为非递归状况处理

8.1.4 能干嘛

就是不断调用自己，最终求得结果的算法
体现了分而治之的思想
递推+回归的运行顺序

明确的退出条件

8.2 递归编码的基本功(套路+模板)

8.2.1 没有退出机制，栈溢出

8.2.2 课堂小练习

传统写法： for循环求和1+2+3+4+…+5

package com.atguigu.study.algorithm.recursion;public class RecursionSumDemo {    /**     * 传统写法,for循环，求和：1+2+3+4+...+10     */    public static int sumArray(int[] array) {        int result = 0;        for (int i = 0; i  递归改写： for循环求和1+2+3+4+…+5
 递归和循环的关系：循环都可以改写成递归，递归未必能改写成循环 这是一个充分不必要的条件
     /**     * 递归写法，求和：1+2+3+4+...+10     */    public static int sumRecursion(int number) {        if (number == 1) {            return 1;        } else {            return number + sumRecursion(number - 1);        }    }//    public static int sumRecursion(int number){//        return 5 + sumRecursion(4);//    }////    public static int sumRecursion(int number){//        return 4 + sumRecursion(3);//    }////    public static int sumRecursion(int number){//        return 3 + sumRecursion(2);//    }////    public static int sumRecursion(int number){//        return 2 + sumRecursion(1);//    }////    public static int sumRecursion(int number){//        return 1//    }
 8.3 递归经典案例
 8.3.1 斐波那契数列

学术定义

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……

特别指出：第零项是零，第1项是第一个1。

这个数列从第三项开始，每一项都等于前两项之和。

package com.atguigu.study.algorithm.recursion;/** * 斐波那契数列指的是这样一个数列 0,  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377...... * 特别指出：第零项是零，第1项是第一个1，这个数列从第三项开始，每一项都等于前两项之和。 * 在数学上，斐波那契数列以如下被以递推的方法定义： * F(0)=0，F(1)=1, * F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*） */public class FibonacciDemo {    public static int fib(int i) {        if (i == 0) {            return 0;        }        if (i == 1 || i == 2) {            return 1;        }        if (i > 2) {            return fib(i - 1) + fib(i - 2);        }        return -1;    }    public static void main(String[] args) {        System.out.println("fib(5) = " + fib(13));    }}

8.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) = " + factorialNumber(12));//13? long 21?    }}        if (number.intValue()             return BigInteger.ONE;        } else {            return number.multiply(factorialBigNumberCount(number.subtract(BigInteger.ONE)));        }    }    public static void main(String[] args) {        System.out.println("factorialBigNumberCount(new BigInteger(\"5\")) = " + factorialBigNumberCount(new BigInteger("19")));    }    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  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就是叶子

9.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);    }    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 if (e.compareTo(node.e)  9.4.4 第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)  标配+前中后三种序
 9.4.5 上面二叉树递归遍历的问题，请谈谈

问题本质描述

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

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

递归可能会产生问题

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

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

优化方法

限制递归次数

对于“限制递归次数”来说，就是在调用函数的时候，同时传入一个数字 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层，防止击穿了但是得不到最终结果。

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

小总结

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

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

9.5 深度优先 VS 广度优先

9.5.1 二叉树非递归遍历之DFS

非递归实现——栈

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

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

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

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

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

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

前序：根-左-右遍历以node为根的二分搜索树, 非递归算法

    /**     * 前序：根-左-右遍历以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为根的二分搜索树, 非递归算法

    /**     * 中序：左-根-右遍历以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为根的二分搜索树, 非递归算法

    /**     * 后序：左-右-根遍历以node为根的二分搜索树，非递归方式     */    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)  9.5.2 二叉树非递归遍历之BFS
 BFS(Breadth First Search广度优先搜索)
 广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。动图如下，每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历，
 先遍历第一层（节点 1），
 再遍历第二层（节点 2，3，4），
 第三层（5，6，7，8），
 第四层（9，10）。
  定义
 按照层的概念进行搜索算法并利用Queue记录需要被展开的TreeNode
 广度优先遍历用的是队列
 模板套路code
 package com.atguigu.study.datastruct.trees;import java.util.LinkedList;import java.util.Queue;public class BFSDemo {    private class Node {        E e;        Node left = null;        Node right = null;        public Node(E e) {            this.e = e;            this.left = null;            this.right = null;        }    }    private Node root;    private int size;    public BFSDemo() {        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 (null == node) {            size++;            return new Node(e);        } else if (e.compareTo(node.e) > 0) {            node.right = add(node.right, e);        } else if (e.compareTo(node.e)  9.5.3 DFS+BFS小总结
 DFS深度优先遍历用的是=====栈
 BFS广度优先遍历用的是=====队列
 9.6 架构设计一个二叉搜索树(Binary Search Tree)，二次优化++
 9.6.1 寻找二分搜索树的最小元素或者最大元素
 也称找最大或者最小叶子节点 BSTSearchMinMaxDemo
 code找到最小，删除最小
 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 (getSize() == 0) {            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);        return minValue;    }    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;    }    /    //      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();    }}
 9.6.2.1 家庭作业、找最大，删最大
     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;    }
 9.6.2 删除二分搜索树的任意元素
  450.删除二叉搜索树中的节点
 https://leetcode.cn/problems/delete-node-in-a-bst/
 
 难在哪里？？？
 删除某个节点后需要重新翻转构建一颗新树并填补以前空白
 理论支撑Hibbard
 
 待删除节点，只有左子树
  
 待删除节点，只有右子树
  
 待删除节点，两边都有树(Hibbard delete)
  理论支撑Hibbard delete
 理论说明
 问题：左右都有子树，需要找一个节点替代被删除的节点，如何找寻？
 
  删除节点，被删节点右子树中所对应的最小节点，用该最小节点替换被删除节点并形成新的树。
  一句话：待删除节点两边都有子树的话，右找最小的 或 左找最大的替代并上位。

全树全景

上位图示

结果

中序遍历

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

9.6.3 删除任意节点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)  9.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;    }    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);    }}
 破题——递归+交换铁三角
  9.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)  9.9 LeetCode(家庭作业)
 二叉树的前序遍历(必须做)
https://leetcode.cn/problems/binary-tree-preorder-traversal/
 二叉树的中序遍历(必须做)
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/
      //二叉树的层次遍历    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  二叉树的最大深度(必须做)
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  二叉树的右视图
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  9.10 家庭作业+课后练习，选做不强制
 二叉树的最小深度
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
 对称二叉树
https://leetcode-cn.com/problems/symmetric-tree/
 二叉树的锯齿形层序遍历
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
 在每个树行中找最大值
https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row/
 N 叉树的层序遍历
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
 十、经典排序算法
 10.1 排序算法复杂度

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

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

10.3 冒泡排序（Bubble Sort）

10.3.1 说明

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

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

10.3.2 动画

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

10.4 选择排序

10.4.1 说明

是什么

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

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

步骤

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

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

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

算法描述：

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

10.4.2 动画

10.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  10.5 其它常见排序算法
 10.5.1 快速排序

说明

动画

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

10.5.3 归并排序(MergeSort)

说明

指的是将两个已经排好序的列表合并成一个有序列表的操作

归并排序用到了：分治+递归的思想。

概述

原理

动画

package com.atguigu.study.algorithm.sort;public class MergeSort {    public static void sort(int[] nums) {        sort(nums, 0, nums.length - 1);        for (int element : nums) {            System.out.print(element+" ");        }    }    /**     * 对数组中的指定区间进行排序     *     * @param nums  待排序数组     * @param start 待排序区间起点     * @param end   待排序区间终点     */    public static void sort(int[] nums, int start, int end) {        //若待排序区间长度为1,则直接返回，递归出口，结束递归。        if (start >= end) {            return;        }        //计算待排序区间的中间位置索引        int mid = (start + end) / 2;        //对左边一半进行递归拆分，并排序        sort(nums, start, mid);        //对右边一半进行递归拆分，并排序        sort(nums, mid + 1, end);        //对两边数组进行合并        merge(nums, start, mid, end);    }    /**     * 对指定数组的两部分进行合并，两部分分别是[start,mid]和[mid+1,end]     *     * @param nums  待合并数组     * @param start 起点     * @param mid   中点     * @param end   终点     */    public static void merge(int[] nums, int start, int mid, int end) {        //创建临时数组        int[] result = new int[end - start + 1];        //i为第一部分起点，j为第二部分起点，k为临时数组索引        int i = start, j = mid + 1, k = 0;        //从两部分的起点开始比较，直到一个部分到达终点        while (i             if (nums[i]

上一篇：菲律宾电商怎么注册?

下一篇：爱思服务器怎么用?