Leetcode: 0051-0060题速览

Leetcode: 0051-0060题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

 

示例 1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[[“Q”]]

 

提示：

• 1 <= n <= 9

难度：困难

标签：数组,回溯

解法

方法一：DFS(回溯)

我们定义三个数组 $col$, $dg$ 和 $udg$，分别表示列、正对角线和反对角线上的是否有皇后，如果位置 $(i,j)$ 有皇后，那么 $col[j]$, $dg[i+j]$ 和 $udg[n-i+j]$ 都为 $1$。另外，我们用一个数组 $g$ 记录当前棋盘的状态，初始时 $g$ 中的所有元素都是 '.'。

接下来，我们定义一个函数 $dfs(i)$，表示从第 $i$ 行开始放置皇后。

在 $dfs(i)$ 中，如果 $i=n$，说明我们已经完成了所有皇后的放置，我们将当前 $g$ 放入答案数组中，递归结束。

否则，我们枚举当前行的每一列 $j$，如果位置 $(i,j)$ 没有皇后，即 $col[j]$, $dg[i+j]$ 和 $udg[n-i+j]$ 都为 $0$，那么我们可以放置皇后，即把 $g[i][j]$ 改为 'Q'，并将 $col[j]$, $dg[i+j]$ 和 $udg[n-i+j]$ 都置为 $1$，然后继续搜索下一行，即调用 $dfs(i+1)$，递归结束后，我们需要将 $g[i][j]$ 改回 '.' 并将 $col[j]$, $dg[i+j]$ 和 $udg[n-i+j]$ 都置为 $0$。

在主函数中，我们调用 $dfs(0)$ 开始递归，最后返回答案数组即可。

时间复杂度 $(n^2\times n!)$，空间复杂度 $O(n)$。其中 $n$ 是题目给定的整数。

Python3

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def dfs(i: int):if i == n:ans.append(["".join(row) for row in g])returnfor j in range(n):if col[j] + dg[i + j] + udg[n - i + j] == 0:g[i][j] = "Q"col[j] = dg[i + j] = udg[n - i + j] = 1dfs(i + 1)col[j] = dg[i + j] = udg[n - i + j] = 0g[i][j] = "."ans = []g = [["."] * n for _ in range(n)]col = [0] * ndg = [0] * (n << 1)udg = [0] * (n << 1)dfs(0)return ans

Java

class Solution {private List<List<String>> ans = new ArrayList<>();private int[] col;private int[] dg;private int[] udg;private String[][] g;private int n;public List<List<String>> solveNQueens(int n) {this.n = n;col = new int[n];dg = new int[n << 1];udg = new int[n << 1];g = new String[n][n];for (int i = 0; i < n; ++i) {Arrays.fill(g[i], ".");}dfs(0);return ans;}private void dfs(int i) {if (i == n) {List<String> t = new ArrayList<>();for (int j = 0; j < n; ++j) {t.add(String.join("", g[j]));}ans.add(t);return;}for (int j = 0; j < n; ++j) {if (col[j] + dg[i + j] + udg[n - i + j] == 0) {g[i][j] = "Q";col[j] = dg[i + j] = udg[n - i + j] = 1;dfs(i + 1);col[j] = dg[i + j] = udg[n - i + j] = 0;g[i][j] = ".";}}}
}

C++

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<int> col(n);vector<int> dg(n << 1);vector<int> udg(n << 1);vector<vector<string>> ans;vector<string> t(n, string(n, '.'));function<void(int)> dfs = [&](int i) -> void {if (i == n) {ans.push_back(t);return;}for (int j = 0; j < n; ++j) {if (col[j] + dg[i + j] + udg[n - i + j] == 0) {t[i][j] = 'Q';col[j] = dg[i + j] = udg[n - i + j] = 1;dfs(i + 1);col[j] = dg[i + j] = udg[n - i + j] = 0;t[i][j] = '.';}}};dfs(0);return ans;}
};

---

52. N 皇后 II

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

 

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

 

提示：

• 1 <= n <= 9

难度：困难

标签：回溯

解法

方法一：回溯

我们设计一个函数 $dfs(i)$，表示从第 $i$ 行开始搜索，搜索到的结果累加到答案中。

