建站行业导航网站网站制公司

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

建站行业导航网站,网站制公司,网站页面链接怎么做,wordpress搜索页面不同文章目录 组合目标和组合总和字母大小写全排序优美的排列N皇后 组合 思路#xff1a;回溯算法 问题要求从 1 到 n 中选出 k 个数的所有组合。 使用回溯算法递归构造解。 每次递归时#xff0c;记录当前的组合路径#xff0c;当组合长度达到 k 时#xff0c;将其加入结果集… 文章目录 组合目标和组合总和字母大小写全排序优美的排列N皇后 组合 思路回溯算法 问题要求从 1 到 n 中选出 k 个数的所有组合。 使用回溯算法递归构造解。 每次递归时记录当前的组合路径当组合长度达到 k 时将其加入结果集。 剪枝优化在递归过程中如果当前选择的起点到 n 不够 k 个数就停止递归。 class Solution {vectorvectorint ret; // 用于存储最终的所有组合结果vectorint path; // 用于存储当前正在构建的组合int n, k; // n 表示范围 [1, n]k 表示组合的大小public:vectorvectorint combine(int _n, int _k) {n _n; // 初始化 nk _k; // 初始化 kdfs(1); // 从数字 1 开始进行深度优先搜索return ret; // 返回所有的组合结果}// 深度优先搜索函数用于生成所有的组合void dfs(int pos){// 如果当前组合的大小等于 k则将该组合加入结果集if(k path.size()){ret.push_back(path); // 将当前组合存储到结果集中return; // 返回结束当前递归分支}// 从当前数字 pos 开始尝试加入到组合中for(int i pos; i n; i){path.push_back(i); // 将当前数字加入到组合中dfs(i 1); // 递归调用处理下一个数字确保数字不会重复path.pop_back(); // 回溯移除最后加入的数字尝试其他可能性}} };目标和 回溯 通过正负号的分配来形成目标和尝试所有可能的组合。 如果找到一种方式满足条件计数1。 class Solution {int ret, aim; // ret 用于存储满足条件的方案总数aim 是目标值public:int findTargetSumWays(vectorint nums, int target) {aim target; // 初始化目标值ret 0; // 初始化方案数dfs(nums, 0, 0); // 从索引 0 开始递归搜索初始路径和为 0return ret; // 返回满足条件的方案数}// 深度优先搜索函数用于枚举所有可能的路径和void dfs(vectorint nums, int pos, int path){// 如果已经遍历到数组末尾检查路径和是否等于目标值if(pos nums.size()){if(path aim) ret; // 如果路径和等于目标值则方案数加 1return; // 返回结束当前递归分支}// 选择将当前数字加到路径和dfs(nums, pos 1, path nums[pos]);// 选择将当前数字减到路径和dfs(nums, pos 1, path - nums[pos]);} };组合总和 思路回溯算法 使用回溯方法试图从给定的数字中选出若干个数可重复使其和为目标值。 在递归过程中 当前路径的总和如果大于目标值停止搜索。 如果总和等于目标值将当前路径加入结果。 每次递归时从当前数字开始避免重复路径。 class Solution {int aim; // 目标和vectorvectorint ret; // 存储所有满足条件的组合vectorint path; // 存储当前路径正在构建的组合public:vectorvectorint combinationSum(vectorint nums, int target) {aim target; // 设置目标和dfs(nums, 0, 0); // 从索引 0 开始深度优先搜索当前和为 0return ret; // 返回所有符合条件的组合}// 深度优先搜索函数void dfs(vectorint nums, int pos, int sum){// 如果当前和等于目标值将当前组合加入结果集if(sum aim){ret.push_back(path); // 将当前路径组合存入结果集return; // 返回结束当前递归分支}// 如果当前和超过目标值或索引超出数组范围则返回if(sum aim || pos nums.size()) return;// 从当前索引 pos 开始尝试每个数字for(int i pos; i nums.size(); i){path.push_back(nums[i]); // 将当前数字加入到路径中dfs(nums, i, sum nums[i]); // 递归调用允许重复选择当前数字path.pop_back(); // 回溯移除最后一个加入的数字尝试其他可能性}} };字母大小写全排序 思路回溯算法 遍历字符串每遇到一个字母字符就有两种选择小写或大写。 使用递归构造所有可能的字符串路径 对于每个字符选择原字符或大小写转换后的字符加入路径。 遇到数字时直接加入路径。 当遍历到字符串末尾时将路径加入结果集。 class Solution {vectorstring ret; // 用于存储所有满足条件的字符串组合string path; // 当前正在构建的路径部分字符串public:vectorstring letterCasePermutation(string s) {dfs(s, 0); // 从字符串的第 0 个字符开始深度优先搜索return ret; // 返回所有可能的组合结果}// 深度优先搜索函数void dfs(string s, int pos){// 如果当前处理位置等于字符串长度说明路径构造完成if(pos s.size()){ret.push_back(path); // 将路径加入结果集return; // 返回结束当前递归分支}char ch s[pos];// 情况 1不改变当前字符直接加入路径path.push_back(ch);dfs(s, pos 1); // 递归处理下一个字符path.pop_back(); // 回溯移除当前字符// 情况 2改变当前字符的大小写if(ch 0 || ch 9) // 如果当前字符不是数字尝试改变大小写{char tmp change(ch); // 改变字符大小写path.push_back(tmp); // 将改变后的字符加入路径dfs(s, pos 1); // 递归处理下一个字符path.pop_back(); // 回溯移除改变后的字符}}// 辅助函数改变字符的大小写char change(char ch){if(ch z ch a) ch - 32; // 小写转大写else ch 32; // 大写转小写return ch;} };优美的排列 思路回溯剪枝 使用回溯法尝试将数字放入数组中。 每次递归时判断当前数字是否满足条件能被当前位置整除或能整除当前位置。 剪枝优化如果当前排列不符合条件提前停止递归。 class Solution {int ret; // 用于记录满足条件的排列方案数bool check[16]; // 用于记录数字是否被使用过数组下标从 1 开始public:int countArrangement(int n) {dfs(n, 1); // 从位置 1 开始深度优先搜索return ret; // 返回最终的方案数}// 深度优先搜索函数void dfs(int n, int pos){// 递归终止条件如果当前位置超出 n说明排列完成if(pos n 1){ret; // 当前排列满足条件计数加 1return; // 返回结束当前递归分支}// 尝试将每个数字放在当前的位置for(int i 1; i n; i){// 如果数字 i 尚未被使用且满足题目中的条件if(!checki){check[i] true; // 标记数字 i 已被使用dfs(n, pos 1); // 递归处理下一个位置check[i] false; // 回溯取消数字 i 的使用状态}}} };N皇后 思路回溯剪枝 使用回溯法尝试将 N 个皇后放置到 N×N 棋盘上。 在递归过程中每一行尝试放置一个皇后 检查当前列、主对角线、副对角线是否已被占用。 剪枝优化利用标志数组记录列、主对角线、副对角线是否被占用避免重复检查。 当所有行都放置完成时将当前结果加入结果集。 class Solution {bool checkCol[10], checkdig1[20], checkdig2[20]; // 分别记录列、主对角线、副对角线是否被占用vectorvectorstring ret; // 存储所有符合条件的棋盘配置vectorstring path; // 当前棋盘状态int n; // 棋盘的大小public:vectorvectorstring solveNQueens(int _n) {n _n; // 初始化棋盘大小path.resize(n); // 初始化棋盘状态for(int i 0; i n; i)path[i].append(n, .); // 将每一行初始化为 n 个 .表示空位置dfs(0); // 从第 0 行开始深度优先搜索return ret; // 返回所有符合条件的棋盘配置}// 深度优先搜索函数void dfs(int row){// 递归终止条件如果已经处理到第 n 行说明所有皇后都已放置完成if(row n){ret.push_back(path); // 将当前棋盘状态加入结果集return; // 返回结束当前递归分支}// 遍历当前行的每一列尝试放置皇后for(int col 0; col n; col){// 检查当前列、主对角线、副对角线是否被占用if(!checkCol[col] !checkdig1[row - col n] !checkdig2[row col]){// 放置皇后更新棋盘状态和限制条件path[row][col] Q; // 在 (row, col) 放置皇后checkCol[col] checkdig1[row - col n] checkdig2[row col] true; // 标记当前位置dfs(row 1); // 递归处理下一行// 回溯移除皇后恢复棋盘状态和限制条件path[row][col] .; // 移除 (row, col) 的皇后checkCol[col] checkdig1[row - col n] checkdig2[row col] false; // 取消标记}}} };