更新时间：2025-04-09
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
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 <= n <= 9
方法一：回溯法 + 剪枝优化（行列、对角线冲突检测）
通过回溯算法逐行放置皇后，使用三个辅助数组快速检测列、主对角线和副对角线的冲突，极大提升搜索效率。
代码实现(Java)：
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
// 初始化标记数组：列、主对角线、副对角线
boolean[] cols = new boolean[n];
boolean[] mainDiag = new boolean[2 * n - 1]; // 主对角线（左上到右下）
boolean[] subDiag = new boolean[2 * n - 1]; // 副对角线（右上到左下）
int[] queens = new int[n]; // 记录每行皇后的列位置
backtrack(0, queens, cols, mainDiag, subDiag, res, n);
return res;
}
private void backtrack(int row, int[] queens, boolean[] cols,
boolean[] mainDiag, boolean[] subDiag,
List<List<String>> res, int n) {
if (row == n) {
res.add(generateBoard(queens, n));
return;
}
for (int col = 0; col < n; col++) {
// 计算主、副对角线索引
int mainIdx = row - col + n - 1;
int subIdx = row + col;
// 冲突检测
if (cols[col] || mainDiag[mainIdx] || subDiag[subIdx]) continue;
// 放置皇后并标记
cols[col] = true;
mainDiag[mainIdx] = true;
subDiag[subIdx] = true;
queens[row] = col;
// 递归处理下一行
backtrack(row + 1, queens, cols, mainDiag, subDiag, res, n);
// 回溯撤销标记
cols[col] = false;
mainDiag[mainIdx] = false;
subDiag[subIdx] = false;
}
}
// 根据queens数组生成棋盘
private List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
方法二：经典回溯法（逐行检查冲突）
通过逐行放置皇后并检查与之前行的冲突，逻辑更直观但效率略低，适合理解回溯基本原理。
代码实现(Java)：
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
backtrack(0, new int[n], res, n);
return res;
}
private void backtrack(int row, int[] queens, List<List<String>> res, int n) {
if (row == n) {
res.add(generateBoard(queens, n));
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col, queens)) {
queens[row] = col;
backtrack(row + 1, queens, res, n);
}
}
}
// 检查当前位置是否合法
private boolean isValid(int row, int col, int[] queens) {
for (int i = 0; i < row; i++) {
int prevCol = queens[i];
if (prevCol == col || Math.abs(row - i) == Math.abs(col - prevCol)) {
return false;
}
}
return true;
}
private List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] arr = new char[n];
Arrays.fill(arr, '.');
arr[queens[i]] = 'Q';
board.add(new String(arr));
}
return board;
}
}
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 方法一 | O(n!) | O(n) | 快速冲突检测，适合n较大时使用 |
| 方法二 | O(n! * n) | O(n) | 逻辑直观，适合理解回溯原理 |
核心思路：
- 回溯框架：逐行放置皇后，每行尝试所有可能列。
- 冲突检测：
- 方法一：通过三个标记数组实现
O(1)时间检测列、主/副对角线冲突。 - 方法二：通过遍历已放置皇后实现
O(n)时间检测。
- 方法一：通过三个标记数组实现
优化点：
- 使用行列、对角线标记数组将冲突检测复杂度从
O(n)降为O(1)。 - 通过
queens数组记录每行放置位置，避免二维数组操作。
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 <= 10^5-10^4 <= nums[i] <= 10^4
方法一：Kadane算法（动态规划）
维护两个变量：currentMax（当前子数组的最大和）和 maxSum（全局最大和）。遍历数组时，动态决定是扩展当前子数组还是以当前元素重新开始子数组。每次更新 currentMax 和 maxSum。
代码实现(Java)：
public class Solution {
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentMax = nums[0];
for (int i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
maxSum = Math.max(maxSum, currentMax);
}
return maxSum;
}
}
复杂度分析：
- 时间复杂度：
O(n)，每个元素遍历一次。 - 空间复杂度：
O(1)，仅用常数变量。
方法二：分治法
将数组递归分为左右两部分，最大子数组和可能出现在左半部分、右半部分或跨越中点的情况。合并结果时，计算三种情况的最大值。
代码实现(Java)：
public class Solution {
static class Result {
int maxSum;
int leftMax;
int rightMax;
int total;
Result(int maxSum, int leftMax, int rightMax, int total) {
this.maxSum = maxSum;
this.leftMax = leftMax;
this.rightMax = rightMax;
this.total = total;
}
}
public int maxSubArray(int[] nums) {
return divideAndConquer(nums, 0, nums.length - 1).maxSum;
}
private Result divideAndConquer(int[] nums, int left, int right) {
if (left == right) {
return new Result(nums[left], nums[left], nums[left], nums[left]);
}
int mid = left + (right - left) / 2;
Result leftResult = divideAndConquer(nums, left, mid);
Result rightResult = divideAndConquer(nums, mid + 1, right);
int crossSum = leftResult.rightMax + rightResult.leftMax;
int maxSum = Math.max(Math.max(leftResult.maxSum, rightResult.maxSum), crossSum);
int newLeftMax = Math.max(leftResult.leftMax, leftResult.total + rightResult.leftMax);
int newRightMax = Math.max(rightResult.rightMax, rightResult.total + leftResult.rightMax);
int total = leftResult.total + rightResult.total;
return new Result(maxSum, newLeftMax, newRightMax, total);
}
}
复杂度分析：
- 时间复杂度：
O(n log n)，递归深度为log n，每层处理O(n)数据。 - 空间复杂度：
O(log n)，递归调用栈的深度。
方法三：前缀和优化
维护前缀和 prefixSum 和最小前缀和 minPrefix。每次计算当前前缀和与最小前缀的差值，更新最大子数组和。通过跟踪最小前缀，确保每次计算的是最大差值。
代码实现(Java)：
public class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int prefixSum = 0;
int minPrefix = 0;
for (int num : nums) {
prefixSum += num;
maxSum = Math.max(maxSum, prefixSum - minPrefix);
minPrefix = Math.min(minPrefix, prefixSum);
}
return maxSum;
}
}
复杂度分析：
- 时间复杂度：
O(n)，单次遍历数组。 - 空间复杂度：
O(1)，仅用常数变量。
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 <= 10^40 <= nums[i] <= 10^5
方法一：正向贪心（最优解法）
维护一个变量 maxReach 表示当前能到达的最远位置。遍历数组时，如果当前位置 i 在可达范围内，则更新 maxReach。若 maxReach 覆盖最后一个位置，直接返回 true；若遍历中发现 i 超过 maxReach，说明无法到达后续位置，返回 false。
代码实现(Java)：
public class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i > maxReach) return false; // 无法到达当前点
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= n - 1) return true; // 提前终止
}
return true;
}
}
复杂度分析：
- 时间复杂度：
O(n)，每个元素遍历一次。 - 空间复杂度：
O(1)，仅用常数变量。
方法二：逆向贪心
从后向前遍历，维护变量 lastPos 表示需要到达的位置。若当前点 i 能跳到 lastPos，则更新 lastPos 为 i。最终判断 lastPos 是否为起点。
代码实现(Java)：
public class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastPos) { // 能到达目标点
lastPos = i; // 更新目标点为当前点
}
}
return lastPos == 0;
}
}
复杂度分析：
- 时间复杂度：
O(n)，遍历整个数组一次。 - 空间复杂度：
O(1)，仅用常数变量。
方法三：动态规划（仅理论，超时不可用）
用 dp[i] 记录位置 i 是否可达。对每个可达的点 i，标记后续可达的位置。但时间复杂度为 O(n²)，无法处理大输入。
代码实现(Java)：
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 0; i < n; i++) {
if (!dp[i]) continue;
int reach = Math.min(i + nums[i], n - 1);
for (int j = i + 1; j <= reach; j++) {
dp[j] = true;
}
}
return dp[n - 1];
}
}
复杂度分析：
- 时间复杂度：
O(n²)，最坏情况下每个点需更新大量后续点。 - 空间复杂度：
O(n)，需要维护布尔数组。
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 <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^4
方法一：排序后合并
- 排序：将所有区间按起始点升序排列。这使得相邻的区间若有重叠必然连续出现。
- 合并：遍历排序后的区间，逐个检查当前区间是否与结果列表最后一个区间重叠。若重叠则合并，否则直接加入结果列表。
代码实现(Java)：
public class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) {
return intervals;
}
// 按区间起始点排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
int[] current = intervals[i];
if (current[0] <= last[1]) {
// 合并区间，更新结束点
last[1] = Math.max(last[1], current[1]);
} else {
// 无重叠，直接添加
merged.add(current);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
复杂度分析：
- 时间复杂度：
O(n log n)，排序耗时O(n log n)，遍历合并耗时O(n)。 - 空间复杂度：
O(n)，存储合并后的结果。
方法二：扫描线算法（理论补充）
- 事件标记：将每个区间的起点和终点标记为事件（如起点为+1，终点为-1）。
- 排序事件：按坐标排序所有事件点，若坐标相同则起点事件优先。
- 扫描合并：遍历事件点，统计当前覆盖的区间层数。当区间层数从0变为1时记录起点，当层数变为0时记录终点，完成一个合并后的区间。
伪代码：
1. 将区间转换为事件点（如 [start, +1], [end, -1]）。
2. 按坐标排序事件点，坐标相同时起点优先。
3. 遍历事件点，统计当前覆盖层数：
- 当层数从0→1时，记录起点。
- 当层数从1→0时，记录终点，并生成合并后的区间。
复杂度分析：
- 时间复杂度：
O(n log n)，事件排序耗时O(n log n)。 - 空间复杂度：
O(n)，存储事件点。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。