一、 数据结构和算法内容介绍
1. 先看几个经典的算法面试题
🔰 字符串匹配问题：
1） 有一个字符串 str1= “ 硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好 ”，和一个子串 str2= “ 尚硅谷你尚硅你 ”
2）现在要判断 str1 是否含有 str2，如果存在，就返回第一次出现的位置，如果没有，则返回 -1
3）要求用最快的速度来完成匹配
4）你的思路是什么？
- 暴力匹配【简单，但是效率低】
- KMP算法《部分匹配表》
🔰 汉诺塔游戏，请完成汉诺塔游戏的代码，要求：
1）将A塔的所有圆盘移动到C塔
2）并且规定，在小圆盘上不能放大圆盘
3）在三根柱子之间一次只能移动一个圆盘
🔰 八皇后问题：
八皇后问题是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克思·贝瑟尔于1848年提出：在 8 x 8 的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。【92】→ 分治算法
🔰 马踏棋盘算法介绍和游戏演示：
1）马踏棋盘算法也被称为骑士周游问题
2）将马随机放在国际象棋的 8 x 8 棋盘上Board【0~7】 【0~7】的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格
3）游戏演示：http://www.4399.com/flash/146267_2.htm
4）会使用到图的深度优化遍历算法(DFS) + 贪心算法优化
二、线性结构和非线性结构
① 最经典的顺序存储结构：数组。顺序表中存储元素是连续的
② 最经典的链式存储结构：链表。链表中的存储元素不一定是连续的
三、稀疏数组
1.基本介绍
2.举例说明
（1）二维数组 转 稀疏数组的思路
① 遍历原始的二维数组，得到有效数据的个数 sum
② 根据 sum 就可以创建稀疏数组 sparseArr int[sum+1][3]
③ 第一行三个数据分别为原始数组的行、列、有效数据个数
④ 将二维数组的有效数据存入到稀疏数组
（2）稀疏数组 转 原始的二维数组的思路
① 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2=int[11][11]
② 再读取稀疏数组后几行的数据，并赋给原始的二维数组即可
代码
package com.atguigu.sparsearray;
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<11;i++) {
for(int j=0;j<11;j++) {
if(chessArr1[i][j]!=0) {
sum++;
}
}
}
// 2. 创建对应的稀疏数组
int sparseArr[][]=new int[sum +1][3];
// 给稀疏数组赋值
sparseArr[0][0]=11;
sparseArr[0][1]=11;
sparseArr[0][2]=sum;
// 遍历二维数组，将非0的值存放到sparseArr中
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;
sparseArr[count][1]=j;
sparseArr[count][2]=chessArr1[i][j];
}
}
}
// 输出稀疏数组的形式
System.out.println();
System.out.println("得到稀疏数组为~~~~");
for(int i=0;i<sparseArr.length;i++) {
System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
System.out.println();
// 将稀疏数组--》恢复成原始的二维数组
// ① 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2=int[11][11]
// ② 再读取稀疏数组后几行的数据，并赋给原始的二维数组即可
// ① 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2=int[11][11]
int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
// ② 再读取稀疏数组后几行的数据（从第二行开始），并赋给原始的二维数组即可
for(int i=1;i<sparseArr.length;i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
// 输出恢复后的二维数组
System.out.println();
System.out.println("恢复后的二维数组");
for(int[] row:chessArr2) {
for(int data:row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
运行结果
