乐趣区

关于前端:螺旋矩阵

jiezi

前言

螺旋矩阵 I,II,III 的题解。三道题均应用模拟法解决。

螺旋矩阵 I

题目


给定一个蕴含 m x n 个元素的矩阵（m 行, n 列），请依照顺时针螺旋程序，返回矩阵中的所有元素。示例 1:

输出:
[[ 1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]
]
输入: [1,2,3,6,9,8,7,4,5]

思路

从终点坐标 [0,0] 开始登程，顺时针遍历分为四个方向，方向的变动如下：

left – 转向 –> bottom – 转向 –> right – 转向 –> top – 转向 –> left

在 left 方向静止时，坐标的变动，x 逐步自增 1，y 不变
在 bottom 方向静止时，坐标的变动，x 不变，y 逐步自增 1
在 right 方向静止时，坐标的变动，x 逐步自减 1，y 不变
在 top 方向静止时，坐标的变动，x 不变，y 逐步自减 1

这道题目的要害是如何转向

  1. 超出边界时转向
  2. 静止到曾经增加的后果数组的坐标时转向（应用 hash 记录那些坐标以及增加到了后果数组）

解答


/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {const w = matrix[0].length;
    const h = matrix.length;
    const total = w * h;
    const hash = {};
    const result = [];
    
    let direction = 'left';
    let x = 0;
    let y = 0;

    const isOutOfBounds = (x, y) => {
        if (x >= w || y >= h || x < 0 || y < 0 || hash[`${x},${y}`]
        ) {return true;}
        return false;
    }

    const left = (x, y) => {
        direction = 'left'
        const nextX = x + 1;
        const nextY = y;
        if (isOutOfBounds(nextX, nextY)) {return bottom(x, y)
        } else {return [nextX, nextY]
        }
    }

    const bottom = (x, y) => {
        direction = 'bottom'
        const nextX = x;
        const nextY = y + 1;
        if (isOutOfBounds(nextX, nextY)) {return right(x, y)
        } else {return [nextX, nextY]
        }
    }

    const right = (x, y) => {
        direction = 'right'
        const nextX = x - 1;
        const nextY = y;
        if (isOutOfBounds(nextX, nextY)) {return top(x, y)
        } else {return [nextX, nextY]
        }
    }

    const top = (x, y) => {
        direction = 'top'
        const nextX = x;
        const nextY = y - 1;
        if (isOutOfBounds(nextX, nextY)) {return left(x, y)
        } else {return [nextX, nextY]
        }
    }

    for (let i = 0; i < total; i++) {let item = matrix[y][x];
        hash[`${x},${y}`] = true;
        result.push(item);
        // 防止有限递归
        if (i < total - 1) {
            let nextX, nextY
            switch (direction) {
                case 'left':
                    [nextX, nextY] = left(x, y);
                    break;
                case 'bottom':
                    [nextX, nextY] = bottom(x, y);
                    break;
                case 'right':
                    [nextX, nextY] = right(x, y);
                    break;
                case 'top':
                    [nextX, nextY] = top(x, y);
                    break
            }
            x = nextX;
            y = nextY;
        }        
    }

    return result;
};

螺旋矩阵 II


给定一个正整数 n，生成一个蕴含 1 到 n2 所有元素，且元素按顺时针程序螺旋排列的正方形矩阵。示例:

输出: 3
输入:
[[ 1, 2, 3],
 [8, 9, 4],
 [7, 6, 5]
]

思路

思路和螺旋矩阵 I 统一，只是这次从遍历二维数组，改为了生成二维数组。