在第 $i$ 行，我们枚举第 $i$ 行的每一列，如果当前列不与前面已经放置的皇后发生冲突，那么我们就可以放置一个皇后，然后继续搜索下一行，即调用 $dfs(i+1)$。

如果发生冲突，那么我们就跳过当前列，继续枚举下一列。

判断是否发生冲突，我们需要用三个数组分别记录每一列、每一条正对角线、每一条反对角线是否已经放置了皇后。

具体地，我们用 $cols$ 数组记录每一列是否已经放置了皇后，用 $dg$ 数组记录每一条正对角线是否已经放置了皇后，用 $udg$ 数组记录每一条反对角线是否已经放置了皇后。

时间复杂度 $O(n!)$，空间复杂度 $O(n)$。其中 $n$ 是皇后的数量。

Python3

class Solution:def totalNQueens(self, n: int) -> int:def dfs(i: int):if i == n:nonlocal ansans += 1returnfor j in range(n):a, b = i + j, i - j + nif cols[j] or dg[a] or udg[b]:continuecols[j] = dg[a] = udg[b] = Truedfs(i + 1)cols[j] = dg[a] = udg[b] = Falsecols = [False] * 10dg = [False] * 20udg = [False] * 20ans = 0dfs(0)return ans

Java

class Solution {private int n;private int ans;private boolean[] cols = new boolean[10];private boolean[] dg = new boolean[20];private boolean[] udg = new boolean[20];public int totalNQueens(int n) {this.n = n;dfs(0);return ans;}private void dfs(int i) {if (i == n) {++ans;return;}for (int j = 0; j < n; ++j) {int a = i + j, b = i - j + n;if (cols[j] || dg[a] || udg[b]) {continue;}cols[j] = true;dg[a] = true;udg[b] = true;dfs(i + 1);cols[j] = false;dg[a] = false;udg[b] = false;}}
}

C++

class Solution {
public:int totalNQueens(int n) {bitset<10> cols;bitset<20> dg;bitset<20> udg;int ans = 0;function<void(int)> dfs = [&](int i) {if (i == n) {++ans;return;}for (int j = 0; j < n; ++j) {int a = i + j, b = i - j + n;if (cols[j] || dg[a] || udg[b]) continue;cols[j] = dg[a] = udg[b] = 1;dfs(i + 1);cols[j] = dg[a] = udg[b] = 0;}};dfs(0);return ans;}
};

---

53. 最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

 

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

 

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

难度：中等

标签：数组,分治,动态规划

解法

方法一：动态规划

我们定义 $f[i]$ 表示以元素 $nums[i]$ 为结尾的连续子数组的最大和，初始时 $f[0]=nums[0]$，那么最终我们要求的答案即为 ${\max }_{0\le i<n}f[i]$。

考虑 $f[i]$，其中 $i\ge 1$，它的状态转移方程为：

f [ i ] = max ⁡ { f [ i − 1 ] + n u m s [ i ] , n u m s [ i ] } f[i] = \max \{ f[i - 1] + nums[i], nums[i] \} f[i]=max{f[i−1]+nums[i],nums[i]}

也即：

f [ i ] = max ⁡ { f [ i − 1 ] , 0 } + n u m s [ i ] f[i] = \max \{ f[i - 1], 0 \} + nums[i] f[i]=max{f[i−1],0}+nums[i]

由于 $f[i]$ 只与 $f[i-1]$ 有关系，因此我们可以只用一个变量 $f$ 来维护对于当前 $f[i]$ 的值是多少，然后进行状态转移即可。答案为 ${\max }_{0\le i<n}f$。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。我们只需要遍历一遍数组即可求得答案。空间复杂度 $O(1)$，我们只需要常数空间存放若干变量。

Python3

class Solution:def maxSubArray(self, nums: List[int]) -> int:ans = f = nums[0]for x in nums[1:]:f = max(f, 0) + xans = max(ans, f)return ans

Java

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];for (int i = 1, f = nums[0]; i < nums.length; ++i) {f = Math.max(f, 0) + nums[i];ans = Math.max(ans, f);}return ans;}
}

C++

class Solution {
public:int maxSubArray(vector<int>& nums) {int ans = nums[0], f = nums[0];for (int i = 1; i < nums.size(); ++i) {f = max(f, 0) + nums[i];ans = max(ans, f);}return ans;}
};

---

54. 螺旋矩阵

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

