6.螺旋矩阵
给定一个正整数 n,生成一个包含 1 到 n 2 n^2n
2
所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。
这里给一个官方的结题思路,里面的动态图能很好的帮助我们理解!
螺旋矩阵 II - 螺旋矩阵 II - 力扣(LeetCode) (leetcode-cn.com)
思路
用的是官方解答的第二种方法,按层打印
看了好几遍都不明白,然后不断debug还是不行。
后来在纸上自己画了一遍给的动画图,然后手写程序,手动debug一下就明白了
中间的if(left < right && top < bottom)这是干什么的呢?
因为整体的思想right,left,top,bottom循环一轮就会往里面缩,加上这条进行判断缩小后不在继续打印了就打印打n的平方
然后还有个关键点是打印的时候要保证左开右闭或者左闭右开的原则,什么意思,第一行打印的时候,可以=right
但是打印第三行的时候right != left
上下打印也是一样,往下移动的时候=底部,那么往上移动的时候要!=top
看了好几天总于看明白了,还是太浮躁了,慢慢来~~~
描述的不好,以后会继续努力!!!
public class SpiralMatrix { public static void main(String[] args) { SpiralMatrix sm = new SpiralMatrix(); int[][] ints = sm.generateMatrix3(3); for (int[] anInt : ints) { for (int i : anInt) { System.out.print(i + "\t"); } System.out.println(); } } public int[][] generateMatrix3(int n) { int num = 1; int[][] matrix = new int[n][n]; //定义一个二维数组 int left = 0, right = n - 1, top = 0, bottom = n - 1; //按层模拟 while (left <= right && top <= bottom) { // 将第一行赋值完成 for (int column = left; column <= right; column++) {//column列 matrix[top][column] = num; num++; } // 将第二行赋值 for (int row = top + 1; row <= bottom; row++) { //row行 matrix[row][right] = num; num++; } if (left < right && top < bottom) { for (int column = right - 1; column > left; column--) { matrix[bottom][column] = num; num++; } for (int row = bottom; row > top; row--) { matrix[row][left] = num; num++; } } left++; right--; top++; bottom--; } return matrix; } }
总结篇
基础回顾
数组是存放在连续内存空间上的相同类型数据的集合。
数组下标都是从0开始的。
数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。
数组的元素是不能删的,只能覆盖。
二分法
循环不变量原则,只有在循环中坚持对区间的定义,才能清楚的把握循环中的各种细节。
二分法是算法面试中的常考题,建议通过这道题目,锻炼自己手撕二分的能力。
双指针法
双指针法(快慢指针法):通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
滑动窗口
数组操作中的另一个重要思想:滑动窗口。滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O ( n 2 ) O(n^2)O(n
2
)的暴力解法降为O ( n ) O(n)O(n)。
二维数据在内存中不是 3\*4 的连续地址空间,而是四条连续的地址空间组成!
模拟行为
模拟类的题目在数组中很常见,不涉及到什么算法,就是单纯的模拟,十分考察大家对代码的掌控能力。
在这道题目中,我们再一次介绍到了循环不变量原则,其实这也是写程序中的重要原则。
相信大家又遇到过这种情况: 感觉题目的边界调节超多,一波接着一波的判断,找边界,踩了东墙补西墙,好不容易运行通过了,代码写的十分冗余,毫无章法,其实真正解决题目的代码都是简洁的,或者有原则性的,大家可以在这道题目中体会到这一点