【LeetCode算法系列题解】第51~55题

LeetCode 51. N 皇后（困难）

【题目描述】

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
N 皇后问题研究的是如何将 N 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n，返回所有不同的 N 皇后问题的解决方案。
每一种解法包含一个不同的 N 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

【示例1】

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

【示例2】

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

【提示】

$1\le n\le 9$

【分析】

---

N 皇后裸题，DFS 爆搜每一行能放置皇后的位置即可，可以使用 col[i]、dg[i] 以及 udg[i] 分别表示某一列、正对角线与反对角线是否能放皇后（由于我们是按行枚举的因此不用判断某一行是否可以放置）。由于正对角线为 $y=x+b$，因此可以用 $y-x$ 唯一确定一条正对角线（可以通过统一加上 $n$ 避免越界）；同理可以用 $y+x$ 确定一条反对角线。

---

【代码】

class Solution {
public:vector<vector<string>> res;vector<bool> col, dg, udg;vector<vector<string>> solveNQueens(int n) {col = vector<bool>(n);dg = udg = vector<bool>(n << 1);  // 对角线的数量为2n-1vector<string> board(n, string(n, '.'));  // 初始化棋盘全为'.'dfs(board, 0);  // 从第0行开始搜return res;}void dfs(vector<string>& board, int x){if (x == board.size()) { res.push_back(board); return; }for (int y = 0; y < board.size(); y++)if (!col[y] && !dg[y - x + board.size()] && !udg[y + x]){board[x][y] = 'Q';col[y] = dg[y - x + board.size()] = udg[y + x] = true;dfs(board, x + 1);col[y] = dg[y - x + board.size()] = udg[y + x] = false;board[x][y] = '.';}}
};

LeetCode 52. N 皇后 II（困难）

【题目描述】

N 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n，返回 N 皇后问题不同的解决方案的数量。

【示例1】

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

【示例2】

输入：n = 1
输出：1

【提示】

$1\le n\le 9$

【分析】

---

与上一题一样，只需要记录方案数而不需要记录整个棋盘。

---

【代码】

class Solution {
public:vector<bool> col, dg, udg;int totalNQueens(int n) {col = vector<bool>(n);dg = udg = vector<bool>(n << 1);return dfs(n, 0);}int dfs(int n, int x){if (x == n) return 1;int res = 0;for (int y = 0; y < n; y++)if (!col[y] && !dg[y - x + n] && !udg[y + x]){col[y] = dg[y - x + n] = udg[y + x] = true;res += dfs(n, x + 1);col[y] = dg[y - x + n] = udg[y + x] = false;}return res;}
};

LeetCode 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\le nums.length\le 10^5$
$-10^4\le nums[i]\le 10^4$

【分析】

---

我们先分析 $O(n)$ 的算法，用动态规划考虑：令 f[i] 表示所有以 nums[i] 结尾的区间中的最大和，那么状态转移有以下两种情况：

• 区间长度等于1：f[i] = nums[i]；
• 区间长度大于1：f[i] = f[i - 1] + nums[i]

因此可以得到状态转移方程为：f[i] = max(nums[i], f[i - 1] + nums[i]) = nums[i] + max(0, f[i - 1])，由于 f[i] 只和 f[i - 1] 有关，因此我们可以只使用一个变量记录 f[i - 1] 的值即可。

现在我们考虑如何用分治法求解，其实分治法就是线段树维护动态最大字段和的简化版，当前数组的最大子段所在的区间可能有以下几种情况：

• 在左子区间中，结果即为左子区间的最大子段；
• 在右子区间中，结果即为右子区间的最大子段；
• 横跨左右两个子区间，结果即为左子区间的最大后缀加上右子区间的最大前缀；

求解最大前缀与最大后缀时可能还会有以下几种情况：

• 最大前缀横跨左右两个子区间，那么最大前缀为左子区间的总和加上右子区间的最大前缀；
• 最大后缀横跨左右两个子区间，那么最大后缀为右子区间的总和加上左子区间的最大后缀；

因此我们需要处理出每个区间的最大子段、最大前缀、最大后缀以及总长度这四个信息。

---

【代码】

【动态规划实现】

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

【分治法实现】

class Solution {
public:struct Node {int sum, lmax, rmax, tmax;  // 区间和，最大前缀，最大后缀，最大子段和};int maxSubArray(vector<int>& nums) {auto t = build(nums, 0, nums.size() - 1);return t.tmax;}Node build(vector<int>& nums, int l, int r){if (l == r) return { nums[l], nums[l], nums[l], nums[l] };  // 递归到了长度为1的结点int mid = l + r >> 1;auto lnode = build(nums, l, mid), rnode = build(nums, mid + 1, r);// 线段树中的pushup操作Node res;res.sum = lnode.sum + rnode.sum;res.lmax = max(lnode.lmax, lnode.sum + rnode.lmax);res.rmax = max(rnode.rmax, rnode.sum + lnode.rmax);res.tmax = max(max(lnode.tmax, rnode.tmax), lnode.rmax + rnode.lmax);return res;}
};

LeetCode 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\le m,n\le 10$
$-100\le matrix[i][j]\le 100$

【分析】

---

分别设置向右、向下、向左、向上四个方向向量，然后模拟一遍即可，走出界或是已经遍历过了改变一下方向即可。

---

【代码】

class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int n = matrix.size(), m = matrix[0].size();int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };vector<int> res;for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i++)  // 总共遍历n*m个点{res.push_back(matrix[x][y]);matrix[x][y] = INT_MIN;  // 遍历过的数修改为INT_MINint nx = x + dx[d], ny = y + dy[d];if (nx < 0 || nx >= n || ny < 0 || ny >= m || matrix[nx][ny] == INT_MIN) d = (d + 1) % 4;x += dx[d], y += dy[d];}return res;}
};

LeetCode 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\le nums.length\le 10^4$
$0\le nums[i]\le 10^5$

【分析】

---

本题和第45题差不多，我们从小到大枚举 $i$，并同时维护 $i$ 之前所有点能跳到的最远距离 $max\_dis$，如果 max_dis < i，说明 $i$ 之前没有点能够跳到 $i$ 了，直接返回 false 即可。

---

【代码】

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