第一题:顺时针输出螺旋矩阵:
螺旋矩阵
在本题中,这个状态就是当前的矩阵坐标和运行方向,而状态的转移遵循题目的限制规则:
-
顺时针旋转走位,这表示 如果当前是向右行走,那么接下来只能是向右或者向下,如果继续向右不会越界,也不会踩到已经走过的格子,那么就向右,否则就向下。 以此类推。所以很容易得出状态表:
right: ['right', 'bottom'] //当前方向是right 只能保持right或者转向bottom,据此穷举出状态对应关系 bottom: ['bottom', 'left'] //同上... left: ['left', 'top'] top: ['top', 'right']
/** * 状态机存储以下几个信息: * 当前的行进方向 curDir * 状态转移关系表 STATUS_TABLE * 当前的坐标 x y * 矩阵的宽高 w h * 已经走过的格子 viewedTable 是一个二维数组 存储布尔值 */ class AutoMachine { constructor(w, h, x = -1, y = 0, curDir = 'right') { this.viewedTable = new Array(h).fill(0).map(i => new Array(w).fill(false)); this.w = w; this.h = h; this.curDir = curDir; this.x = x; this.y = y; } //获取下一步的取值坐标 getNextCord() { this.curDir = this.getNextDir();//获取下一步行进的方向 let { curDir, x, y } = this; switch (curDir) { case 'left': x--; break; case 'right': x++ break; case 'top': y--; break; case 'bottom': y++; break; } this.x = x; this.y = y; this.viewedTable[y][x] = true;//标记这个取值过的坐标 return [x, y]; } getNextDir() { //获取接下来行进的方向 //通过isRightDir判断当前方向是否还能前进, //如果可以继续行进 则维持当前状态 如果不能继续 则切换到下一个状态(转换方向) //状态切换的规则在状态对应表table中定义 let { curDir, x, y } = this; let colIndex; if (this.isRightDir(x, y, curDir)) colIndex = 0; else colIndex = 1; return this.STATUS_TABLE[curDir][colIndex]; } //状态对应表: STATUS_TABLE = { //由于是顺时针螺旋,很容易得出状态的转移规则: 右 -> 下 -> 左 -> 上 -> 右 ... right: ['right', 'bottom'], bottom: ['bottom', 'left'], left: ['left', 'top'], top: ['top', 'right'], }; isRightDir() { //通过探测 判断下一步是否还能沿着当前的方向前进 let { w, h, x, y, curDir } = this; if (curDir === 'left') x--; if (curDir === 'right') x++; if (curDir === 'top') y--; if (curDir === 'bottom') y++; if (x < 0 || x > w - 1 || y < 0 || y > h - 1) return false; //下一步越界了 不应该维持当前方向 返回false if (this.viewedTable[y][x]) return false;//下一步会走入已经走过的格子 返回false return true;//可以继续行进 返回true } } var spiralOrder = function (matrix) { let x = -1, y = 0; //假设我们当前在矩阵的左上角的左边 还未进入矩阵 //状态机启动后 由于我们的初始化坐标为 -1,0 方向为right 所以第一个进入的格子就是左上角的格子 let h = matrix.length; if(h === 0) return []; let w = matrix[0].length; let len = w * h; let res = []; const AM = new AutoMachine(w, h, x, y,'right'); while (res.length < len) { let [_x, _y] = AM.getNextCord();//状态机自动查找下一个坐标,然后利用坐标取值 res.push(matrix[_y][_x]); } return res; }; //测试用例: var matrix = [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]; console.log( spiralOrder(matrix) ) //输出: [1,2,3,6,9,8,7,4,5]
第二题:顺时针填写矩阵
/** * @param {number} n * @return {number[][]} */ var generateMatrix = function(n) { let x = -1, y = 0; let h = n; let w = n; let len = w * h; let i = 0; let matrix = new Array(h).fill(0).map(i => new Array(w).fill(0)); const AM = new AutoMachine(w, h, x, y); while (i++<len) { let [_x, _y] = AM.getNextCord(); matrix[_y][_x] = i; } return matrix; };
状态机解法并不快,但是胜在容易实现和理解,并且可以复用。即使某些题目条件变了,比如说从右下角开始填写,或者逆时针填写,我们仍然不需要修改状态机的代码,只需要改一下初始状态。