当前位置： 首页 > news >正文

代码随想录算法训练营第二十五天

news 2025/7/20 14:10:25

LeetCode.491 递增子序列

题目链接 递增子序列

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {dfs(nums, 0);return resList;}private void dfs(int[] nums,int index){Set<Integer> uset = new HashSet<>();if (res.size() >= 2) {resList.add(new ArrayList<>(res));}for(int i = index;i < nums.length;i++){if((res.isEmpty() || nums[i] >= res.get(res.size()-1)) && !uset.contains(nums[i])){res.add(nums[i]);uset.add(nums[i]);dfs(nums,i+1);res.remove(res.size()-1);}}}
}

解题思路

这段代码实现了寻找数组中所有递增子序列的功能，其中子序列的长度至少为 2。下面我来分析其工作原理：

采用深度优先搜索 (DFS) 结合回溯法，通过递归的方式探索所有可能的递增子序列，并使用集合进行去重处理，确保结果中没有重复的子序列。

代码解析

  1. 成员变量：

    • resList：用于存储所有符合条件的递增子序列
    • res：作为临时容器，存储当前正在构建的子序列

  2. 主方法 findSubsequences：

    • 启动 DFS 搜索，从数组的第 0 个元素开始
    • 返回最终收集到的所有符合条件的子序列

  3. DFS 递归方法：

    • index：当前递归开始遍历的数组索引
    • uset：用于记录本层递归中已经使用过的元素，防止同一层出现重复选择

  4. 递归终止与收集结果：

    • 当临时子序列res的长度大于等于 2 时，将其加入结果集resList
    • 这里没有显式的终止条件，而是通过循环自然结束递归

  5. 循环与选择逻辑：

    • 从index开始遍历数组，确保子序列元素的相对顺序
    • 选择条件：
      • 要么是子序列的第一个元素（res.isEmpty()）
      • 要么当前元素大于等于子序列的最后一个元素（保证递增性）
      • 当前元素在本层未被使用过（!uset.contains(nums[i])，用于去重）

  6. 回溯操作：

    • 选择元素后，将其加入res和uset
    • 递归探索下一个位置（i+1）
    • 递归返回后，移除res中最后一个元素，实现回溯，尝试其他可能的选择

去重逻辑说明

uset在每一层递归中都会重新创建，仅作用于当前层的元素选择。这确保了：

  • 同一层中不会选择相同值的元素，避免产生重复子序列
  • 不同层可以选择相同值的元素（如[7,7]这样的有效子序列）

例如，对于数组[4,7,7]，代码会正确生成[4,7]和[4,7,7]，但不会因为两个 7 而生成重复的[4,7]。

这段代码时间复杂度为 O (2^n)（最坏情况下需要探索所有可能的子序列），空间复杂度为 O (n)（递归栈深度和临时存储的子序列长度）。

LeetCode.46 全排列

题目链接 全排列

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {int len = nums.length;if(len == 0) return resList;used = new boolean[len];dfs(nums);return resList;}private void dfs(int[] nums){if(res.size() == nums.length) {resList.add(new ArrayList<>(res));return ;}for(int i = 0;i<nums.length;i++){if(used[i]) continue;used[i] = true;res.add(nums[i]);dfs(nums);res.remove(res.size()-1);used[i]=false;}}
}

解题思路

这段代码实现了数组全排列的功能，能够生成给定数组中所有元素的所有可能排列组合。下面我来分析其工作原理：

采用深度优先搜索 (DFS) 结合回溯法，通过递归的方式探索所有可能的元素排列，使用一个布尔类型的数组记录元素是否已被使用，确保每个元素在每个排列中只出现一次。

代码解析

  1. 成员变量：

    • resList：用于存储所有可能的排列结果
    • res：作为临时容器，存储当前正在构建的排列
    • used：布尔数组，标记对应索引的元素是否已被使用

  2. 主方法 permute：

    • 初始化并判断数组长度，若为空则直接返回
    • 初始化used数组，用于标记元素使用状态
    • 启动 DFS 搜索
    • 返回最终收集到的所有排列

  3. DFS 递归方法：

    • 递归终止条件：当临时容器res的长度等于数组长度时，表示已构建出一个完整排列
    • 此时将当前排列加入结果集resList并返回

  4. 循环与选择逻辑：

    • 遍历数组中的所有元素
    • 若元素已被使用（used[i]为true），则跳过该元素
    • 若元素未被使用，则标记为已使用，将其加入当前排列
    • 递归调用dfs继续构建排列的下一个位置
    • 递归返回后，进行回溯操作：从当前排列中移除最后一个元素，并将其标记为未使用

