新星计划Day4【数据结构与算法】 稀疏数组与队列

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

💻首发时间：🎞2022年4月28日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

图片

🛒导航小助手🎪

⛳001 几个经典的算法面试题（1）

字符串匹配问题：： 有一个字符串 str1= ""硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好""，和一个子串 str2="尚硅谷你尚硅你" 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1 要求用最快的速度来完成匹配 你的思路是什么？

暴力匹配 KMP算法《部分匹配表》

汉诺塔游戏, 请完成汉诺塔游戏的代码: 要求：1) 将A塔的所有圆盘移动到C塔。并且规定，在2) 小圆盘上不能放大圆盘，3)在三根柱子之间一次只能移动一个圆盘 使用到分治算法.

🛶002 几个经典的算法面试题（2）

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。【92】

使用到回溯算法

高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题

马踏棋盘算法介绍和游戏演示 马踏棋盘算法也被称为骑士周游问题 将马随机放在国际象棋的8×8棋盘Board0～7的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格

会使用到图的深度优化遍历算法(DFS) + 贪心算法优化

🎩003 内容介绍与授课方式

数据结构和算法的重要性

算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算 一般来讲 程序会使用了内存计算框架(比如Spark)和缓存技术(比如Redis等)来优化程序,再深入的思考一下，这些计算框架和缓存技术， 它的核心功能是哪个部分呢？

拿实际工作经历来说, 在Unix下开发服务器程序，功能是要支持上千万人同时在线， 在上线前，做内测，一切OK,可上线后，服务器就支撑不住了, 公司的CTO对代码进行优化，再次上线，坚如磐石。你就能感受到程序是有灵魂的，就是算法。 目前程序员面试的门槛越来越高，很多一线IT公司(大厂)，都会有数据结构和算法面试题(负责的告诉你，肯定有的)

如果你不想永远都是代码工人,那就花时间来研究下数据结构和算法

👝006 线性结构与非线性结构

线性结构

• 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。

• 线性结构有两种不同的存储结构，即顺序存储结构（数组）和链式存储结构（链表）。顺序存储结构的线性表称为顺序表，顺序表中的存储元素是连续的。

• 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。

• 线性结构常见的有：数组、队列、链表和栈，后面我会相信讲解。

非线性结构

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

🥋007 稀疏数组的应用场景

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

稀疏数组的处理方法是

• 记录数组一共有几行几列，有多少个不同的值

• 把具有不同值的元素的行列及值记录在一个小规模数组中，从而缩小程序的规模

• 

🎎008 稀疏数组转换的思路分析

二维数组转稀疏数组的思路

1.遍历原始的二维数组，得到要保存的有效数据个数

2.根据sum就可以创建稀疏数组sparseArr intsum+1

3.将二维数组的有效数据存入到稀疏数组中

稀疏数组转原始的二维数组的思路

1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr2=int11

2.在读取稀疏数组后几行的数据， 并赋给原始的二维数组即可

🥌009 稀疏数组的代码实现

 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][4]=2;
         //输出原始的二维数组
         System.out.println("原始的二维数组");
         for(int[] row:chessArr1){
             for(int data:row){
                 System.out.println("%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++;
                     }
                 }
             }
             System.out.println("sum="+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",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
                
             }
             System.out.println();
             //稀疏数组转原始的二维数组的思路
             //1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
             int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
             //2.在读取稀疏数组后几行的数据(从第二行）， 并赋给原始的二维数组即可
             for(int i=1;i<soarseArr.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.println("%d\t",data);
             }
         }
     }
 }

👗010 队列的应用场景与介绍

• 队列是一个有序列表，可以用数组或是链表实现

• 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。

🥽011 数组模拟队列的思路分析

• 队列本身也是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中MaxSize为队列的最大容量

• 因为队列的输出输入是分别从前后端来处理，因此需要两个变量front和rear分别记录前后端的下标，front会随着数据输出而改变，而rear会随着数据输入而改变