难度：中等

标签：数组,矩阵,模拟

解法

方法一：模拟

我们用 $i$ 和 $j$ 分别表示当前访问到的元素的行和列，用 $k$ 表示当前的方向，用数组或哈希表 $vis$ 记录每个元素是否被访问过。每次我们访问到一个元素后，将其标记为已访问，然后按照当前的方向前进一步，如果前进一步后发现越界或者已经访问过，则改变方向继续前进，直到遍历完整个矩阵。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

对于访问过的元素，我们也可以将其值加上一个常数 $300$，这样就不需要额外的 $vis$ 数组或哈希表来记录是否访问过了，从而将空间复杂度降低到 $O(1)$。

Python3

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m, n = len(matrix), len(matrix[0])dirs = (0, 1, 0, -1, 0)i = j = k = 0ans = []vis = set()for _ in range(m * n):ans.append(matrix[i][j])vis.add((i, j))x, y = i + dirs[k], j + dirs[k + 1]if not 0 <= x < m or not 0 <= y < n or (x, y) in vis:k = (k + 1) % 4i = i + dirs[k]j = j + dirs[k + 1]return ans

Java

class Solution {public List<Integer> spiralOrder(int[][] matrix) {int m = matrix.length, n = matrix[0].length;int[] dirs = {0, 1, 0, -1, 0};int i = 0, j = 0, k = 0;List<Integer> ans = new ArrayList<>();boolean[][] vis = new boolean[m][n];for (int h = m * n; h > 0; --h) {ans.add(matrix[i][j]);vis[i][j] = true;int x = i + dirs[k], y = j + dirs[k + 1];if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {k = (k + 1) % 4;}i += dirs[k];j += dirs[k + 1];}return ans;}
}

C++

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();int dirs[5] = {0, 1, 0, -1, 0};int i = 0, j = 0, k = 0;vector<int> ans;bool vis[m][n];memset(vis, false, sizeof(vis));for (int h = m * n; h; --h) {ans.push_back(matrix[i][j]);vis[i][j] = true;int x = i + dirs[k], y = j + dirs[k + 1];if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y]) {k = (k + 1) % 4;}i += dirs[k];j += dirs[k + 1];}return ans;}
};

---

55. 跳跃游戏

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

 

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

难度：中等

标签：贪心,数组,动态规划

解法

方法一：贪心

我们用变量 $mx$ 维护当前能够到达的最远下标，初始时 $mx=0$。

我们从左到右遍历数组，对于遍历到的每个位置 $i$，如果 $mx<i$，说明当前位置无法到达，直接返回 false。否则，我们可以通过跳跃从位置 $i$ 到达的最远位置为 $i+nums[i]$，我们用 $i+nums[i]$ 更新 $mx$ 的值，即 $mx=\max (mx,i+nums[i])$。

遍历结束，直接返回 true。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

相似题目：

• 45. 跳跃游戏 II
• 1024. 视频拼接
• 1326. 灌溉花园的最少水龙头数目

Python3

class Solution:def canJump(self, nums: List[int]) -> bool:mx = 0for i, x in enumerate(nums):if mx < i:return Falsemx = max(mx, i + x)return True

Java

class Solution {public boolean canJump(int[] nums) {int mx = 0;for (int i = 0; i < nums.length; ++i) {if (mx < i) {return false;}mx = Math.max(mx, i + nums[i]);}return true;}
}

C++

class Solution {
public:bool canJump(vector<int>& nums) {int mx = 0;for (int i = 0; i < nums.size(); ++i) {if (mx < i) {return false;}mx = max(mx, i + nums[i]);}return true;}
};

---

56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

 

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

难度：中等

标签：数组,排序

解法

方法一：排序 + 一次遍历

我们可以将区间按照左端点升序排列，然后遍历区间进行合并操作。

具体的合并操作如下。

我们先将第一个区间加入答案，然后依次考虑之后的每个区间：

• 如果答案数组中最后一个区间的右端点小于当前考虑区间的左端点，说明两个区间不会重合，因此我们可以直接将当前区间加入答案数组末尾；
• 否则，说明两个区间重合，我们需要用当前区间的右端点更新答案数组中最后一个区间的右端点，将其置为二者的较大值。

最后，我们返回答案数组即可。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为区间个数。