工作流程示例

以数组[1,2,3]为例，代码的执行流程如下：

  1. 初始状态：res为空，used全为false
  2. 第一层递归：选择 1，标记为已使用，res变为[1]
  3. 第二层递归：选择 2，标记为已使用，res变为[1,2]
  4. 第三层递归：选择 3，标记为已使用，res变为[1,2,3]，达到数组长度，加入结果集
  5. 回溯：移除 3，标记为未使用，返回上一层
  6. 继续探索其他可能的选择，直到生成所有 6 种排列

这段代码的时间复杂度为 O (n×n!)，其中 n 是数组长度，需要生成 n! 个排列，每个排列需要 O (n) 的时间来复制。空间复杂度为 O (n)，主要用于递归栈和存储当前排列。

LeetCode.47 全排列 II

题目链接 全排列 II

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {int len = nums.length;if(len == 0) return resList;Arrays.sort(nums);used = new boolean[len];dfs(nums);return resList;}public void dfs(int[] nums){if(res.size() == nums.length){resList.add(new ArrayList<>(res));return ;}for(int i = 0;i<nums.length;i++){if(i > 0 && nums[i] == nums[i-1] && used[i-1]==false)continue;if(!used[i] ){used[i] = true;res.add(nums[i]);dfs(nums);res.remove(res.size()-1);used[i] = false;}else continue;}}
}

解题思路

这段代码实现了求含重复元素数组的所有不重复全排列的功能。与普通全排列不同，它通过特定的去重逻辑确保生成的排列没有重复项。下面我来分析其工作原理：

采用深度优先搜索 (DFS) 结合回溯法，同时通过排序和精心设计的条件判断来去除重复排列。关键在于对相同元素的处理 —— 确保相同元素在排列中保持固定的相对顺序，从而避免生成重复排列。

代码解析

  1. 成员变量：

    • resList：用于存储所有不重复的排列结果
    • res：作为临时容器，存储当前正在构建的排列
    • used：布尔数组，标记对应索引的元素是否已被使用

  2. 主方法 permuteUnique：

    • 初始化并判断数组长度，若为空则直接返回
    • 关键步骤：对数组进行排序，使相同元素相邻，为去重做准备
    • 初始化used数组，启动 DFS 搜索
    • 返回最终收集到的所有不重复排列

  3. DFS 递归方法：

    • 递归终止条件：当临时容器res的长度等于数组长度时，表示已构建出一个完整排列
    • 此时将当前排列加入结果集resList并返回

  4. 循环与去重逻辑：

    • 遍历数组中的所有元素
    • 核心去重条件：if(i > 0 && nums[i] == nums[i-1] && used[i-1]==false)continue
      • 当当前元素与前一个元素相同时
      • 且前一个元素未被使用时
      • 跳过当前元素，避免重复排列
    • 若元素未被使用，则标记为已使用，将其加入当前排列
    • 递归调用dfs继续构建排列的下一个位置
    • 递归返回后，进行回溯操作：从当前排列中移除最后一个元素，并将其标记为未使用

去重逻辑说明

去重的关键在于对相同元素的处理策略：

  • 排序使相同元素相邻，为判断重复提供条件
  • 当遇到相同元素时，只有在前一个相同元素已被使用的情况下，才使用当前元素
  • 这确保了相同元素在排列中的相对顺序固定，避免了因相同元素位置互换而产生的重复排列

例如，对于数组[1,1,2]：

  • 排序后仍是[1,1,2]
  • 第一个 1 未使用时，第二个 1 会被跳过
  • 只有第一个 1 被使用后，第二个 1 才能被使用
  • 这样就避免了生成两个相同的[1,1,2]排列

这段代码的时间复杂度为 O (n×n!)，空间复杂度为 O (n)（用于递归栈、存储当前排列和标记数组）。排序操作额外增加了 O (n log n) 的时间复杂度，但不影响整体数量级。

LeetCode.51 N皇后

题目链接 N皇后

题解

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];for (char[] c : chessboard) {Arrays.fill(c, '.');}dfs(n,0,chessboard);return res;}private void dfs(int n,int row,char[][] chessboard){if(n == row){res.add(toList(chessboard));return;}for(int i = 0;i<n;i++){if(isValid(row,i,n,chessboard)){chessboard[row][i] = 'Q';dfs(n,row + 1,chessboard);chessboard[row][i] = '.';}}}private List<String> toList(char[][] chessboard){List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}private boolean isValid(int row,int col,int n,char[][] chessboard){// 竖着for(int i = 0;i<row;i++){if(chessboard[i][col] == 'Q') return false;}// 45°for(int i = row -1,j = col - 1;i>=0 && j >= 0;i --,j--){if(chessboard[i][j] == 'Q') return false;}for(int i = row -1,j = col + 1;i>=0 && j<=n-1;i--,j++){if(chessboard[i][j] == 'Q') return false;}return true;}
}

