chapter5. Java数据结构与java算法

数据结构包括：线性结构和非线性结构。
1线性结构

1. 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
   一对一e.g. a[0] = 3;
2. 线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。
   顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
3. 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息（链表可以充分利用碎片内存）
4. 线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解.

2非线性结构
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

1. 加入队列时，需要将尾指针往后移：先判断 front == rear （队列是否为空，是否满↓）-> rear+1 ,
2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。
   rear == maxSize -1(队列满）

加入队列和删除代码：
！注意！
因为先进先出的特点，不管是增加值到队列还是删除，front和rear都是先++，再增/删。

优化：数组模拟环形队列

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含 data 域， next 域：指向下一个节点.
3. 如图：发现链表的各个节点不一定是连续存储.
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

增+查：

2. 添加时考虑顺序，根据排名插入到指定位置；若排名存在，则添加失败。

改：根据某个元素，找到指定节点，并修改其部分内容。
思路(1) 先找到该节点，通过遍历，(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

**我的题解 - LeetCode 删除单链表的值：

https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/shan-chu-lian-biao-de-zhi-by-duo-bi-e-fvvx/**

面试题：

1. 求单链表中有效节点的个数（如果是带头结点的链表，需求不统计头节点)

   1. 判断链表是否为空
   2. 定义辅助变流len
   3. 遍历时不包括head while len++

2. 查找单链表中的倒数第 k 个结点 【新浪面试题】

**我的题解 - 返回倒数第k个结点到最后的链表 （剑指offer 第22题）：

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/fan-hui-dao-shu-di-kge-jie-dian-dao-zui-pyh5b/**

3. 单链表的反转【腾讯面试题，有点难度】
   1 定义一个结点 reverseHead() = new ListNode()
   2 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，放入新的链表reverseHead的最前端
   3 原来的链表的head.next = reverseHead.next

**我的题解 - 链表翻转 LeetCode 24：

管理单向链表的缺点分析:

1. 单向链表，查找的方向只能是一个方向（需要一个一个遍历），而双向链表可以向前或者向后查找。
2. 单向链表不能自我删除，需要找到前一个节点（辅助节点）才能删除。 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).

分析双向链表的格式、 如何完成遍历，添加，修改和删除的思路
格式：单链表 + pre[指向前一个节点]

分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现

1. 遍历 方和 单链表一样，只是可以向前，也可以向后查找

2. 添加 (默认添加到双向链表的最后)
   (1) 先找到双向链表的最后的节点（即next=null）
   //2.3.形成一个双向链接
   (2) temp.next = newHeronode （指向后一个节点）
   (3) newHeroNode.pre = temp; （指向前一个节点）

3. 修改 思路和 原来的单向链表一样.

4. 删除
   (1) 因为是双向链表，因此，我们可以实现自我删除某个节点
   (2) 直接找到要删除的这个节点，比如 temp
   //3.4.形成一个双向链接
   (3) temp.pre.next = temp.next
   if（temp.next != null){
   (4) temp.next.pre = temp.pre; （如果是最后一个结点，就不需要执行此代码）
   }

Josephu 问题为：
设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
 提示
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束

栈的介绍：

栈（stack）

1. 栈是一个先入后出(FILO-First In Last Out)的有序列表。
2. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的
   一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
3. 根据栈的定义可知，最先放入栈中元素在栈底(入栈(push))，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元
   素最先删除(出栈(pop))，最先放入的元素最后删除

栈的应用场景

1. 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以
   回到原来的程序中。
2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆
   栈中。
3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4. 二叉树的遍历。
5. 图形的深度优先(depth 一 first)搜索法。

实现栈的思路

1. 使用数组来模拟栈
2. 定义一个 top 来表示栈顶，初始化 为 -1
3. 入栈的操作，当有数据加入到栈时， top++; stack[top] = data;
4. 出栈的操作， int value = stack[top]; top–, return value
5. 遍历：从栈顶开始遍历, for(int i = top; i>0; i–)

栈实现综合计算器：中缀表达式

前缀（波兰式）、中缀：运算符在操作数之间、后缀表达式（后波兰式）

前缀（波兰式）：从右向左扫描表达式
中缀：需要判断运算符的优先级，对机算计并不方便。
后缀表达式（后波兰式）：一般中缀会转为后缀，后缀最易操作
从左向右扫描表达式

中缀表达式转后缀表达式

具体步骤如下:

1. 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压 s2；
4. 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
   1.如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
   2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
   3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较；
5. 遇到括号时：
   (1) 如果是左括号“(”，则直接压入 s1
   (2) 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤 2 至 5，直到表达式的最右边
7. 将 s1 中剩余的运算符依次弹出并压入 s2
8. 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

举例说明:
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
因此结果为 :“1 2 3 + 4 × + 5 –”

应用场景：迷宫问题/回溯
概念：递归就是方法自己调用自己，每次调用时传入不同的变量。
递归调用规则：

1. 当程序执行到一个方法时，就会开辟一个独立的空间(栈)
2. 2. 每个空间的数据(局部变量)，是独立的.

1. 各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)
2. 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.
3. 将用栈解决的问题–>第归代码比较简洁

递归需要遵守的重要规则

1. 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
2. 方法的局部变量是独立的，不会相互影响, 比如 n 变量
3. 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
4. 递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError，死循环:)
5. 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或
   者返回时，该方法也就执行完毕

定义：排序是将一组数据，根据指定的顺序进行排序的过程

排序的分类：

1. 内部排序（8种，重点，面试经常考）
把需要处理的所有数据加载入内部存储器/内存中进行排序

2. 外部排序
   当数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

算法时间复杂度（如何衡量一个程序执行时间）

1. 事后统计法
   局限：
   需要先运行程序，需要等；
   依赖于计算机的硬件、软件等环境。

2. 事前估算法
   通过分析某个算法的时间复杂度来判断哪个算法更优。

时间频度：一个算法花费的时间与算法中语句的执行次数成正比。一个算法中的语句执行次数称为语句频度或时间频度。

随着n的变大，有三个特点：
忽略常数项，忽略低次项（n的一次方），忽略系数。
所以时间复杂度主要还是看n的高次方

函数T(n)可能不相同，时间复杂度O(n)可能相同

计算时间复杂度的Steps：

1. 用常数1代替运行时间中的所有加法常数 T(n)=5n²+7n+6 => T(n)=5n²+7n+1
2. 修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = 5n²
3. 去除最高阶项的系数 T(n) = 5n² => T(n) = n² => O(n²)

常见的时间复杂度

1. 常数阶O(1) ：没有循环等复杂结构，就算有几十万行，也是O(1)

2. 对数阶O(log2n) ： 常数的n次方
   e.g while(i < n)
   i=i*2;
   2的 x 次方等于 n即可退出循环，那么 x = log2n也就是说当循环 log2n 次以后
   （N=a的x次方，x=loga N）

3. 线性阶O(n) ：一个for循环，这个for循环会执行n次，T(n)=n+1，时间复杂度为O(n)。

4. 线性对数阶O(nlog2n) ：for 套 对数阶 = O(n*log2n)

5. 平方阶O(n²) ：双层for循环

6. 立方阶O(n³) ：三层for循环

7. k次方阶O(n^k) ：嵌套了k次for循环

8. 指数阶O(2ⁿ) ：尽量避免

算法的时间复杂度

空间复杂度

基本介绍

1. 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
2. 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
3. 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

1. 冒泡排序Bubble Sorting

基本思想是：
通过对待 排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下 来没有进行过交换，就说明序列有序，因此要在排序过程中设置 一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)

e.g. 原始数组：3,9,-1,10,20 数组大小：size=5
总共需要size-1次

第一趟排序
(1) 3, 9, -1, 10, 20 // 如果相邻的元素逆序就交换
(2) 3, -1, 9, 10, 20
(3) 3, -1, 9, 10, 20
(4) 3, -1, 9, 10, 20

第二趟排序
(1) -1, 3, 9, 10, 20 //交换
(2) -1, 3, 9, 10, 20
(3) -1, 3, 9, 10, 20

第三趟排序
(1) -1, 3, 9, 10, 20
(2) -1, 3, 9, 10, 20

第四趟排序
(1) -1, 3, 9, 10, 20

小结冒泡排序规则 for{for{}}
(1) 一共进行 数组的大小 size-1次 的大循环
(2) 每一趟排序的次数在逐渐的减少
(3) 优化：如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。

3. 优化：如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。
   使用flag （boolean）表示是否进行果交换
   优化过后，提前结束冒泡排序

2. 选择排序

是从预排序的数据中，按指定的规则选出某一元素，再依照规定交换位置后达到排序的目的
从整个数组中找到最小值，跟arr[0]交换，（范围：arr[0] ~ arr[n-1]）
第二次从数组中找到最小值，跟arr[1]交换。（范围：arr[1] ~ arr[n-1]）

以此类推，总共需要size-1次，得到一个按排序码从小到大排列的有序序列。

原始的数组 ： 101, 34, 119, 1
第一轮排序 :
1, 34, 119, 101

第二轮排序 :
1, 34, 119, 101
第三轮排序 :
1, 34, 101, 119

说明：

1. 选择排序一共有 数组大小 - 1 轮排序
2. 每1轮排序，又是一个循环, 循环的规则(代码)
   2.1先假定当前这个数是最小数 arr[0]
   2.2 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
   2.3 当遍历到数组的最后时，就得到本轮最小数和下标
   2.4 交换 [代码中再继续说 ]

选择排序算法快于冒泡算法

3. 插入排序Insertion Sorting

介绍:
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序（Insertion Sorting）的基本思想是：
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

次数：size-1次

插入和冒泡算法话费的时间差不多

4. 希尔排序shell

基本排序的更高效的版本，也称缩小增量排序
基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

希尔排序法应用：

1. 希尔排序时， 对有序序列在插入时采用交换法, 并测试排序速度.
2. 希尔排序时， 对有序序列在插入时采用移动法, 并测试排序速度

交换希尔排序比插入慢
优化：移动法，比交换希尔排序 和插入 快很多，十分的厉害

5. 快速排序（Quicksort）

介绍:
快速排序（Quicksort）是对冒泡排序的一种改进。

基本思想是：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

步骤

1）找到中位数pivot，
2）一直找，找到左边比pivot大的；再一直找，找到右边比pivot小的。
3）进行交换；
4）递归 recursion
. 4.1 左递归
. 4.2 右递归

我的题解 - leetcode18 将数组的奇数放在数组的前半部分，偶数放在数组的后半部分：

https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solution/qi-shu-fang-zai-shu-zu-de-qian-ban-bu-fe-v7mr/

我的题解 - LeetCode剑指40 k个数最小的元素

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/kge-shu-zui-xiao-de-yuan-su-by-duo-bi-e-vgnx/

快速排序十分快！8w数据0~1秒

快排实例：
原数组：[-9,78,0,23,-567,70]

思路：标志数x 在x左边找比x大的数， 在x右边找比x小的数， 进行交换

1. 快速排序得到：x = 0的话，0左边的78比0大；0右边的-567比0小，进行交换，得到：【-9,-567,0,23,78,70】
2. 进行左递归得到：【-567，-9,0,23,78,70】
3. 进行右递归得到：【-567，-9,0,23,70,78】

6. 归类排序Merge Sort

介绍：是利用归并的思想实现的排序方法，该算法采用经典的分治算法策略
（分治法：分阶段：将问题分成一些小问题然后递归求解，治阶段：则将分的阶段得到的答案修补在一起）

归并排序时间很短！！！8w数据0~1秒

题：合并两个有序序列

7. 基数排序

1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序(Radix Sort)是桶排序的扩展
4. 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序基本思想

1. 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
2. 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

基数排序十分快；8w1s，80w1s，800w1s，但是会耗费内存。

基数排序的说明:

1. 基数排序是对传统桶排序的扩展，速度很快.
2. 基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
3. 基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
4. 有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

8. 第八个堆排序跟二叉树相关，等二叉树那再讲

相关术语：

1. 稳定：相同的数在排序之后位置不会变。比如 1a = 1b, [1a,56,8,5,6,2,8,1b], 1a在1b前面，排序后，1a任然在1b前面
2. 不稳定： 1a在1b前面，排序后，1a可能在1b后面
3. 内排序：在内存里进行排序
4. 外排序：在内存外进行排序
5. 时间复杂度：一个算法执行所消耗的时间
6. 空间复杂度：一个算法执行所消耗的空间/内存大小
7. n：数据规模
8. k：桶的个数
9. in-place：不占用额外内存空间
10. out-place：占用额外内存空间

1. 顺序(线性)查找
2. 二分查找/折半查找
3. 插值查找
4. 斐波那契查找

【顺序查找】就是最简单的用for循环找某个值，传入一个数组和标志，有提示找到 并给出下标值

e.g.
有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称
【顺序查找】 要求: 如果找到了，就提示找到，并给出下标值

二分查找：
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.

二分查找的思路分析

1. 首先确定该数组的中间的下标 mid = (left + right) / 2
2. 然后让需要查找的数 findVal 和 arr[mid] 比较
   2.1 findVal > arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找
   2.2 findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
   2.3 findVal == arr[mid] 说明找到，就返回
3. 结束递归.
   1. 找到就结束递归
   2. 递归完整个数组，仍然没有找到findVal ，也需要结束递归 当 left > right 就需要退出

若要找的数，有多个相同的数值时，可将所有相同的值放入ArrayList