[数据结构与算法]【数组专题】—— 模拟法

$模拟法$

1.什么是模拟法？

据相传，模拟法是最不像算法的算法。通过模拟实现某种具体的要求。

2.LeetCode 59. 螺旋矩阵 II

(1) 此题就是一个典型的用模拟法来解决问题的。

(2) 我认为解决这个问题的关键在于找准关键点与边界的变化

(3) 通过二维数组来模拟比较形象，指定了顺时针方向移动也就决定了我们填充的顺序

(4) 首先定位到四个初始的边界：也就是上下左右，因为传入的参数为 n,数组的大小也就为 n * n。

top = 0
bottom = n - 1
left = 0
right = n - 1

• 这里的定位是代表的是在数组中的索引

(5) 将整个填充的过程划分为四个方向上的填充

从左到右 —— 对应上边界
从上到下 —— 对应右边界
从右到左 —— 对应下边界
从下到上 —— 对应左边界

(6) 填充完一行或一列之后都会涉及到边界的变化

上边界填充完一次 top 要向下移动
下边界填充完一次 bottom 要向上移动
左边界填充完一次 left 要向右移动
有边界填充完一次 right 要向左移动

3.代码部分:

class Solution {
    public int[][] generateMatrix(int n) {
        //模拟法创建一个二维数组
        //对四个点进行定位
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;

        /*
        对于整个填充流程我们可以看成四步：
            （1）从左向右填充
            （2）从上向下填充
            （3）从右向左填充
            （4）从下向上填充

        填充结果: 把 1-n^2 全部填充到矩阵中

        注意事项: 对于每一行和每一列完成填充后下一次填充可能涉及边界的变化

         */

         //定义一个数作为填充数
         int cut = 1;

        //定义一个二维数组
        int [][] arr = new int [n][n];

        //通过循环进行不断填充
         while(cut <= n * n){
             //自左向右
             for(int i = left; i <= right; i++){
                 arr[top][i] = cut;
                 cut++;
             }
             top++;

            //自上向下
            for(int i = top; i <= bottom; i++){
                arr[i][right] = cut;
                cut++;
            }
            right--;

            //自右向左
            for(int i = right; i >= left; i--){
                arr[bottom][i] = cut;
                cut++;
            }
            bottom--;

            //自下向上
            for(int i = bottom; i >= top; i--){
                arr[i][left] = cut;
                cut++;
            }
            left++;

         }

         return arr;
    }
}