Python3

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()ans = []st, ed = intervals[0]for s, e in intervals[1:]:if ed < s:ans.append([st, ed])st, ed = s, eelse:ed = max(ed, e)ans.append([st, ed])return ans

Java

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));int st = intervals[0][0], ed = intervals[0][1];List<int[]> ans = new ArrayList<>();for (int i = 1; i < intervals.length; ++i) {int s = intervals[i][0], e = intervals[i][1];if (ed < s) {ans.add(new int[] {st, ed});st = s;ed = e;} else {ed = Math.max(ed, e);}}ans.add(new int[] {st, ed});return ans.toArray(new int[ans.size()][]);}
}

C++

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int st = intervals[0][0], ed = intervals[0][1];vector<vector<int>> ans;for (int i = 1; i < intervals.size(); ++i) {if (ed < intervals[i][0]) {ans.push_back({st, ed});st = intervals[i][0];ed = intervals[i][1];} else {ed = max(ed, intervals[i][1]);}}ans.push_back({st, ed});return ans;}
};

---

57. 插入区间

题目描述

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

 

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

 

提示：

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals 根据 starti 按 升序 排列
• newInterval.length == 2
• 0 <= start <= end <= 105

难度：中等

标签：数组

解法

方法一：排序 + 区间合并

我们可以先将新区间 newInterval 加入到区间列表 intervals 中，然后按照区间合并的常规方法进行合并。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是区间的数量。

Python3

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:def merge(intervals: List[List[int]]) -> List[List[int]]:intervals.sort()ans = [intervals[0]]for s, e in intervals[1:]:if ans[-1][1] < s:ans.append([s, e])else:ans[-1][1] = max(ans[-1][1], e)return ansintervals.append(newInterval)return merge(intervals)

Java

class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {int[][] newIntervals = new int[intervals.length + 1][2];for (int i = 0; i < intervals.length; ++i) {newIntervals[i] = intervals[i];}newIntervals[intervals.length] = newInterval;return merge(newIntervals);}private int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> ans = new ArrayList<>();ans.add(intervals[0]);for (int i = 1; i < intervals.length; ++i) {int s = intervals[i][0], e = intervals[i][1];if (ans.get(ans.size() - 1)[1] < s) {ans.add(intervals[i]);} else {ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e);}}return ans.toArray(new int[ans.size()][]);}
}

C++

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {intervals.emplace_back(newInterval);return merge(intervals);}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ans;ans.emplace_back(intervals[0]);for (int i = 1; i < intervals.size(); ++i) {if (ans.back()[1] < intervals[i][0]) {ans.emplace_back(intervals[i]);} else {ans.back()[1] = max(ans.back()[1], intervals[i][1]);}}return ans;}
};

---

58. 最后一个单词的长度

题目描述

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

 

示例 1：

输入：s = “Hello World”
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = " fly me to the moon "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = “luffy is still joyboy”
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

 

提示：

• 1 <= s.length <= 104
• s 仅有英文字母和空格 ' ' 组成
• s 中至少存在一个单词

难度：简单

标签：字符串

解法

方法一：逆向遍历 + 双指针

我们从字符串 $s$ 末尾开始遍历，找到第一个不为空格的字符，即为最后一个单词的最后一个字符，下标记为 $i$。然后继续向前遍历，找到第一个为空格的字符，即为最后一个单词的第一个字符的前一个字符，记为 $j$。那么最后一个单词的长度即为 $i-j$。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 长度。空间复杂度 $O(1)$。

Python3

class Solution:def lengthOfLastWord(self, s: str) -> int:i = len(s) - 1while i >= 0 and s[i] == ' ':i -= 1j = iwhile j >= 0 and s[j] != ' ':j -= 1return i - j

Java

class Solution {public int lengthOfLastWord(String s) {int i = s.length() - 1;while (i >= 0 && s.charAt(i) == ' ') {--i;}int j = i;while (j >= 0 && s.charAt(j) != ' ') {--j;}return i - j;}
}

C++

class Solution {
public:int lengthOfLastWord(string s) {int i = s.size() - 1;while (~i && s[i] == ' ') {--i;}int j = i;while (~j && s[j] != ' ') {--j;}return i - j;}
};

---

59. 螺旋矩阵 II

题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

难度：中等

标签：数组,矩阵,模拟

