一、Java数据结构和算法
1、数据结构和算法内容介绍
1.1、几个经典的算法面试题
1、字符串匹配问题：
- 有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串str2="尚硅谷你尚硅你"
- 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
- 要求用最快的速度来完成匹配
- 你的思路是什么？
- 若是没学过算法，第一思路就是暴力匹配(同样可以完成需求，但效率很低)
- 若是我会算法，这个题目我就会使用KMP算法(我会建立一个部分匹配表，通过匹配表的搜索词进行匹配，提高效率)
2、汉诺塔游戏
- 请完成汉诺塔游戏的代码: 要求：1) 将 A 塔的所有圆盘移动到 C 塔。并且规定，在2) 小圆盘上不能放大圆盘，3)在三根柱子之间一次只能移动一个圆盘
3、八皇后问题
- 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。【92】=> 分治算法
马踏棋盘算法介绍和游戏演示
- 马踏棋盘算法也被称为骑士周游问题
- 将马随机放在国际象棋的 8×8 棋盘 Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格
- 游戏演示: http://www.4399.com/flash/146267_2.htm
- 会使用到图的深度优化遍历算法(DFS) + 贪心算法优化
1.2、数据结构和算法的重要性
- 1) 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算
- 2) 一般来讲 程序会使用了内存计算框架(比如 Spark)和缓存技术(比如 Redis 等)来优化程序,再深入的思考一下，这些计算框架和缓存技术， 它的核心功能是哪个部分呢？
- 3) 拿实际工作经历来说, 在 Unix 下开发服务器程序，功能是要支持上千万人同时在线，在上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公司的 CTO 对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。
- 4) 目前程序员面试的门槛越来越高，很多一线 IT 公司(大厂)，都会有数据结构和算法面试题(负责的告诉你，肯定有的)
- 5) 如果你不想永远都是代码工人,那就花时间来研究下数据结构和算法
二、数据结构和算法概述
2.1.1、数据结构和算法的关系
- 1) 数据 data 结构(structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
- 2) 要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.
- 3) 程序 = 数据结构 + 算法
- 4) 数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位。
2.2、看几个实际编程中遇到的问题
2.2.1、问题一：字符串替换问题
- Java代码：
public static void main(String[] args){
String str = "Java,Java,hello,world!"
String new str = str.replaceAll("Java","胡桃~");
System.out.println("new Str = " + new Str);
}
- 问：试写出用单链表表示的字符串类及字符串节点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求字串、两串连接、求字串在串中位置等7个成员函数。
- 小结：需要使用到单链表数据结构
2.2.2、一个五子棋程序
- 如何判断游戏的输赢，并可以完成存盘退出和继续上局的功能
- 1) 棋盘 二维数组=>(稀疏数组)-> 写入文件 【存档功能】
- 2) 读取文件-> 稀疏数组-> 二维数组 -> 棋盘 【接上局】
2.2.3、约瑟夫(Josephu)问题(丢手帕问题)
- 1) Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
- 2) 提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表（单向环形链表），然后由 k 结点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
- 3) 小结：完成约瑟夫问题，需要使用到单向环形链表 这个数据结构
2.2.4、其它常见算法问题:
- 1) 修路问题 => 最小生成树(加权值)【数据结构】+ 普利姆算法
- 2) 最短路径问题 => 图+弗洛伊德算法
- 3) 汉诺塔 => 分支算法
- 4) 八皇后问题 => 回溯法
2.3 、线性结构和非线性结构
- 数据结构包括：线性结构和非线性结构
2.3.1、线性结构
- 1) 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
- 2) 线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
- 3) 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
- 4) 线性结构常见的有：数组、队列、链表和栈，后面我们会详细讲解
2.3.2、非线性结构
- 非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
三、稀疏数组和队列
3.1、稀疏 sparsearray 数组
3.1.1、先看一个实际的需求
- 编写的五子棋程序中，有存盘退出和续上盘的功能。
- 分析问题：
- 因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组
3.1.2、基本介绍
- 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
- 稀疏数组的处理方法是:
- 1) 记录数组一共有几行几列，有多少个不同的值
- 2) 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
- 稀疏数组举例说明：
3.1.3、应用实例
- 1) 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
- 2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3) 整体思路分析
二维数组转稀疏数组的思路 1. 遍历 原始的二维数组，得到有效数据的个数 sum 2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3] 3. 将二维数组的有效数据存入到稀疏数组 稀疏数组转原始的二维数组的思路 1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11] 2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.4) 代码实现，按照思路首先先把原始的二维数组进行遍历
public class SparseArray {
public static void main(String[] args) {
//首先创建一个原始的五子棋棋盘(即二维数组) 大小为 11 * 11，0表示没有棋子，1表示黑子，2表示篮子
int[][] chessArr1 = new int[11][11];
//给黑子赋值，即代表黑子的位置是在第二行的第三列，数组默认下标是从0开始的
chessArr1[1][2] = 1;
//给篮子赋值，即代表篮子的位置是在第三行的第四列，数组默认下标是从0开始的
chessArr1[2][3] = 2;
//赋值完毕，使用for循环输出原始的二维数组,即遍历到一维数组，数据到每一行，即原始的二维数组
for(int[] row : chessArr1){
//再次循环具体的数据
for(int data: row){
//格式化输出显得更美观
System.out.printf("%d\t",data);
}
//每打印一行换一行
System.out.println();
}
}
}
- 输出结果如图所示：
- 遍历二维数组过后就可以使用变量int sum去记录并得到有效数据的个数
//遍历二维数组过后得到非0数据的个数，并使用int sum记录非0的值(默认为0）
int sum = 0;
//使用for循环遍历chessArr1这个数组，意为此数组原先有多少数据就遍历多少数据
for (int i = 0; i <11; i++) {
//再遍历列数
for (int j = 0; j < 11; j++) {
//再做一个判断，若二维数组chessArr1中的i和j不为0，就让sum自增(即记录非0的数据个数)
if (chessArr1[i][j]!=0){
sum++;
}
}
}
//验证数组中非0的数据个数
System.out.println("sum =" + sum);
}
- 输出结果如图所示：也可以得出结论：非0的有效数据个数为2
- 接下来创建对应的稀疏数组int sparseArr初始化稀疏数组后遍历并输出
/**
* 接下来创建对应的稀疏数组int sparseArr [][],由于sum是存储具体数值，
* 所以sum+1，压缩成稀疏数组后具体的列是4，所以行为4-1
*/
int [][] SparseArr = new int[sum+1][3];
//根据原始数组几行几列以及有多少分离数据，给稀疏数组赋值
//第一行的第一列有11个数据
SparseArr[0][0] = 11;
//第一行的第二列也有11个数据
SparseArr[0][1] = 11;
//第一行的有效数据sum个,至此稀疏数组初始化完毕
SparseArr[0][2] = sum;
int count = 0; //使用count用于记录稀疏数组中的非0数据
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j]!=0){
count++;
SparseArr[count][0] = i; //第一列是i，由于count会递增，所以用于记录非0数据
SparseArr[count][1] = j; //第二列是j
SparseArr[count][2] = chessArr1[i][j]; //第三列是数组本身
}
}
}
//赋值完毕后输出稀疏数组的形式
System.out.println("得到的稀疏数组为如下形式~~");
//遍历输出稀疏数组SparseAr
for (int i = 0; i < SparseArr.length; i++) {
//格式化输出稀疏数组%d 代表第一行 \t代表第一列，依次递增,稀疏数组所在行的1-3列输出即可,\n代表换行
System.out.printf("%d\t%d\t%d\t\n",SparseArr[i][0],SparseArr[i][1],SparseArr[i][2]);
}
//换行
System.out.println();
}
- 输出结果如图所示：
- 图解：第一行记录了原始数组有几行几列以及数组中的非0数据个数
- 第二行和第三行分别记录非零数据的行、列、值，前面以及提及，1代表黑子，2代表篮子
- 再给一个黑子赋值,即代表黑子的位置是再第五行的第六列
chessArr1[4][5] = 1;
- 而后稀疏数组的输出结果会随着有效数字的变化而变化
- 而后再将稀疏数恢复成原始的二维数组,这是没有经过任何处理的稀疏数组转原始二维数组
/**
* 稀疏数组转原始的二维数组的思路
* 1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
* 2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
* 稀疏数组的第一行第一列就是二维数组chessArr2的行，稀疏数组的第一行第二列就是二维数组chessArr2的的列
*/
int[][] chessArr2 = new int[SparseArr[0][0]][SparseArr[0][1]];
//现在我们没有经过任何处理，直接输出看看效果
System.out.println("没经处理恢复后的二维数组");
for (int[] ints : chessArr2) {
for (int data : ints){
System.out.printf("%d\t",data);
}
//给数组加上换行
System.out.println();
}
}
- 输出结果如图：
- 得出结论，稀疏数组恢复为原始的二维数组之前需要先进行读取，所以进行操作读取并恢复二维数组
//在读取稀疏数组后几行的数据(即从第二行开始遍历)，并赋给原始的二维数组 即可.
for(int i = 1; i < SparseArr.length; i++) {
/**
* 由于稀疏数组内都是非0数据，所以不需要再进行非0判断，直接赋值即可,恢复二维数组的行和列可直接从稀疏数组中获取
* chessArr2是恢复后的原始二维数组，二维数组的行和列就直接从稀疏数组里取值即可，即i里的第一、第二、第三列，分别为 行、列、值
*/
chessArr2[SparseArr[i][0]][SparseArr[i][1]] = SparseArr[i][2];
}
//输出恢复过后的二维数组
System.out.println("恢复过后的二维数组");
for (int[] ints : chessArr2) {
for(int data : ints){
System.out.printf("%d\t",data);
}
//换行
System.out.println();
}
}
- 恢复后的二维数组如下：
