技术干货（四）「LeetCode」51 - 60题详解( 三 ) 51.N皇后n皇后问题研究的是如何

示例:
输入: 3输出:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]向量位移public int[][] generateMatrix(int n) {int[][] res = new int[n][n];int[] dx = {0, 1, 0, -1};int[] dy = {1, 0, -1, 0};int x = 0, y = 0, d = 0;for(int i = 1; i <= n * n; i ++){res[x][y] = i;int a = x + dx[d], b = y + dy[d];// 转向的条件 1. 越界 2. 走过if(a < 0 || b < 0 || a >= n || b >= n || res[a][b] != 0){d = (d + 1) % 4;a = x + dx[d]; b = y + dy[d];}// 更新下一个点的位置x = a; y = b;}return res;}普通模拟public int[][] generateMatrix(int n) {// 设定左、右、上、下边界int l = 0, r = n - 1, t = 0, b = n - 1;int[][] res = new int[n][n];int num = 1;while(num <= n * n){for(int i = l; i <= r; i++) res[t][i] = num++;t++;for(int i = t; i <= b; i++) res[i][r] = num++;r--;for(int i = r; i >= l; i--) res[b][i] = num++;b--;for(int i = b; i >= t; i--) res[i][l] = num++;l++;}return res;}60. 第k个排列给出集合 [1,2,3,…,*n*] ，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k ，返回第 k 个排列。
说明：

给定 n 的范围是 [1, 9] 。
给定 k 的范围是[1, n!] 。

示例 1:
输入: n = 3, k = 3输出: "213"示例 2:
输入: n = 4, k = 9输出: "2314"回溯法

class Solution {boolean[] used; // 记录数字是否用过int[] factorial; //阶乘数组int n , k;public String getPermutation(int n, int k) {// 初始化操作this.n = n;this.k = k;calculateFactorial(n);used = new boolean[n + 1];StringBuilder path = new StringBuilder();dfs(path, 0);return path.toString();}void dfs(StringBuilder path, int u){if(u == n) return;// 还未确定的数字的全排列个数int cnt = factorial[n - 1 - u];for(int i = 1; i <= n; i ++){if(used[i]) continue;if(cnt < k){k -= cnt;continue;}path.append(i);used[i] = true;dfs(path , u + 1);// return 后续没有必要再遍历了return;}}// 计算阶乘数组void calculateFactorial(int n){factorial = new int[n + 1];factorial[0] = 1;for(int i = 1; i <= n; i++) factorial[i] = factorial[i - 1] * i;}}

数学模拟

public class Solution {public String getPermutation(int n, int k) {// 注意：相当于在 n 个数字的全排列中找到下标为 k - 1 的那个数 ， 因此 k 先减 1k --;int[] factorial = new int[n];factorial[0] = 1;// 先算出所有的阶乘值for (int i = 1; i < n; i++) {factorial[i] = factorial[i - 1] * i;}// 这里使用数组或者链表都行List nums = new LinkedList<>();for (int i = 1; i <= n; i++) {nums.add(i);}StringBuilder stringBuilder = new StringBuilder();// i 表示剩余的数字个数 ， 初始化为 n - 1for (int i = n - 1; i >= 0; i--) {int index = k / factorial[i] ;stringBuilder.append(nums.remove(index));k -= index * factorial[i];}return stringBuilder.toString();}}

原文链接：
如果觉得本文对你有帮助，可以转发关注支持一下