• 当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析

  1) 将尾指针往后移：rear + 1 , 当 rear == front 【空】

  2) 若尾指针 rear 小于队列的最大下标 MaxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 reatr == MaxSize - 1[队列满]

  
  

  🩰012 数组模拟队列实现

   public class ArrayQueueDemo{
       public static void main(String[] args){
           //测试一把
           //创建一个队列
           ArrayQueue queue=new ArrayQueue(3);
           char key=' ';//接收用户输入
           Scanner scanner=new Scanner(System.in);
           boolean loop=true;
           //输出一个菜单
           while(loop){
               System.out.println("s(show):显示队列");
               System.out.println("e(exit):退出程序");
               System.out.println("a(add):添加数据到队列");
               System.out.println("g(get):从队列取出数据");
               System.out.println("h(head):查看队列头的数据");
               key=scanner.next().charAt(0);//接收一个字符
               switch(key){
                   case 's':
                       queue.showQueue();
                       break;
                   case 'a':
                       System.out.println("输出一个数");
                       int value=scanner.nextInt();
                       queue.addQueue(value);
                       break;
                   case 'g'://取出数据
                       try{
                           int res=queue.getQueue();
                           System.out.println("取出的数据是%d\n",res);
                           
                       }catch(Exception e){
                           System.out.println(e.getMessage());
                       }
                       break;
                   case 'h'://查看队列头的数据
                       try{
                           int res=queue.headQueue();
                           System.out.println("队列头的数据是%d\n",res);
                       }catch(Exception e){
                           System.out.println(e.getMessage());
                       }
                       break;
                   case 'e'://退出
                       scanner.close();
                       loop=false;
                       break;
                   default:
                       break;
               }
           }
           System.out.println(程序退出);
       }
   }
   //使用数组模拟队列-编写一个ArrayQueue类
   class ArrayQueue{
       private int maxsize;//表示数组的最大容量
       private int front;//队列头
       private int front;//队列尾
       private int[] arr;//该数组用于存放数据，模拟队列
       //创建队列的构造器
       public ArrayQuene(int arrMarSize){
           maxSize=arrMaxSize;
           arr=new int[maxSize];
           front=-1;//指向队列头部，分析出front是指向队列头的前一个位置
           rear=-1;//指向队列尾，指向队列尾的数据（即就是队列最后一个数据）
       }
       //判断队列是否满
       public boolean isFull(){
           return rear==maxsize-1;
       }
       //判断队列是否为空
       public boolean isEmpty(){
           return rear==front;
       }
       //添加数据到队列
       public void addQueue(int n){
           //判断队列是否满
           if(isFull()){
               System.out.println("队列满，不能加入数据");
               return;
           }
           rear++;//让rear后移
           arr[rear]=n;
       }
       //获取队列的数据，出队列
       public int getQueue(){
           //判断队列是否空
           if(isEmpty()){
               //通过抛出异常
               throw new RuntimeException("队列空，不能取数据");
           }
           front++;//front后移
           return arr[front];
       }
       //显示队列的所有数据
       public void showQueue(){
           //遍历
           if(isEmpty()){
               System.out.println("队列孔，没有数据");
               return;
           }
           for(int i=0;i<arr.length;i++){
               System.out.println("arr[%d]=%d\n",i,arr[i]);
           }
       }
       //显示队列的头数据，注意不是取出数据
       public int headQueue(){
           //判断
           if(isEmpty()){
               throw new RuntimeException("队列空，不能取数据");
           }
           return arr[front+1];
       }
   }

  此种方式存在的问题和优化方案

  • 数组使用一次就不能使用了，没有达到复用的效果

  • 使用算法，改成一个环形的队列：取模%

  
  

下期预告：新星计划Day5 【数据结构与算法】链表

觉得文章写的不错的亲亲们，点赞评论走一波，爱你们哦！🥗