极简Java数据结构-稀疏数组SparseArray
【摘要】 👨🏻🎓博主介绍:大家好,我是芝士味的椒盐,一名在校大学生,热爱分享知识,很高兴在这里认识大家🌟🌈擅长领域:Java、大数据、运维、电子🙏🏻如果本文章各位小伙伴们有帮助的话,🍭关注+👍🏻点赞+🗣评论+📦收藏,相应的有空了我也会回访,互助!!!🤝另本人水平有限,旨在创作简单易懂的文章,在文章描述时如有错,恳请各位大佬指正,在此感谢!!!@[TOC] 经典算法面试题字符...
👨🏻🎓博主介绍:大家好,我是芝士味的椒盐,一名在校大学生,热爱分享知识,很高兴在这里认识大家🌟
🌈擅长领域:Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话,🍭关注+👍🏻点赞+🗣评论+📦收藏,相应的有空了我也会回访,互助!!!
🤝另本人水平有限,旨在创作简单易懂的文章,在文章描述时如有错,恳请各位大佬指正,在此感谢!!!
@[TOC]
经典算法面试题
- 字符串匹配问题:
- 暴力匹配[简单,效率低下]
- KMP算法《部分匹配表》
- 汉罗塔游戏
- 分治算法
- 八皇后问题
- 回溯算法
- 马踏棋盘
- 深度优化遍历算法(DFS)+贪心算法
数据结构和算法的关系
- 数据结构是一门研究组织数据方式的学科,有了编程语言也就有了数据结构.学好数据结构可以编写出更加漂亮,更加有效率的代码。
- 程序 = 数据结构 + 算法
常见算法
- 修路问题 => 最小生成树(加权值)【数据结构】+ 普利姆算法
- 最短路径问题 => 图+弗洛伊德算法
- 汉诺塔 => 分支算法
- 八皇后问题 => 回溯法
线性结构和非线性结构
- 数据结构分为线性结构和非线性结构
- 线性结构
- 数据元素之间一对一的的线性关系
- 有两种不同的存储结构:
- 顺序结构—>顺序表(元素连续)(数组)
- 链式存储结构—>链表(元素不一定是连续的,元素节点存放数据元素及相邻元素的地址信息)(链表)
- 常见的结构有:数组、队列、链表和栈
- 非线性结构
- 二维数组、多维数组、广义表、树结构、图结构
稀疏表
-
适用场景
- 当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组
-
稀疏数组的处理方法:
- 记录数组一共有几行几列,有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
-
例子:
-
原始二维数组和稀疏数组之间的转换原理:
-
代码复现:
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(); } } }
执行结果:
推荐
![](https://res.hc-cdn.com/ecology/9.3.130/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)