网站虚拟空间更新缓存,php外贸网站建设,wordpress免费相册插件,微网站特点目录
什么是深度优先搜索#xff08;DFS#xff09;
DFS题型分类
DFS和回溯的关系
排列与组合
LeetCode 46 全排列
LeetCode 47 全排列 II
LeetCode 39 组合总和
LeetCode 40 组合总和 II
子集
LeetCode 78 子集
LeetCode 90 子集 II
分割问题
LeetCode 131 分割…目录
什么是深度优先搜索DFS
DFS题型分类
DFS和回溯的关系
排列与组合
LeetCode 46 全排列
LeetCode 47 全排列 II
LeetCode 39 组合总和
LeetCode 40 组合总和 II
子集
LeetCode 78 子集
LeetCode 90 子集 II
分割问题
LeetCode 131 分割回文串
LeetCode 22 括号生成
图搜索类
LeetCode 79 单词搜索
LeetCode 200 岛屿数量 什么是深度优先搜索DFS
深度优先搜索Depth-First Search简称 DFS是一种遍历或搜索图、树等数据结构的算法。其基本思想是尽可能深的搜索图的分支当不能继续深度搜索时回溯到上一个分支点继续搜索其它未被访问过的路径。
DFS 的核心思想是通过递归或栈来实现对每个节点的深度遍历。
DFS的基本原理 1. 起始点从根节点或图中的某个节点开始 2. 访问节点访问当前节点并将其标记为已访问 3. 递归或栈操作从当前节点的未访问邻接节点出发递归地进行 DFS 搜索 4. 回溯如果当前节点的所有邻接节点都已访问则回溯到上一个节点继续对其它未访问的节点进行 DFS 搜索 DFS的应用场景 图的遍历DFS常用于在图中遍历所有节点和边可以用于解决很多图算法问题比如找连通分量、拓扑排序、环检测。 树的遍历在树结构中DFS通过先访问子节点再访问父节点可以找到树的所有路径比如路径和问题、最小/最大深度等。 回溯问题DFS的一个重要应用是回溯问题比如全排列、组合问题、数独问题它通过递归的方式尝试所有可能的选择直到找到符合条件的解。
DFS的实现方式 1. 递归实现通过递归函数调用来模拟栈的行为。 2. 非递归实现使用栈或队列显式地保存每一个待访问的节点。 递归实现 递归版 DFS 的流程简洁清晰通过递归函数来实现深度优先的遍历。
void DFS(TreeNode* node) {if (node nullptr) return;// 访问当前节点cout node-val ;// 遍历左子树DFS(node-left);// 遍历右子树DFS(node-right);
}
非递归实现栈版 非递归版 DFS 使用栈显式地保存当前节点及其未访问的邻接节点。
void DFS(TreeNode* root) {stackTreeNode* s;if (root) s.push(root);while (!s.empty()) {TreeNode* node s.top();s.pop();cout node-val ;// 注意顺序先右后左因为栈是后进先出if (node-right) s.push(node-right);if (node-left) s.push(node-left);}
}
由于栈是后进先出所以需要先把右子节点压入栈才能确保左子节点在栈顶优先被访问。 DFS的特点 空间复杂度DFS 在递归实现中通常需要 O(h) 的栈空间其中 h 为树的高度最坏情况下是 O(n)当树为链状结构时。 时间复杂度对于图的 DFS时间复杂度是 O(V E)其中 V 为节点数E 为边数。对于树的 DFS时间复杂度是 O(n)其中 n 为节点数。 DFS题型分类
排列与组合类 全排列生成所有可能的排列 组合问题从一个集合中选择多个元素有时可以重复选择有时不能 常见题目 LeetCode 46全排列 LeetCode 47全排列 II LeetCode 39组合总和 LeetCode 40组合总和 II
子集类 生成一个集合的所有子集通常是二进制枚举的变种 常见题目 LeetCode 78子集 LeetCode 90子集 II
分割问题 将一个集合或数组划分成几个小部分或进行某种分割通常需要满足特定条件 常见题目 LeetCode 131分割回文串 LeetCode 22括号生成
图搜索类 主要在二维网格或图结构中进行搜索寻找特定的路径或模式 常见题目 LeetCode 79单词搜索 LeetCode 200岛屿数量
数独与拼图类 解决类似数独之类的填充或排列问题使用回溯法逐步尝试填充发现无解时撤回 常见题目 LeetCode 37数独解法 DFS和回溯的关系
回溯法是一种算法思想DFS 是实现回溯的常用手段。 DFS 的核心是一种遍历或搜索策略沿着一条路径尽可能深入地探索直到无法继续再回溯到上一个节点选择另一条路径继续探索。 回溯法的核心是在搜索过程中当发现当前路径不可能得到有效解时主动放弃该路径剪枝回退到上一步重新选择以避免无效搜索。 关系 回溯法通常使用 DFS 来实现但也可以用 BFS 等其他搜索方式 DFS 强调遍历的过程回溯强调 试错 - 回退 - 再试 的决策过程 回溯法在 DFS 的基础上增加了剪枝操作提高搜索效率 排列与组合
排列与组合问题是回溯算法中最基础的类型它们通常涉及如何从一个集合中选择或排列元素
1. 排列问题 排列指的是从一组元素中选取出所有可能的排列排列中元素的顺序非常重要。 要求生成给定集合中所有元素的不同排列。 特点 需要考虑元素的顺序排列的结果与选取的元素顺序相关。 如果题目中有重复元素需要进行去重处理避免重复的排列。 排列问题可以通过递归回溯实现逐步将元素放入不同的位置尝试所有可能的排列。 LeetCode 46 全排列
解题思路 回溯法核心思想 每次选择一个元素将数组中的每个元素都尝试放入不同的位置。 递归生成剩余的排列当选定一个元素放入当前排列后递归生成剩下的元素的排列。 回溯当递归深入到最深层即排列完成就需要回溯到上一步去尝试不同的元素组合。 去重题目中已经保证了输入数组没有重复元素所以不需要处理去重问题。
递归树的构建 对于数组 [1, 2, 3]第一层递归会选择 1、2、3 中的一个元素放入排列中。然后递归地继续选择剩余的元素直到数组中的元素都被选完为止。
vectorvectorint permute(vectorint nums) {vectorvectorint res; // 存储所有排列结果vectorint path; // 存储当前路径排列dfs(nums, path, res);return res;
}void dfs(vectorint nums, vectorint path, vectorvectorint res) {if (path.size() nums.size()) {res.push_back(path);return;}for (int i 0; i nums.size(); i) {// 检查当前元素是否已在路径中if (find(path.begin(), path.end(), nums[i]) ! path.end()) {continue;}path.push_back(nums[i]); // 选择当前元素// 递归调用继续构建路径dfs(nums, path, res);path.pop_back(); // 回溯移除最后一个元素}
} if (find(path.begin(), path.end(), nums[i]) ! path.end()) 这个条件通过 find 函数检查 nums[i] 是否已经出现在当前排列 path 中 find 函数会返回一个迭代器如果元素在 path 中找到了返回的迭代器位置将不等于 path.end()。 如果 nums[i] 已经在 path 中则跳过本次循环继续检查下一个元素。这是为了避免重复的元素出现在排列中。 时间复杂度是 O(n!)因为生成全排列需要遍历所有可能的排列排列的总数为 n! 空间复杂度是 O(n)因为递归的深度最多为 n且每次递归都需要存储当前的排列。 LeetCode 47 全排列 II
vectorvectorint permuteUnique(vectorint nums) {vectorvectorint res;vectorint path;vectorbool used(nums.size(), false); // 标记元素是否被使用过sort(nums.begin(), nums.end()); // 排序使得相同元素相邻dfs(nums, used, path, res);return res;
}void dfs(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) {if (path.size() nums.size()) {res.push_back(path);return;}for (int i 0; i nums.size(); i) {if (used[i]) {continue;}// 去重关键当前元素与前一个元素相同且前一个元素未被使用时跳过if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue;}used[i] true;path.push_back(nums[i]);dfs(nums, used, path, res);path.pop_back();used[i] false; }
}
sort(nums.begin(), nums.end()) 的作用是让相同的数字相邻这样在回溯时才能用 nums[i] nums[i-1] 判断重复并正确剪枝。如果不排序相同的数字可能分散在数组各处无法正确去重从而生成重复的排列。 例如 nums [1, 2, 1] 当 i2nums[2] 1nums[i-1] 2nums[i] ! nums[i-1]所以不会跳过导致重复选择 1 find(path.begin(), path.end(), nums[i]) 这种方法不能正确处理重复数字的排列问题 去重必须保证相同数字的使用顺序 如果 nums[i] nums[i-1]并且 nums[i-1] 还没被使用!used[i-1]说明 nums[i] 是重复的应该跳过。这样才能保证相同数字按顺序被选中避免重复排列。
find 无法实现这一点find 只检查 nums[i] 是否在 current 中但无法判断它是否是应该跳过的重复数字 第一层递归 i0选 nums[0]1 → 进入子树 i1发现 nums[1]1 且 nums[0] 未被使用 → 跳过剪枝 i2选 nums[2]2 → 进入子树 如果 nums[i] nums[i-1] 且 !used[i-1]说明 nums[i-1] 还没被选但 nums[i] 却先被选了这样会导致重复所以跳过 nums[i]。 如果 used[i-1] true说明 nums[i-1] 已经被选了nums[i] 可以正常选。 2. 组合问题 组合指的是从一组元素中选取若干个元素顺序不重要。 要求从给定集合中选取元素不需要考虑顺序输出所有的组合。 特点 组合问题不关心顺序只关心选取了哪些元素。 选取的元素数量可以固定也可以可变。 如果有重复元素通常需要进行去重处理。 组合问题的回溯通常是选择或不选择的决策过程逐步选择元素并递归地生成组合。
LeetCode 39 组合总和
sort 函数把 candidates 数组从小到大排好。有两个好处 方便剪枝如果某枚硬币比剩下要凑的钱还多后面更大的硬币肯定也凑不上直接跳过 避免重复组合通过控制只能从当前硬币及后面的硬币里选避免[2,3] 和 [3,2] 这种重复情况 可以把这个题想象成凑硬币
dfs 参数介绍
参数名含义例子目标 7当前选了 2a排序后的硬币数组不能改[2,3,6,7]start从哪枚硬币开始选控制不重复0第一次选、0选了 2 后还能再选 2remain还需要凑多少钱才能到目标7刚开始、5选了 2 后path当前正在尝试的组合能改选硬币就加不选就删[2]刚选了第一个 2res最终要返回的所有有效组合能改找到一个就加进去刚开始是空的后来加 [2,2,3]
vectorvectorint combinationSum(vectorint candidates, int target) {sort(candidates.begin(), candidates.end()); vectorvectorint res;vectorint path;dfs(candidates, 0, target, path, res);return res;
}void dfs(const vectorint a, int start, int remain,vectorint path, vectorvectorint res) {if (remain 0) { res.push_back(path);return;}for (int i start; i a.size(); i) {if (a[i] remain) break; // 剪枝path.push_back(a[i]); dfs(a, i, remain - a[i], path, res); // 传 i 允许重复选path.pop_back(); // 撤销选择}
} LeetCode 40 组合总和 II
代码和组合总和有两处不同 1. dfs递归时传的是i 1而不是i意思是下一次只能从当前元素的下一个开始选避免重复使用同一个元素 2. 多了一行if (i start a[i] a[i - 1]) continue; 作用是去掉同一层循环中重复的元素避免出现重复组合为什么i start因为i start时是第一个出现的元素需要保留
vectorvectorint combinationSum2(vectorint candidates, int target) {sort(candidates.begin(), candidates.end());vectorvectorint res;vectorint path;dfs(candidates, 0, target, path, res);return res;
}void dfs(const vectorint a, int start, int remain,vectorint path, vectorvectorint res) {if (remain 0) {res.push_back(path);return;}for (int i start; i a.size(); i) {if (a[i] remain) break; // 剪枝if (i start a[i] a[i - 1]) continue; // 同层去重path.push_back(a[i]);dfs(a, i 1, remain - a[i], path, res); path.pop_back();}
} 子集
子集类题型的特点 1. 目标是生成所有子集幂集 给定一个数组子集类问题的核心就是对于每个元素都有两种选择即要或不要 所以总共有 2^n 种子集包括空集和全集
2. 顺序不重要 子集问题与排列不同元素的顺序不影响子集的唯一性 例如 [1,2] 和 [2,1] 被认为是同一个子集 所以子集类问题的递归搜索常使用 start 参数避免回头
3. 两种常见实现方式 回溯法DFS递归过程中把当前路径视为一个子集依次探索「选择 / 不选择某个元素」的分支 二进制枚举用一个二进制数表示某个元素是否被选入子集。例如 nums [1,2,3]101 表示子集 [1,3]
4. 是否包含重复元素 → 处理方式不同 无重复元素直接回溯或枚举即可典型题目是 LeetCode 78 子集 有重复元素要做去重和组合 IILeetCode 40的思路类似需要排序同层去重典型题目是 LeetCode 90 子集 II LeetCode 78 子集
方法一DFS
vectorvectorint subsets(vectorint nums) {vectorvectorint res;vectorint path;dfs(nums, 0, path, res);return res;
}void dfs(const vectorint nums, int start,vectorint path, vectorvectorint res) {res.push_back(path);for (int i start; i nums.size(); i) {path.push_back(nums[i]); dfs(nums, i 1, path, res); path.pop_back(); }
}
方法二二进制枚举
vectorvectorint subsets(vectorint nums) {int n nums.size();vectorvectorint res;for (int mask 0; mask (1 n); mask) {vectorint path;for (int i 0; i n; i) {if (mask (1 i)) {path.push_back(nums[i]); // 该位为1则选}}res.push_back(move(path));}return res;
}
1 n 是个位运算意思是 1 向左移 n 位等价于 2^n
mask (1 i) 可以判断 mask 的第 i 位是否为 1
move() 作用是将一个对象转换为右值引用 带 move 时 path 中的数据直接被转移到 res 中两者首元素地址相同没有新内存分配 转移后 path 变成空向量资源已被取走 不带 move 时 res 中会生成新的拷贝首元素地址和原 path 不同 path 仍然保留原有数据内存未释放 左值Lvalue能放在赋值号左边的持久对象 本质有明确的内存地址且生命周期较长比如函数内的局部变量、全局变量、数组元素等可以被多次访问或修改。 右值Rvalue只能放在赋值号右边的临时对象 本质没有持久的内存身份要么是临时生成的数值要么是即将被销毁的对象生命周期很短。 LeetCode 90 子集 II
vectorvectorint subsetsWithDup(vectorint nums) {sort(nums.begin(), nums.end()); // 排序便于同层去重vectorvectorint res;vectorint path;dfs(nums, 0, path, res);return res;
}void dfs(const vectorint nums, int start,vectorint path, vectorvectorint res) {res.push_back(path);for (int i start; i (int)nums.size(); i) {// 同层去重本层已用过 nums[i-1] 作为起点就不要再用相同值的 nums[i]if (i start nums[i] nums[i - 1]) continue;path.push_back(nums[i]);dfs(nums, i 1, path, res); path.pop_back();}
}
同层去重本层已用过 nums[i-1] 作为起点就不要再用相同值的 nums[i] 分割问题
分割类问题的核心在某些位置切或不切形成搜索树 解法通常是 回溯 剪枝加上条件判断 难点在于 如何快速判断切出来的部分是否合法回文判定/括号合法等 如何避免重复计算可以用 DP 优化 LeetCode 131 分割回文串
vectorvectorstring partition(string s) {int n s.size();vectorvectorstring res;vectorstring path;// 预处理回文表vectorvectorbool isPal(n, vectorbool(n, false));for (int i n - 1; i 0; --i) {for (int j i; j n; j) {if (s[i] s[j] (j - i 2 || isPal[i 1][j - 1])) {isPal[i][j] true;}}}// 回溯切分dfs(s, 0, isPal, path, res);return res;
}void dfs(const string s, int start,const vectorvectorbool isPal,vectorstring path,vectorvectorstring res) {if (start s.size()) { res.push_back(path);return;}for (int end start; end s.size(); end) {if (!isPal[start][end]) continue; // 剪枝path.push_back(s.substr(start, end - start 1));dfs(s, end 1, isPal, path, res); path.pop_back(); }
}
dfs参数 s原始字符串 start当前拆分的起始位置从这里开始找下一个回文子串 isPal前面算好的回文表 path当前正在拆分的方案 res存储所有有效的拆分方案 以 s aab 为例 第一次调用 dfsstart0从开头开始拆path 为空 循环 end 从 0 开始 end0isPal[0][0]是 truea 是回文→ path 变成 [a] → 调用 dfs (start1) 第二次调用 dfsstart1从索引 1 开始拆path[a] 循环 end 从 1 开始 end1isPal[1][1]是 truea 是回文→ path 变成 [a,a] → 调用 dfs (start2) 第三次调用 dfsstart2从索引 2 开始拆path[a,a] 循环 end2isPal[2][2]是 trueb 是回文→ path 变成 [a,a,b] → 调用 dfs (start3) start3 等于字符串长度 3 → 方案 [a,a,b] 加入 res 回溯后继续尝试 回到 start1 时end2isPal[1][2]是 falseab 不是回文→ 跳过 回到 start0 时end1isPal[0][1]是 trueaa 是回文→ path 变成 [aa] → 调用 dfs (start2) start2 时选 b → path 变成 [aa,b] → 加入 res 最终 res 里就有了两种方案[[a,a,b], [aa,b]] LeetCode 22 括号生成
思路 只能在还没用完左括号时放 (open n 只能在当前序列仍然合法时放 )close open 终止open n close n收集结果
vectorstring generateParenthesis(int n) {vectorstring res;string path;dfs(n, 0, 0, path, res);return res;
}void dfs(int n, int open, int close, string path, vectorstring res) {if (open n close n) { res.push_back(path);return;}if (open n) { // 还能放左括号path.push_back(();dfs(n, open 1, close, path, res);path.pop_back();}if (close open) { // 右括号数量必须 左括号path.push_back());dfs(n, open, close 1, path, res);path.pop_back();}
}
dfs参数 n需要生成的括号对数 open当前已经用了多少个左括号 ( close当前已经用了多少个右括号 ) path当前正在构建的括号串 res存储所有有效的括号组合 图搜索类
题目一般给一个 二维矩阵grid、迷宫地图或者图Graph要求搜索是否存在路径、找出所有路径、或者计算最短路径。
常用搜索方式 DFS深度优先搜索 沿着一个方向不断深入直到走不通再回溯 适合判断连通性、找路径、求面积、遍历所有可能 BFS广度优先搜索 从起点出发一层层向外扩展 适合求最短路径层数 步数
常用技巧 访问标记visited避免重复走已经访问过的点防止无限循环 方向数组dx, dy简化对上下左右的遍历
int dx[4] {1, -1, 0, 0};
int dy[4] {0, 0, 1, -1};
问题模式 是否存在路径DFS 或 BFS典型如单词搜索79 连通块计数DFS/BFS 遍历整张图典型如岛屿数量200 最短路径BFS层数就是最短步数典型如最短路径 in 二维网格、迷宫问题 复杂约束结合回溯典型如数独求解37
复杂度特点 DFS/BFS 都是 O(VE)顶点边二维网格里一般是 O(m·n) 回溯题型则会指数爆炸但剪枝能优化 LeetCode 79 单词搜索
方法一使用 visited 数组
bool exist(vectorvectorchar board, string word) {int m board.size(), n board[0].size();vectorvectorint vis(m, vectorint(n, 0));// 找可能的起点for (int i 0; i m; i) {for (int j 0; j n; j) {if (board[i][j] word[0] dfs(board, word, i, j, 0, vis))return true;}}return false;
}const int dx[4] {1, -1, 0, 0};
const int dy[4] {0, 0, 1, -1};bool dfs(vectorvectorchar b, const string w,int x, int y, int k, vectorvectorint vis) {if (k w.size()) return true; // 终止条件int m b.size(), n b[0].size();// 剪枝if (x 0 || x m || y 0 || y n) return false;if (vis[x][y] || b[x][y] ! w[k]) return false;vis[x][y] 1; // 标记// 向四个方向探索下、上、右、左for (int dir 0; dir 4; dir) {int nx x dx[dir], ny y dy[dir];if (dfs(b, w, nx, ny, k 1, vis)) return true;}// 四个方向都走不通进行回溯vis[x][y] 0; return false;
}
dfs参数 b网格 w要找的单词 x,y当前所在的网格坐标 k当前要匹配的单词字符索引比如 k0 表示要匹配 word [0] vis标记已使用单元格的数组 方法二原地标记省内存
用一个特殊字符#暂存覆盖以表示已访问回溯时再还原
bool exist(vectorvectorchar board, string word) {int m board.size(), n board[0].size();for (int i 0; i m; i) {for (int j 0; j n; j) {if (dfs(board, word, i, j, 0)) return true;}}return false;
}const int dx[4] {1, -1, 0, 0};
const int dy[4] {0, 0, 1, -1};bool dfs(vectorvectorchar b, const string w, int x, int y, int k) {if (k w.size()) return true;int m b.size(), n b[0].size();if (x 0 || x m || y 0 || y n) return false;if (b[x][y] ! w[k]) return false;char keep b[x][y];b[x][y] #; // 原地标记为已用for (int dir 0; dir 4; dir) {int nx x dx[dir], ny y dy[dir];if (dfs(b, w, nx, ny, k 1)) {b[x][y] keep; // 回溯前还原return true;}}b[x][y] keep; // 还原return false;
} LeetCode 200 岛屿数量
思路发现一个岛就清空一个岛 遍历整个网格只要遇到一个没被访问过的陆地1就说明发现了一个新岛屿 然后用 DFS 把这个岛屿上所有相连的陆地都 “变成水”标记为 0避免重复统计 最后统计这样的 “新岛屿” 有多少个。
int numIslands(vectorvectorchar grid) {int m grid.size();int n grid[0].size();int ans 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) { // 发现新岛屿ans;dfs(grid, i, j); // 淹没岛屿}}}return ans;
}void dfs(vectorvectorchar g, int x, int y) {int m g.size(), n g[0].size();if (x 0 || x m || y 0 || y n || g[x][y] ! 1) return;g[x][y] 0; // 标记为已访问const int dx[4] {1, -1, 0, 0};const int dy[4] {0, 0, 1, -1};for (int d 0; d 4; d) {dfs(g, x dx[d], y dy[d]);}
}
