1.稀疏数组

需求

五子棋游戏
要有存盘退出,续上盘的功能
image.png
第一步的抽象:把五子棋的某一时刻转换为二维数组
问题:里面有很多没有意义的数据
第二步的解决方法:抽象为稀疏数组(见下图)

介绍

画图

image.png

文字说明

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

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

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

    分析思路

    1.数组转稀疏

    计算出有值的个数
    赋值

    2.稀疏转数组

    还原

    代码实现

    1. public class SparseArray {
    2.  public static void main(String[] args) {
    3.      //初始化数组
    4.      int[][] rawArray = new int[11][11];
    5.      rawArray[1][2] = 1;
    6.      rawArray[2][3] = 2;
    7.      rawArray[4][5] = 1;
    8.      showArray(rawArray);
    9.      int[][] sparseArray = array2Sparse(rawArray);
    10.      showArray(sparseArray);
    11.      int[][] convertArray = sparse2Array(sparseArray);
    12.      System.out.println("=============================================================");
    13.      showArray(convertArray);
    14.  }
    15.  //打印数组
    16.  public static void showArray(int[][] printArray) {
    17.      for (int[] ints : printArray) {
    18.          for (int val : ints) {
    19.              System.out.printf("%d\t", val);
    20.          }
    21.          System.out.println();
    22.      }
    23.  }
    24.  //二维数组转稀疏数组
    25.  public static int[][] array2Sparse(int[][] rawArray) {
    26.      int count = 0;
    27.      for (int[] ints : rawArray) {
    28.          for (int val : ints) {
    29.              if (val > 0) {
    30.                  count++;
    31.              }
    32.          }
    33.      }
    34.      System.out.println("count:" + count);
    35.      int[][] sparseArray = new int[count + 1][3];//根据count 声明稀疏数组
    36.      sparseArray[0][0]=rawArray.length;
    37.      sparseArray[0][1]=rawArray[0].length;
    38.      sparseArray[0][2]=count;
    39.      int sparseRowIndex=0;//记录下稀疏的行
    40.      for (int row=0;row<rawArray.length;row++) {
    41.          for (int col=0;col<rawArray[0].length;col++) {
    42.              if (rawArray[row][col]>0) {
    43.                  sparseRowIndex++;
    44.                  sparseArray[sparseRowIndex][0]=row;
    45.                  sparseArray[sparseRowIndex][1]=col;
    46.                  sparseArray[sparseRowIndex][2]=rawArray[row][col];
    47.              }
    48.          }
    49.      }
    50.      return sparseArray;
    51.  }
    52.  //稀疏数组转二维数组
    53.  public static int[][] sparse2Array(int[][] sparseArray) {
    54.      int[][] array=new int[sparseArray[0][0]][sparseArray[0][1]];
    55.      for (int i = 1; i < sparseArray.length; i++) {
    56.          //i 代表 稀疏数组的行数
    57.          array[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    58.      }
    59.      return array;
    60.  }
    61. }

    运行结果

    image.png

    思考小结

    1.需要慢慢调试,慢慢改
    2.转稀疏数组的时候要控制行和列,用原始for循环替代增强for循环
    3.转二维数组的时候注意下标控制
    4.写算法慢慢来不要急

    2.队列

    需求

    类似银行排队的效果

    介绍

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

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

image.png

2.1 简单队列

思路

  1. 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图,其中maxSize是该队列的最大容量。
  2. 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变

  3. 需要实现的方法:add get head show isfull isempty

    代码实现

    ```java public class ArrayQueue { int size;//队列容量 int[] arr;//数组存放数据 int front;//队列头指针 int rear;//队列尾指针

    public ArrayQueue(int size) {

    1.  this.size = size;
    2.  this.front=-1;
    3.  this.rear=-1;
    4.  arr = new int[size];

    }

    public void show(){

    1.  if (isEmpty()) {
    2.      System.out.println("队列空的,无法取数据");
    3.      return;
    4.  }
    5.  for (int i = 0; i < arr.length; i++) {
    6.      System.out.printf("a[%d]=%d\n",i,arr[i]);
    7.  }

    }

    public boolean isFull(){

    1.  return rear == size - 1;

    }

    public boolean isEmpty(){

    1.  return rear == front;

    }

  1. public void add(int val) {
  2.     if (isFull()) {
  3.         System.out.println("满了,无法添加");
  4.         return;
  5.     }
  6.     rear++;
  7.     arr[rear] = val;
  8. }
  10. public int get() {
  11.     if (isEmpty()) {
  12.         throw new RuntimeException("队列空的,无法取数据");
  13.     }
  14.     front++;
  15.     return arr[front];
  16. }
  18. public int head(){
  19.     if (isEmpty()) {
  20.         throw new RuntimeException("队列空的,无法取数据");
  21.     }
  22.     return arr[front+1];
  23. }
  25. public static void main(String[] args) {
  26.     ArrayQueue queue = new ArrayQueue(3);
  27.     queue.add(3);
  28.     System.out.println(queue.head());
  29.     queue.add(4);
  30.     System.out.println(queue.head());
  31.     queue.add(5);
  32.     System.out.println(queue.head());
  33.     queue.add(6);
  34.     queue.show();
  35.     System.out.println(queue.get());
  36.     System.out.println(queue.get());
  37.     System.out.println(queue.get());
  38.     System.out.println(queue.get());
  39. }

}

  1. <a name="uLAlp"></a>
  2. ### 运行结果
  3. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/655064/1638846136792-3d423ba6-c9c0-42a3-bb8c-5799e467efc3.png#clientId=u2b8eacd7-ffa1-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=171&id=udf81d62d&margin=%5Bobject%20Object%5D&name=image.png&originHeight=341&originWidth=881&originalType=binary&ratio=1&rotation=0&showTitle=false&size=31997&status=done&style=none&taskId=u0bb02f16-ef88-490b-9bda-3fa68fdcf29&title=&width=440.5)
  4. <a name="dBQyL"></a>
  5. ### 小结和优化
  7. 1. 目前数组使用一次就不能用，没有达到复用的效果
  8. 1. 将这个数组使用算法(**取模算法**)，改进成一个**环形队列**
  9. <a name="zpcVw"></a>
  10. ## 2.2 环形队列
  11. <a name="iR5AL"></a>
  12. ### 思路
  13. 重复利用数组之前空出的位置<br />重新定义front rear重新定义isFull isEmpty<br />环形其实就是类似跑步套圈
  14. <a name="OdTxW"></a>
  15. ### 实现
  16. ```java
  17. public class CircleArrayQueue {
  18.     int size;//队列容量
  19.     int[] arr;//数组存放数据
  20.     int front;//队列头指针 指向第一个元素
  21.     int rear;//队列尾指针 指向最后一个元素前一个的位置
  23.     public CircleArrayQueue(int size) {
  24.         this.size = size;
  25.         arr = new int[size];
  26.     }
  28.     public void show() {
  29.         if (isEmpty()) {
  30.             System.out.println("队列空的,无法取数据");
  31.             return;
  32.         }
  33.         for (int i = front; i < front + size(); i++) {
  34.             System.out.printf("a[%d]=%d\n", i % size, arr[i % size]);
  35.         }
  36.     }
  38.     public boolean isFull() {
  39.         return (rear + 1) % size == front;//有一个空位不能加,预留空位
  40.     }
  42.     public boolean isEmpty() {
  43.         return rear == front;
  44.     }
  47.     public void add(int val) {
  48.         if (isFull()) {
  49.             System.out.println("满了,无法添加");
  50.             return;
  51.         }
  52.         arr[rear] = val;
  53.         rear = (rear + 1) % size;
  54.     }
  56.     public int get() {
  57.         if (isEmpty()) {
  58.             throw new RuntimeException("队列空的,无法取数据");
  59.         }
  60.         int val = arr[front];
  61.         front = (front + 1) % size;
  62.         return val;
  63.     }
  65.     public int size() {
  66.         return (rear + size - front) % size;
  67.     }
  69.     public int head() {
  70.         if (isEmpty()) {
  71.             throw new RuntimeException("队列空的,无法取数据");
  72.         }
  73.         return arr[front];
  74.     }
  76.     public static void main(String[] args) {
  77.         CircleArrayQueue queue = new CircleArrayQueue(4);
  78.         queue.add(3);
  79.         queue.add(4);
  80.         queue.add(5);
  81.         queue.show();
  83.         System.out.println(queue.get());
  84.         System.out.println(queue.get());
  85.         System.out.println(queue.get());
  86.         queue.add(6);
  87.         System.out.println(queue.head());
  88.         queue.add(7);
  89.         queue.add(8);
  90.         queue.show();
  91.         System.out.println(queue.head());
  92.         System.out.println(queue.get());
  93.         System.out.println(queue.get());
  94.         System.out.println(queue.get());
  95.     }
  96. }

运行结果

image.png

小结和优化

有一点技巧,增加个获取有效数据