算法问题——螺旋矩阵问题

54. 螺旋矩阵

/**
 * Copyright (C), 2018-2020
 * FileName: 螺旋矩阵
 * Author:   xjl
 * Date:     2020/10/1 9:19
 * Description:
 */
package 牛客面试必会100题;

import org.junit.Test;

import java.util.ArrayList;

public class 螺旋矩阵 {

    @Test
    public void test() {
        ArrayList list = spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}});
        System.out.println(list);
    }

    /**
     * 螺旋矩阵 使用的就是模拟的思想
     *
     * @param matrix
     * @return
     */
    public ArrayList spiralOrder(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return new ArrayList();
        int n = matrix[0].length;
        boolean[][] vis = new boolean[m][n];
        //表示方向 已经是 设计好的
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        //表示的是起始位置
        int x = 0;
        int y = 0;
        //表示转向的标志
        int d = 0;
        //存放结果
        ArrayList list = new ArrayList();
        while (list.size() < m * n) {
            list.add(matrix[x][y]);
            vis[x][y] = true;
            int nx = x + dx[d];
            int ny = y + dy[d];
            //表示的是可以开始方向
            if (nx < m && nx >= 0 && ny < n && ny >= 0 && !vis[nx][ny]) {
                x = nx;
                y = ny;
            } else {
                d = (d + 1) % 4;
                nx = x + dx[d];
                ny = y + dy[d];
                x = nx;
                y = ny;
            }
        }
        return list;
    }
}

59. 螺旋矩阵 II

/**
 * Copyright (C), 2018-2020
 * FileName: 螺旋矩阵II
 * Author:   xjl
 * Date:     2020/10/1 9:45
 * Description:
 */
package 牛客面试必会100题;

import org.junit.Test;

public class 螺旋矩阵II {

    @Test
    public void test() {
        int[][] ints = generateMatrix(3);
        for (int[] a : ints) {
            for (int num : a) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    /**
     * 填充数字
     *
     * @param n
     * @return
     */

    public int[][] generateMatrix(int n) {
        if (n == 0) return new int[][]{};
        int[][] arry = new int[n][n];
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};

        boolean[][] vis = new boolean[n][n];

        int d = 0;

        int x = 0;
        int y = 0;
        for (int i = 1; i = 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) {
                x = nx;
                y = ny;
            } else {
                d = (d + 1) % 4;
                nx = x + dx[d];
                ny = y + dy[d];
                x = nx;
                y = ny;
            }
        }
        return arry;
    }
}

885. 螺旋矩阵 III

/**
 * Copyright (C), 2018-2020
 * FileName: 螺旋矩阵II
 * Author:   xjl
 * Date:     2020/10/1 9:45
 * Description:
 */
package 牛客面试必会100题;

import org.junit.Test;

public class 螺旋矩阵III {

    @Test
    public void test() {
        int[][] res = spiralMatrixIII(5, 6, 1, 4);
        for (int[] a : res) {
            for (int i : a) {
                System.out.print(i+" ");
            }
            System.out.println();
        }

    }

    /**
     * 也是螺旋矩阵的思想
     *
     * @param R
     * @param C
     * @param r0
     * @param c0
     * @return
     */
    public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
        int total = R * C;
        int x = r0, y = c0, d = 0;

        int[][] result = new int[R * C][2];
        boolean[][] vis = new boolean[R][C];
        int index = 0;
        int cnt = 1;
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        if (x >= 0 && x < R && y >= 0 && y < C) {
            result[index][0] = x;
            result[index][1] = y;
            index += 1;
            total--;
        }
        while (total > 0) {
            int len = (cnt - 1) / 2 + 1;
            for (int i = 1; i = 0 && x < R && y >= 0 && y < C) {
                    result[index][0] = x;
                    result[index][1] = y;
                    index += 1;
                    total--;
                }
            }
            d = (d + 1) % 4;
            cnt++;
        }
        return result;
    }
}