厂房验收 技术支持 东莞网站建设,昆山app网站制作,广州做网站建设的公司哪家好,永康关键词优化系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于【CodeTopHot300】进行的#xff0c;每个知识点的修正和深入主要参… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于【CodeTopHot300】进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证所有代码均优先参考最佳性能。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 基础知识回溯基础算法模板组合问题无重复元素的组合有重复元素的组合 排列问题无重复元素的全排列有重复元素的全排列 HOT200回溯相关题目39. 组合总和40. 组合总和 II93. 复原 IP 地址131. 分割回文串1005. K 次取反后最大化的数组和 参考博客 点此到文末惊喜↩︎
基础知识
回溯算法 穷举 剪枝 穷举从一个选择开始一步步尝试每一个可能的选择如果某次选择导致问题无法解决则回溯并选择另一种可能直到找到一个可行的解或者穷举所有可能的解。剪枝在搜索过程中根据问题的限制条件减少搜索空间提高算法效率 作用 在多个选择中搜索出满足条件的所有可能解一般地组合问题和排列问题是在树形结构的叶子节点上收集结果而子集问题就是取树上所有节点的结果。 回溯算法解决的问题一般为npc问题难以使用常规算法进行解决 组合问题N个数里面按一定规则找出k个数的集合 切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集 排列问题N个数按一定规则选出M个有几种排列方式棋盘问题N皇后解数独等等 所有的回溯法解决的问题都可以抽象为树形结构 根节点是总数据集合树枝节点是可选数据集合叶子节点为根节点到叶子节点的路径的选择集合
// 结果集和路径集
vectorvectortype res;
vectortype path;
void backtracking(vecotrtype candidates, int startIndex) {// 针对当前选择的合法性判断auto is_ok [](const type data)-bool{// type中数据项的合法性判断};// 递归出口结点剪枝生成慢if (is_ok(val)) {res.push_back(path);return;}// 延申和回撤路径时可能涉及多个状态标记变量的改动for (int i startIndex; i candidates.size(); i) {分叉剪枝判断性能高;// 状态延申改动path.push_back(candidates[i]);// 向下延申backtracking(剩余可选列表); // 回溯// 状态回撤改动path.pop_back();// 回撤延申}
}
// 主函数
vectorvectorint combine(vectortype candidates) {res.clear(); // 可以不写path.clear();// 可以不写backtracking(candidates, 0);return result;}回溯基础算法模板 模板使用的初衷将问题的输入转换成对应模板的输入格式然后调用模板的函数已经背诵的进行快速的求解 组合问题
组合问题的复杂度 时间复杂度 O ( C n k × k ) O(C_n^k × k) O(Cnk×k)总共有 C n k C_n^k Cnk种组合每种组合需要 O ( k ) O(k) O(k) 的时间复杂度空间复杂度 O ( n ) O(n) O(n)递归深度为n所以系统栈所用空间为 O ( n ) O(n) O(n)
无重复元素的组合
基本概述 问题从无重复元素的集合中选出K个元素组成组合每个元素只能被选取一次且选出的元素之间没有顺序之分。举例从元素集合{123}中选择2个元素的组合为{(1,2)(1,3)(2,3)}。 代码 解决的问题给定一个线性表求该线性表中满足条件的组合示例求线性表中所有个数为target的结果。剪枝列表中剩余元素(vec.size() - i) 所需需要的元素个数(target - path.size())
// 从候选集candidate中选出任意k个数组成的集合
vectorvectorint Backtracking(vectorint candidate, int k) {const int len candidate.size();// 递归函数vectorint path; // 符合条件的路径vectorvectorint res; // 符合条件的路径集合auto self [](auto self, int pos){// 递归出口满足条件的路径加入结果集中if (path.size() k) {res.push_back(path);return;}// i start表示从之后剩余中选择for (int i pos; i len ; i) {if (i len - (k-path.size())) continue;path.push_back(candidate[i]); // 做出选择self(self, i1);// key: 是i1 // 递归path.pop_back(); // 撤销选择}};self(self, 0);return res;
}
有重复元素的组合
基本概述 问题从有重复元素的组合中选出若干元素组成组合每个元素只能被选取一次且选出的元素之间没有顺序之分。举例从集合{1, 2, 2, 3}中选择2个元素的组合为{1, 2}、{1, 3}、{2, 2}、{2, 3}。 代码 解决问题给定一个线性表求该线性表中满足条件的组合因为有重复元素所以选择重复元素时只能使用一次否则会出现集合中的重复
vectorvectorint Backtracking(vectorint candidate, int k) {// 排序sort(candidate.begin(), candidate.end());// 递归匿名函数vectorint path;vectorvectorint res;auto self [](auto self, int pos){if (path.size() k) {res.push_back(path);return;}for (int i pos; i candidate.size(); i) {// key: i pos。第一次选取到重复的数不会影响后面if (i pos candidate[i] candidate[i-1])continue;path.push_back(candidate[i]);self(self, i1);path.pop_back();}};// 递归调用self(self, 0);return res;
}排列问题
组合问题的复杂度 时间复杂度 O ( n × n ! ) O(n×n!) O(n×n!)一共 n ! n! n! 种组合每种排列构造时间需要 O ( n ) O(n) O(n) 的时间复杂度空间复杂度 O ( n ) O(n) O(n)递归深度为n所以系统栈所用空间为 O ( n ) O(n) O(n)
无重复元素的全排列
基本概述 问题无重复元素的排列是指在给定一组不同的元素中按照一定的顺序排列出所有可能的组合每个元素只出现一次。举例从集合{1, 2, 3}则可以产生以下6种无重复元素的排列{1, 2, 3}、{1, 3, 2}、{2, 1, 3}、{2, 3, 1}、{3, 1, 2}、{3, 2, 1}。 代码 不需要使用pos每一个i对应一位 vectorvectorint permute(vectorint candidate) {const int len candidate.size();vectorint path; // 回溯路径vectorvectorint res; // 回溯结果集vectorbool used(len, false); // 使用标记auto self [](auto self){ // 回溯算法if (path.size() len) {res.push_back(path);return ;}for (int i 0; i len; i) {// path里已经收录的元素直接跳过if (used[i] true) continue;// 增加选择used[i] true;path.push_back(candidate[i]);// 进行回溯self(self);// 撤回选择used[i] false;path.pop_back();}};// 调用self(self);return res;
}有重复元素的全排列 基本概述 问题无重复元素的排列是指在给定一组不同的元素中按照一定的顺序排列出所有的不重复组合举例从集合[1,1,2]则可以产生无重复的全排列 [1,1,2], [1,2,1], [2,1,1] 代码 产生重复解的原因例如[1,1,2], 无法区分[1(0), 1(1), 2] 和[1(1), 1(0), 2] 这两种情况的解 vectorvectorint permuteUnique(vectorint candidate) {const int len candidate.size();sort(candidate.begin(), candidate.end());// 递归vectorint path;vectorvectorint res;vectorbool used(len, false); // key注意初始化auto self [](auto self){if (path.size() len) {res.emplace_back(path);return ;}for (int i 0; i len; i) {// 有效的重复元素 前一个元素未被使用// 保证相同元素同层中只有第一个被使用if (i 0 candidate[i] candidate[i-1] used[i-1] false) continue;if (used[i] false) {used[i] true;path.emplace_back(candidate[i]);self(self);used[i] false;path.pop_back();}}};self(self);return res;
}// 哈希表处理重复解
vectorvectorint permuteUnique(vectorint candidate) {const int len candidate.size();// 去重unordered_mapint, int umap;for (auto i : candidate) umap[i];// 回溯算法vectorvectorint res;vectorint path;auto self [](auto self, int pos){// 递归出口if (pos len) {res.push_back(path);return ;}for (auto i : umap) {if (i.second 0) continue;path.push_back(i.first);--i.second;self(self, pos1);path.pop_back();i.second;}};self(self, 0);return res;
}HOT200回溯相关题目
39. 组合总和
题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回candidates 中的 同一个 数字可以 无限制重复被选取输入candidates [2,3,5], target 4输出[[2,2]]
vectorvectorint combinationSum(vectorint candidates, int target) {vectorvectorint res;vectorint path;auto self [](auto self, int pos, int sum){// 结束条件if (sum target) return ;if (sum target) {res.push_back(path);return ;}// 路径回溯for (int i pos; i candidates.size(); i) {sum candidates[i];path.push_back(candidates[i]);self(self, i, sum); // key: 不用i1表示可重复读取当前值sum - candidates[i];path.pop_back();}};self(self, 0, 0);return res;
}40. 组合总和 II
题目 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。输入: candidates [2,5,2,1,2], target 5,输出[ [1,2,2], [5] ] 代码
vectorvectorint combinationSum2(vectorint candidates, int target) {const int len candidates.size();sort(candidates.begin(), candidates.end());// 回溯部分vectorint path;vectorvectorint res;vectorbool used(len, false);int sum 0;auto self [](auto self, int pos){// 结点剪枝if (sum target) {res.emplace_back(path);return ;}for (int i pos; i len; i) {// 分叉剪枝: 性能高一些if (sum candidates[i] target) continue;if (i 0 candidates[i] candidates[i-1] used[i-1] false) continue;if (used[i] true) continue;used[i] true;path.emplace_back(candidates[i]);sum candidates[i];self(self, i1); // i1表示每个元素不重复使用sum - candidates[i];path.pop_back();used[i] false;}};self(self, 0);return res;
}93. 复原 IP 地址
题目 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成输入s “25525511135”输出[“255.255.11.135”,“255.255.111.35”] vectorstring restoreIpAddresses(string s) {const int len s.size();// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法auto is_valid [](const string s, int start, int end) {cout start end endl;if (start end) {return false;}if (s[start] 0 start ! end) // 0开头的数字不合法return false;int num 0;for (int i start; i end; i) {if (s[i] 9 || s[i] 0) { // 遇到非数字字符不合法return false;}num num * 10 (s[i] - 0);if (num 255) { // 如果大于255了不合法return false;}}return true;
};131. 分割回文串
131. 分割回文串 获取[startIndex,i]在s中的子串s.substr(startIndex, i - startIndex 1) // 判断是否为回文字符串
bool isPalindrome(const string s, int start, int end) {for (int i start, j end; i j; i, j--) {if (s[i] ! s[j]) {return false;}}return true;
}
// 基本的回溯
vectorvectorstring result;
vectorstring path; // 放已经回文的子串
void backtracking (const string s, int startIndex) {// 如果起始位置已经大于s的大小说明已经找到了一组分割方案了if (startIndex s.size()) {result.push_back(path);return;}for (int i startIndex; i s.size(); i) {// 剪枝与枝的延长if (isPalindrome(s, startIndex, i)) { // 是回文子串// 获取[startIndex,i]在s中的子串string str s.substr(startIndex, i - startIndex 1);path.push_back(str);} else { // 不是回文跳过continue;}backtracking(s, i 1); // 寻找i1为起始位置的子串path.pop_back(); // 回溯过程弹出本次已经填在的子串}
}vectorvectorstring partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;
}1005. K 次取反后最大化的数组和
1005. K 次取反后最大化的数组和 sort的使用第三个参数为自定义的排序队则在头文件#includeaccumulate的使用第三个参数为累加的初值在头文件include static bool cmp(int a, int b) {return abs(a) abs(b);// 绝对值的从大到小进行排序
}
int largestSumAfterKNegations(vectorint A, int K) {// 将容器内的元素按照绝对值从大到小进行排序sort(A.begin(), A.end(), cmp); // 在K0的情况下将负值按照绝对值从大到小依次取反for (int i 0; i A.size(); i) { if (A[i] 0 K 0) {A[i] * -1;K--;}}// 如果K为奇数将最小的正数取反if (K % 2 1) A[A.size() - 1] * -1; // 求和return accumulate(A.begin(),A.end(),0);// 第三个参数为累加的初值在头文件includenumeric
}少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 「代码随想录」47. 全排列 II:【彻底理解排列中的去重问题】详解 codetop
