LeetCode 60. Permutation Sequence

Problem

LeetCode 54. Spiral Matrix

1. 题目简述

给出一个m * n的矩阵，将其螺旋打印出来。例如：

Example 1:

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

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

2. 算法思路

相关问题：

1. LeetCode 59. Spiral Matrix II

极其经典的螺旋打印的问题，这里的暴力做法其实是很麻烦的，用方向数组比较好！

回溯法

这里问题其实是在于，如何判断当前行所放的皇后是否合理，这里我的做法是直接将二维的棋盘表示了出来，然后用board[i - x][j - x]表示左上到右下的对角线，用board[i - x][j + x]表示右上到左下的对角线（注意边界）。

但是其实还有另外一种更为节省空间的做法（其实必要性不大），用bool型数组来表示每一行、每一列、每一个对角线是否已经共存在了一个皇后。如果已知n，那么每一组（左上到右下算一组，左下到右上算一组）对角线的个数也是已知的，2n - 1，然后用[i, j]做一个映射即可。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 也就是说每一行，每一列，每一个斜线上都不能有任意两个皇后。每一行和每一列都还算好判断，斜线上要怎么判断呢？可以用[i][j]来做映射。但是这里我打算采用一个二维数组来做计算，写起来方便。

        int[][] board = new int[n][n];
        List<List<String>> res = new ArrayList();

        backtrack(0, n, board, res);

        return res;
    }

    private void backtrack(int line, int n, int[][] board, List<List<String>> res) {
        // 判断一下是否已经填完了最后一层，如果是，则向结果集中添加一个solution
        if (line == n) {
            List<String> solution = new ArrayList();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(board[i][j] == 0 ? "." : "Q");
                }
                solution.add(sb.toString());
            }
            res.add(solution);
            return;
        }

        // 如果没有填完最后一层，则填line这一层，从0到n-1逐个尝试，每次尝试出一个valid的就继续向下一层出发。
        for (int i = 0; i < n; i++) {
            board[line][i] = 1;
            if (checkValid(board, line, i)) {
                backtrack(line + 1, n, board, res);
            }
            board[line][i] = 0;
        }

        return;
    }

    private boolean checkValid(int[][] board, int line, int pos) {
        // 检查第line行，pos位置放queen是否合法（同一行无须检查）
        int n = board.length;

        // 检查同一列
        for (int i = 0; i < line; i++) {
            if (board[i][pos] == 1) {
                return false;
            }
        }

        // 检查左上到右下的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // 检查左下到右上的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }
}