解题思路

这段代码实现了经典的 N 皇后问题求解，能够的是回溯算法来找出所有可能的摆放方案，使得每个方案中 N 个皇后彼此不会相互攻击（即不在同一行、同一列或同一斜线上）。

N 皇后问题的核心挑战是在 N×N 的棋盘上放置 N 个皇后，使它们不能互相攻击。代码采用深度优先搜索 (DFS) 结合回溯法，逐行尝试放置皇后，通过有效性检测确保放置的皇后是安全的。

代码解析

  1. 成员变量：

    • res：用于存储所有有效的皇后后摆放方案，每个方案表示为字符串列表

  2. 主方法 solveNQueens：

    • 初始化 N×N 的棋盘，用 '.' 表示空位置
    • 从第 0 行开始启动 DFS 搜索
    • 返回所有有效的摆放方案

  3. DFS 递归方法：

    • row：当前正在处理的行
    • chessboard：当前的棋盘状态
    • 递归终止条件：当处理到第 N 行时（n == row），表示已找到一个有效解
    • 将当前棋盘状态转换为字符串列表并添加到结果集

  4. 辅助方法 toList：

    • 将字符数组表示的棋盘转换为字符串列表，便于存储和返回结果

  5. 有效性检查方法 isValid：

    • 检查在(row, col)位置放置皇后后是否安全
    • 检查内容：
      • 同一列（竖方向）是否已有皇后
      • 左上到右下的 45° 对角线是否已有皇后
      • 右上到左下的 135° 对角线是否对角线是否已有皇后
    • 无需检查同一行，因为我们是逐行放置皇后的，每行只会放一个

算法执行流程

  1. 初始化棋盘，所有位置都为 '.'
  2. 从第 0 行开始，尝试在当前行的每个列放置皇后
  3. 对每个位置检查是否可以安全放置皇后
  4. 如果可以，放置皇后 ('Q') 并递归处理下一行
  5. 递归返回后，进行回溯操作，将当前位置恢复为 '.'
  6. 当处理完所有行（达到第 N 行），将当前棋盘状态添加到结果集

时间和空间复杂度

  • 时间复杂度：O (N!)，在第一行有 N 种选择，第二行最多 N-1 种选择，以此类推
  • 空间复杂度：O (N²)，主要用于存储棋盘状态和递归栈（递归深度为 N）

这段代码高效地解决了 N 皇后问题，通过逐行处理和有效的剪枝（只在安全位置放置皇后）避免了不必要的搜索，是回溯算法的经典应用。

http://www.lryc.cn/news/593608.html

相关文章：

  • Streamlit 官翻 3 - 开发教程 Develop Tutorials
  • 80、【OS】【Nuttx】【启动】caller-saved 和 callee-saved 示例：栈空间对齐
  • Input输入和Screen相关
  • 轻松学习C++：基本语法解析
  • 从丢包到恢复：TCP重传机制的底层逻辑全解
  • 将HTML+JS+CSS数独游戏包装为安卓App
  • 微服务学习（六）之分布式事务
  • 华为擎云L420安装LocalSend
  • Java大视界：Java大数据在智能医疗电子健康档案数据挖掘与健康服务创新＞
  • kafka--基础知识点--6.1--LEO、HW、LW
  • LeetCode Hot100【7. 整数反转】
  • 创意 C++ 文本冒险战斗游戏代码
  • Uniapp之自定义图片预览
  • 下一场范式革命：Transformer架构≠最终解法
  • Spring IOC容器在Web环境中是如何启动的（源码级剖析）？
  • Java多线程进阶
  • Node.js net.Socket.destroy()深入解析
  • [spring6: AspectMetadata AspectInstanceFactory]-源码解析
  • 零基础学习性能测试第二章-监控体系
  • OllyDbg技巧学习
  • Redis 如何保证高并发与高可用
  • Python爬虫实战：研究pefile库相关技术
  • PCB 混合介质叠层：材料特性匹配与性能提升的技术解析
  • 1. Spring AI概述
  • OSPF高级特性之Overflow
  • 【c++】提升用户体验：问答系统的交互优化实践——关于我用AI编写了一个聊天机器人……（12）
  • Buildroot vs Yocto：SDK 构建机制的核心差异与实践案例
  • 多线程 示例
  • QT窗口（8）-QFileDiag
  • esp32 sd卡