目录一、N 皇后问题LeetCode 51・困难题目描述解题思路Java 代码实现标准回溯版复杂度分析优化版用 Set 记录冲突O (1) 校验核心知识点总结二、搜索插入位置LeetCode 35・简单题目描述解题思路Java 代码实现标准二分版复杂度分析大家好今天我们来拆解两道经典算法题一道是回溯法的天花板级难题 ——N 皇后问题另一道是二分查找的入门题搜索插入位置。前者帮你彻底吃透回溯剪枝的核心思想后者带你入门二分查找的标准模板非常适合作为算法学习的进阶内容一、N 皇后问题LeetCode 51・困难题目描述按照国际象棋的规则皇后可以攻击与之处在同一行、同一列或同一斜线上的棋子。n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n皇后问题的棋子放置方案该方案中Q和.分别代表皇后和空位。你可以按任意顺序返回答案。示例n4plaintext输入n 4 输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]] 解释4 皇后问题存在两个不同的解法解题思路N 皇后问题是回溯法 剪枝的经典应用核心逻辑可以拆解为 3 步逐行放置皇后因为同一行只能放一个皇后所以我们按行遍历每行只放一个皇后避免行冲突。合法性校验对于当前要放置皇后的位置(row, col)需要校验 3 个条件同一列是否有皇后左上到右下的对角线是否有皇后row - col相等右上到左下的对角线是否有皇后row col相等回溯枚举遍历当前行的每一列若位置合法则放置皇后递归下一行递归结束后回溯撤销皇后尝试其他列的位置。终止条件当row n时说明已经放完所有皇后将当前棋盘加入结果集。Java 代码实现标准回溯版java运行import java.util.ArrayList; import java.util.List; public class NQueens { ListListString result new ArrayList(); public ListListString solveNQueens(int n) { // 初始化棋盘全为 . char[][] board new char[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { board[i][j] .; } } // 从第0行开始回溯 backtrack(board, 0, n); return result; } /** * 回溯函数 * param board 当前棋盘状态 * param row 当前放置的行号 * param n 棋盘大小 */ private void backtrack(char[][] board, int row, int n) { // 终止条件所有行都放完了将棋盘转为ListString加入结果 if (row n) { result.add(boardToList(board)); return; } // 遍历当前行的每一列尝试放置皇后 for (int col 0; col n; col) { // 校验当前位置是否合法 if (isValid(board, row, col, n)) { // 做选择放置皇后 board[row][col] Q; // 递归放置下一行 backtrack(board, row 1, n); // 撤销选择回溯移除皇后 board[row][col] .; } } } /** * 校验位置(row, col)是否可以放置皇后 */ private boolean isValid(char[][] board, int row, int col, int n) { // 1. 校验同一列从第0行到当前行是否有皇后 for (int i 0; i row; i) { if (board[i][col] Q) { return false; } } // 2. 校验左上到右下的对角线 for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (board[i][j] Q) { return false; } } // 3. 校验右上到左下的对角线 for (int i row - 1, j col 1; i 0 j n; i--, j) { if (board[i][j] Q) { return false; } } return true; } /** * 将char[][]棋盘转为ListString */ private ListString boardToList(char[][] board) { ListString list new ArrayList(); for (char[] row : board) { list.add(new String(row)); } return list; } }复杂度分析时间复杂度O(n!)第一行有 n 种选择第二行最多 n-1 种第三行最多 n-2 种以此类推总共有n!种可能剪枝后实际复杂度远低于理论值。空间复杂度O(n2)棋盘占用n2空间递归栈深度为n。优化版用 Set 记录冲突O (1) 校验上面的代码每次校验都要遍历我们可以用 3 个 Set 分别记录已占用的列、左上 - 右下对角线、右上 - 左下对角线实现 O (1) 时间复杂度的合法性校验大幅提升效率java运行import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class NQueensOpt { ListListString result new ArrayList(); SetInteger colSet new HashSet(); // 已占用的列 SetInteger diag1Set new HashSet(); // 左上-右下对角线 (row - col) SetInteger diag2Set new HashSet(); // 右上-左下对角线 (row col) public ListListString solveNQueens(int n) { char[][] board new char[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { board[i][j] .; } } backtrack(board, 0, n); return result; } private void backtrack(char[][] board, int row, int n) { if (row n) { result.add(boardToList(board)); return; } for (int col 0; col n; col) { int diag1 row - col; int diag2 row col; // O(1)校验列、两条对角线是否被占用 if (!colSet.contains(col) !diag1Set.contains(diag1) !diag2Set.contains(diag2)) { // 做选择 board[row][col] Q; colSet.add(col); diag1Set.add(diag1); diag2Set.add(diag2); // 递归 backtrack(board, row 1, n); // 撤销选择 board[row][col] .; colSet.remove(col); diag1Set.remove(diag1); diag2Set.remove(diag2); } } } private ListString boardToList(char[][] board) { ListString list new ArrayList(); for (char[] row : board) { list.add(new String(row)); } return list; } }核心知识点总结回溯法核心逐行枚举、合法校验、回溯撤销是解决排列组合、棋盘类问题的通用思路。对角线规律左上→右下row - col为定值右上→左下row col为定值剪枝优化提前排除不合法的位置避免无效递归是回溯法的核心优化手段。二、搜索插入位置LeetCode 35・简单题目描述给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。示例plaintext输入: nums [1,3,5,6], target 5 输出: 2 输入: nums [1,3,5,6], target 2 输出: 1解题思路这道题是二分查找的标准入门题核心是在有序数组中查找目标值若不存在则返回插入位置完全符合二分查找的适用场景初始化左右指针left 0right nums.length - 1循环二分当left right时计算中间位置mid left (right - left) / 2避免溢出比较判断若nums[mid] target直接返回mid若nums[mid] target目标在右半区left mid 1若nums[mid] target目标在左半区right mid - 1循环结束此时left rightleft就是目标值的插入位置因为循环结束时left 指向第一个大于 target 的元素Java 代码实现标准二分版java运行public class SearchInsert { public int searchInsert(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { // 计算中间位置避免(left right)溢出 int mid left (right - left) / 2; if (nums[mid] target) { // 找到目标值直接返回索引 return mid; } else if (nums[mid] target) { // 目标在右半区左指针右移 left mid 1; } else { // 目标在左半区右指针左移 right mid - 1; } } // 循环结束left就是插入位置 return left; } }复杂度分析时间复杂度O(logn)二分查找每次将搜索范围缩小一半时间复杂度为对数级。空间复杂度O(1)仅使用常数级额外空间。