解法

方法一：模拟

直接模拟螺旋矩阵的生成过程。

定义一个二维数组 ans，用于存储螺旋矩阵。用 i 和 j 分别表示当前位置的行号和列号，用 k 表示当前的方向编号，dirs 表示方向编号与方向的对应关系。

从 1 开始，依次填入矩阵中的每个位置。每次填入一个位置后，计算下一个位置的行号和列号，如果下一个位置不在矩阵中或者已经被填过，则改变方向，再计算下一个位置的行号和列号。

时间复杂度 $O(n^2)$，其中 $n$ 是矩阵的边长。忽略输出数组不计，空间复杂度 $O(1)$。

Python3

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:ans = [[0] * n for _ in range(n)]dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))i = j = k = 0for v in range(1, n * n + 1):ans[i][j] = vx, y = i + dirs[k][0], j + dirs[k][1]if x < 0 or y < 0 or x >= n or y >= n or ans[x][y]:k = (k + 1) % 4x, y = i + dirs[k][0], j + dirs[k][1]i, j = x, yreturn ans

Java

class Solution {public int[][] generateMatrix(int n) {int[][] ans = new int[n][n];int i = 0, j = 0, k = 0;int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};for (int v = 1; v <= n * n; ++v) {ans[i][j] = v;int x = i + dirs[k][0], y = j + dirs[k][1];if (x < 0 || y < 0 || x >= n || y >= n || ans[x][y] > 0) {k = (k + 1) % 4;x = i + dirs[k][0];y = j + dirs[k][1];}i = x;j = y;}return ans;}
}

C++

class Solution {
public:const int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};vector<vector<int>> generateMatrix(int n) {vector<vector<int>> ans(n, vector<int>(n));int i = 0, j = 0, k = 0;for (int v = 1; v <= n * n; ++v) {ans[i][j] = v;int x = i + dirs[k][0], y = j + dirs[k][1];if (x < 0 || y < 0 || x >= n || y >= n || ans[x][y]) {k = (k + 1) % 4;x = i + dirs[k][0], y = j + dirs[k][1];}i = x, j = y;}return ans;}
};

---

60. 排列序列

题目描述

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

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

示例 1：

输入：n = 3, k = 3
输出：“213”

示例 2：

输入：n = 4, k = 9
输出：“2314”

示例 3：

输入：n = 3, k = 1
输出：“123”

提示：

• 1 <= n <= 9
• 1 <= k <= n!

难度：困难

标签：递归,数学

解法

方法一：枚举

我们知道，集合 $[1,2,..n]$ 一共有 $n!$ 种排列，如果我们确定首位，那剩余位能组成的排列数量为 $(n-1)!$。

因此，我们枚举每一位 $i$，如果此时 $k$ 大于当前位置确定后的排列数量，那么我们可以直接减去这个数量；否则，说明我们找到了当前位置的数。

对于每一位 $i$，其中 $0\le i<n$，剩余位能组成的排列数量为 $(n-i-1)!$，我们记为 $fact$。过程中已使用的数记录在 vis 中。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

Python3

class Solution:def getPermutation(self, n: int, k: int) -> str:ans = []vis = [False] * (n + 1)for i in range(n):fact = 1for j in range(1, n - i):fact *= jfor j in range(1, n + 1):if not vis[j]:if k > fact:k -= factelse:ans.append(str(j))vis[j] = Truebreakreturn ''.join(ans)

Java

class Solution {public String getPermutation(int n, int k) {StringBuilder ans = new StringBuilder();boolean[] vis = new boolean[n + 1];for (int i = 0; i < n; ++i) {int fact = 1;for (int j = 1; j < n - i; ++j) {fact *= j;}for (int j = 1; j <= n; ++j) {if (!vis[j]) {if (k > fact) {k -= fact;} else {ans.append(j);vis[j] = true;break;}}}}return ans.toString();}
}

C++

class Solution {
public:string getPermutation(int n, int k) {string ans;bitset<10> vis;for (int i = 0; i < n; ++i) {int fact = 1;for (int j = 1; j < n - i; ++j) fact *= j;for (int j = 1; j <= n; ++j) {if (vis[j]) continue;if (k > fact)k -= fact;else {ans += to_string(j);vis[j] = 1;break;}}}return ans;}
};

---