解答

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {if (n === 0) {return []
    }
    if (n === 1) {return [[1]]
    }
    
    const w = n;
    const h = n;
    const hash = {};
    const result = [];

    let direction = 'left';
    let x = 0;
    let y = 0;

    for (let i = 0; i < n; i++) {result.push([])
    }

    const isOutOfBounds = (x, y) => {
        if (x >= w || y >= h || x < 0 || y < 0 || hash[`${x},${y}`]
        ) {return true;}
        return false;
    }

    const left = (x, y) => {
        direction = 'left'
        const nextX = x + 1;
        const nextY = y;
        if (isOutOfBounds(nextX, nextY)) {
            direction = 'bottom'
            return [x, y + 1]
        } else {return [nextX, nextY]
        }
    }

    const bottom = (x, y) => {
        direction = 'bottom'
        const nextX = x;
        const nextY = y + 1;
        if (isOutOfBounds(nextX, nextY)) {
            direction = 'right'
            return [x - 1, y]
        } else {return [nextX, nextY]
        }
    }

    const right = (x, y) => {
        direction = 'right'
        const nextX = x - 1;
        const nextY = y;
        if (isOutOfBounds(nextX, nextY)) {
            direction = 'top'
            return [x, y - 1]
        } else {return [nextX, nextY]
        }
    }

    const top = (x, y) => {
        direction = 'top'
        const nextX = x;
        const nextY = y - 1;
        if (isOutOfBounds(nextX, nextY)) {
            
            direction = 'left'
            return [x + 1, y]
        } else {return [nextX, nextY]
        }
    }

    for (let i = 1; i <= n ** 2; i++) {
        const item = i;
        hash[`${x},${y}`] = true;
        result[y][x] = item;
        if (i < n ** 2) {
            let nextX, nextY
            switch (direction) {
                case 'left':
                    [nextX, nextY] = left(x, y);
                    break;
                case 'bottom':
                    [nextX, nextY] = bottom(x, y);
                    break;
                case 'right':
                    [nextX, nextY] = right(x, y);
                    break;
                case 'top':
                    [nextX, nextY] = top(x, y);
                    break
            }
            x = nextX;
            y = nextY;
        }
    }

    return result;
};

螺旋矩阵 III

思路

本题仍然应用模拟法解决，只是转向的边界判断有所扭转。

咱们首先将原点坐标 push 进入后果数组中，而后从 bottom 方向开始遍历（方向的变动：bottom -> right -> top -> left -> bottom )。在四个方向上 x，y 坐标变动的法则和螺旋矩阵 I 统一。咱们次要是须要找到转向的法则。

通过上图，能够得出两个论断：

  1. 对于前 3 次转向（从 bottom 方向开始），都是在坐标挪动 2 个长度后转向
  2. 之后的转向，都是坐标静止 3 + n 个长度后转向（n 初始等于 0）。当转向的次数每累计 2 次后，n 须要自增 1

解答


/**
 * @param {number} R
 * @param {number} C
 * @param {number} r0
 * @param {number} c0
 * @return {number[][]}
 */
var spiralMatrixIII = function(R, C, r0, c0) {
    const total = R * C
    const result = []
    let current = 0
    let turnsNumber = 1; // 每距离 2 次转弯的时候，边长须要加 1（然而前 3 次都是 2，3 次之后是这个法则）let direction = 'bottom' // left -> bottom -> right -> top -> left 方向变动的程序
    let sideLength = 2;
    let x = c0;
    let y = r0;

    // 判断坐标是否非法
    const isLegal = () => {if (x < 0 || y < 0 || x >= C || y >= R) {return false;} else {
            current += 1;
            return true;
        }
    }

    // 首先尝试增加终点的坐标
    if (isLegal()) {result.push([y, x])
        x = x + 1;
        y = y;
    }

    const calculateSideLength = () => {if (turnsNumber <= 3) {sideLength = 2} else {sideLength = 2 + Math.ceil((turnsNumber - 3) / 2)
        }
    }

    const left = () => {
        let num = 0;
        while (num < sideLength) {if (isLegal()) {result.push([y, x]);
            }
            num += 1;
            if (num < sideLength) {
                x = x + 1;
                y = y;
            }
        }
        direction = 'bottom'
        x = x;
        y = y + 1;
    }

    const bottom = () => {
        let num = 0;
        while (num < sideLength) {if (isLegal()) {result.push([y, x]);
            }
            num += 1;
            if (num < sideLength) {
                x = x;
                y = y + 1;
            }
        }
        direction = 'right'
        x = x - 1;
        y = y; 
    } 

    const right = () => {
        let num = 0;
        while (num < sideLength) {if (isLegal()) {result.push([y, x]);
            }
            num += 1;
            if (num < sideLength) {
                x = x - 1;
                y = y; 
            }
        }
        direction = 'top'
        x = x;
        y = y - 1;
    }

    const top = () => {
        let num = 0;
        while (num < sideLength) {if (isLegal()) {console.log('top', y,x)
                result.push([y, x]);
            }
            num += 1;
            if (num < sideLength) {
                x = x;
                y = y - 1;
                
            }
        }
        direction = 'left'
        x = x + 1;
        y = y;
    }

    while (current < total) {calculateSideLength();
        switch (direction) {
            case 'left':
                left();
                break;
            case 'bottom':
                bottom();
                break;
            case 'right':
                right();
                break;
            case 'top':
                top();
                break;                
        }
        turnsNumber += 1
    }


    return result
};
退出移动版