当前位置:网站首页>螺旋矩阵

螺旋矩阵

2020-12-07 19:34:12 张越

前言

螺旋矩阵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

image.png

思路

本题依然使用模拟法解决,只是转向的边界判断有所改变。

我们首先将原点坐标push进入结果数组中,然后从bottom方向开始遍历(方向的变化:bottom -> right -> top -> left -> bottom )。在四个方向上x,y坐标变化的规律和螺旋矩阵I一致。我们主要是需要找到转向的规律。

image.png

通过上图,可以得出两个结论:

  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
};

版权声明
本文为[张越]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000038404402