👨🏻🎓博主介绍：大家好，我是芝士味的椒盐，一名在校大学生，热爱分享知识，很高兴在这里认识大家🌟
🌈擅长领域：Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话，🍭关注+👍🏻点赞+🗣评论+📦收藏，相应的有空了我也会回访，互助！！！
🤝另本人水平有限，旨在创作简单易懂的文章，在文章描述时如有错，恳请各位大佬指正，在此感谢！！！
@[TOC]
经典算法面试题
字符串匹配问题:
- 暴力匹配[简单，效率低下]
- KMP算法《部分匹配表》
汉罗塔游戏
- 分治算法
八皇后问题
- 回溯算法
马踏棋盘
- 深度优化遍历算法（DFS）+贪心算法
数据结构和算法的关系
- 数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
- 程序 = 数据结构 + 算法
常见算法
- 修路问题 => 最小生成树(加权值)【数据结构】+ 普利姆算法
- 最短路径问题 => 图+弗洛伊德算法
- 汉诺塔 => 分支算法
- 八皇后问题 => 回溯法
线性结构和非线性结构
- 数据结构分为线性结构和非线性结构
线性结构
- 数据元素之间一对一的的线性关系
有两种不同的存储结构：
- 顺序结构—>顺序表（元素连续）（数组）
- 链式存储结构—>链表（元素不一定是连续的，元素节点存放数据元素及相邻元素的地址信息）（链表）
- 常见的结构有:数组、队列、链表和栈
非线性结构
- 二维数组、多维数组、广义表、树结构、图结构
稀疏表
适用场景
- 当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
稀疏数组的处理方法：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
- 例子：
- 原始二维数组和稀疏数组之间的转换原理：
代码复现：
package icu.lookyousmileface.sparsearray; import java.io.*; /** * @author 芝士味的椒盐 * @title: SparseArray * @projectName DataStructure_Algorithm * @date 2020/12/14 10:17 * 模拟棋盘 */ public class SparseArray { private static final int originalRow = 11; private static final int originalCol = 11; private static int itWorksNum; private static final File filePath = new File("map.data"); public static void main(String[] args) throws IOException { //定义原始数组 int[][] originalArray = new int[originalRow][originalCol]; originalArray[1][2] = 1; originalArray[2][3] = 2; originalArray[3][4] = 2; System.out.println("原始数组状态："); for (int[] row : originalArray) { for (int data : row) { itWorksNum = data != 0 ? ++itWorksNum : itWorksNum; System.out.print(data+"\t"); } System.out.println(); } //定义稀疏数组 originalArray.length表示行，originalArray[0].length表示列 int[][] sparseArray = new int[itWorksNum + 1][3]; sparseArray[0][0] = 11; sparseArray[0][1] = 11; sparseArray[0][2] = itWorksNum; int count = 0; for (int i = 0; i < originalArray.length; i++) { for (int i1 = 0; i1 < originalArray[0].length; i1++) { if (originalArray[i][i1] != 0) { count++; sparseArray[count][0] = i; sparseArray[count][1] = i1; sparseArray[count][2] = originalArray[i][i1]; } } } System.out.println("稀疏数组状态："); for (int[] row : sparseArray) { for (int data : row) { itWorksNum = data != 0 ? ++itWorksNum : itWorksNum; System.out.print(data+"\t"); } System.out.println(); } //稀疏数组写入到map.data FileWriter fileWriter = new FileWriter(filePath); for (int i = 0; i < sparseArray.length; i++) { for (int i1 = 0; i1 < sparseArray[0].length; i1++) { fileWriter.write(sparseArray[i][i1] + "\t"); } fileWriter.write("\r\n"); } fileWriter.close(); // ----------复原------- //将map.data中的数据读取到稀疏数组中,先读取row确定row，col是确定的 int row = 0; String line; BufferedReader bufferedReader = null; bufferedReader = new BufferedReader(new FileReader(filePath)); while ((line = bufferedReader.readLine()) != null) { ++row; } bufferedReader.close(); //根据获得的row确定稀疏数组，切片 int rowtmp = 0; int[][] originalArrayed = new int[row][3]; bufferedReader = new BufferedReader(new FileReader(filePath)); while ((line = bufferedReader.readLine()) != null) { String[] splited = line.split("\t"); for (int i = 0; i < splited.length; i++) { originalArrayed[rowtmp][i] = Integer.parseInt(splited[i]); } ++rowtmp; } // 原始数组 int[][] oArrays = new int[originalArrayed[0][0]][originalArrayed[0][1]]; for (int i = 1; i < originalArrayed.length; i++) { for (int i1 = 0; i1 < originalArrayed[0].length; i1++) { if (true){ oArrays[originalArrayed[i][1]-1][originalArrayed[i][1]] = originalArrayed[i][2]; continue; } } } System.out.println("稀疏数组复原状态："); for (int[] rowss : oArrays) { for (int data : rowss) { System.out.print(data+"\t"); } System.out.println(); } } }执行结果：
