当前位置:网站首页>Spiral matrix

Spiral matrix

2020-12-07 19:34:12 Zhang Yue

Preface

Spiral matrix I,II,III The antithesis of . All three problems are solved by simulation .

Spiral matrix I

subject


 Given an inclusion  m x n  A matrix of elements (m  That's ok , n  Column ), Please follow the clockwise spiral sequence , Returns all elements in the matrix .

 Example  1:

 Input :
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
 Output : [1,2,3,6,9,8,7,4,5]

Ideas

From the starting point coordinates [0,0] Start off , Clockwise traversal is divided into four directions , The changes in direction are as follows :

left -- to turn to --> bottom -- to turn to --> right -- to turn to --> top -- to turn to --> left

stay left When moving in a direction , Changes in coordinates ,x Increase gradually 1,y unchanged
stay bottom When moving in a direction , Changes in coordinates ,x unchanged ,y Increase gradually 1
stay right When moving in a direction , Changes in coordinates ,x Gradually self decreasing 1,y unchanged
stay top When moving in a direction , Changes in coordinates ,x unchanged ,y Gradually self decreasing 1

The key to this question is how to turn to

  1. Turn when you go beyond the boundary
  2. Move to the coordinates of the result array that has been added ( Use hash Record those coordinates and add them to the result array )

answer


/**
 * @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);
        //  Avoid infinite recursion 
        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;
};

Spiral matrix II


 Given a positive integer  n, Generate a include  1  To  n2  All the elements , A square matrix in which the elements are spirally arranged in a clockwise order .

 Example :

 Input : 3
 Output :
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Ideas

Ideas and spiral matrices I Agreement , Just this time from traversing the two-dimensional array , Instead of generating a two-dimensional array .

answer

/**
 * @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;
};

Spiral matrix III

image.png

Ideas

The problem is still solved by simulation , It's just that the boundary judgment of turning has changed .

Let's first take the origin coordinates push Enter the result array , And then from bottom Direction begins to traverse ( Change of direction :bottom -> right -> top -> left -> bottom ). In four directions x,y The law of coordinate change and spiral matrix I Agreement . We mainly need to find the law of turning .

image.png

Pass the above figure , Two conclusions can be drawn :

  1. For the former 3 Secondary steering ( from bottom Direction begins ), It's all moving in coordinates 2 Then turn to
  2. Then the turn , It's all coordinate motion 3 + n Then turn to (n The beginning is equal to 0). When the number of turns accumulates 2 Next time ,n Need to grow up 1

answer


/**
 * @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; //  Every interval 2 The next turn , The side length needs to be added 1( But before 3 The second is all 2,3 And then it's the law )
    let direction = 'bottom' // left -> bottom -> right -> top -> left  The order of direction change 
    let sideLength = 2;
    let x = c0;
    let y = r0;

    //  Judge whether the coordinates are legal 
    const isLegal = () => {
        if (x < 0 || y < 0 || x >= C || y >= R) {
            return false;
        } else {
            current += 1;
            return true;
        }
    }

    //  First try to add the coordinates of the starting point 
    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
};

版权声明
本文为[Zhang Yue]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207193309562r.html