网站用 做有什么好处,全国十大摄影培训机构,宁波建设网站价格,wordpress 插件 mysql系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了秋招面试的#xff0c;整理期间苛求每个知识点#xff0c;平衡理解简易度与深入程度。 #x1f970;来源#xff1a;材料主要源于左程云算法课程进行的#xff0c;每个知识点的修正和深入主要参考… 系列综述 目的本系列是个人整理为了秋招面试的整理期间苛求每个知识点平衡理解简易度与深入程度。 来源材料主要源于左程云算法课程进行的每个知识点的修正和深入主要参考各平台大佬的文章其中也可能含有少量的个人实验自证。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 【C】秋招实习面经汇总篇 文章目录 贪心算法并查集 参考博客 点此到文末惊喜↩︎
贪心算法
需要整理堆的使用重写cmp
auto cmp [](const int a, const int b) {return cnt[a] cnt[b];//此处cnt可由上文完成定义最大堆--跟sort正好相反
};
priority_queueint, vectorint, decltype(cmp)pq{cmp};分解过程 分解业务根据业务逻辑找到不同的贪心策略可以举出反例的贪心策略直接跳过不能举出反例的要证明其有效性 贪心算法的解题套路 实现一个不依靠贪心策略的解法X可以用最暴力的尝试脑补出贪心策略A、贪心策略B、贪心策略C…用解法X和对数器用实验的方式得知哪个贪心策略正确不要去纠结贪心策略的证明 贪心策略通常使用堆和排序示例排序式贪心 题目 一些项目要占用一一个会议室宣讲会议室不能同时容纳两个项目的宣讲。给你每- -个项目开始的时间和结束的时间你来安排宣讲的日程要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。 贪心思路每次优先安排结束时间最早的并且将无法安排的进行删除 示例堆式贪心1 题目 一块金条切成两部分需要花费和原长度一样的铜板数量比如长度为20的金条不管怎么切都要花费20个铜板。一群人各自分到自己想要的金条部分和为总长度怎么分最省铜板? 思路1每次尽可能的切下最大的部分思路2使用哈夫曼树每次弹出最小的两个数合并后在压入 示例堆式贪心2 题目 输入正数数组costs、正数数组profits、 正数K、正数M。costs[]表示i号项目的花费profits[]表示i号项目在扣除花费之后还能挣到的钱(利润)K表示你只能串行的最多做k个项目M表示你初始的资金说明每做完一个项目马上获得的收益可以支持你去做下一个项目。不能并行的做项目。输出:你最后获得的最大钱数。 思路1建立两个堆一个以costs作为key的小根堆一个是以profits作为key的大根堆。 struct Program {int p;int cProgram(int profit, int cost) : p(profit), c(cost){}
}int FindMaxProfits(vectorint profits, vectorint costs, int times, int surplus) {// 比较最小花费auto cmp_min_cost [](const Program a, const Program b)-bool{return a.c b.c;};// 比较最大利润auto cmp_max_profit [](const Program a, const Program b)-bool{return a.p b.p;};// 关于花费的小根堆priority_queueProgram , vectorProgram, decltype(cmp_min_cost) min_cost_pq;// 关于利润的大根堆priority_queueProgram , vectorProgram, decltype(cmp_max_profit) max_profit_pq;// 将所有花费压入优先队列中for (int i 0; i profits.size(); i) {Program pg {profits[i], costs[i]};min_cost_pq.push(pg);} // 每次循环取出所有可支持的项目并压入最大利润队列for (int i 0; i times; i) {while (!min_cost_pq.empty() min_cost_pq.top().c surplus){Program pg min_cost_pq.top();min_cost_pq.pop();max_profit_pq.push(pg);}// 如果最大利润队列为空说明没有符合的项目可以继续进行if (max_profit_pq.empty()) {return surplus;}// 获取最大利润surplus max_profit_pq.top().p;max_profit_pq.pop();} }并查集
基本操作 并合并两个子集为一个新的集合查通过查找一个结点的根节点从而查找元素所属子集 作用快速确定集合中的两两元素是否属于S的同一子集基本并查集 问题每一次Find操作的时间复杂度为O(H)H为树的高度由于树的不断合并可能会使树严重不平衡最坏情况每个节点都只有一个子节点如下图3第一个点为根节点 #include vector
class DisjSet {
private:vectorint parent;
public:DisjSet(int max_size) : parent(vectorint(max_size)) {// 各自为营初始化每一个元素的根节点都为自身for(int i 0; i max_size; i) parent[i] i; }// 查找没找到就一直递归查看父亲结点int find(int x) {return (parent[i] x ? x : find(parent[i]);}// 合并将 x1 所在的集合的根节点的父节点设置为 x2 所在集合的根节点void to_union(int x1, int x2) {parent[find(x1)] find(x2);}// 判断两个元素是否属于同一个集合bool is_same(int e1, int e2) {return find(e1) find(e2);}
}; 优化并查集 路径压缩查询过程中将沿途每个结点的父结点都设置为根结点下次就可以减少查询路径长度按秩合并“按秩合并”。实际上就是在合并两棵树时将高度较小的树合并到高度较大的树上。这里我们使用“秩”(rank)代替高度秩表示高度的上界通常情况我们令只有一个节点的树的秩为0严格来说rank 1才是高度的上界两棵秩分别为r1、r2的树合并如果秩不相等我们将秩小的树合并到秩大的树上这样就能保证新树秩不大于原来的任意一棵树。如果r1与r2相等两棵树任意合并并令新树的秩为r1 1。 #include vector
class DisjSet {private:std::vectorint parent;std::vectorint rank; // 秩public:DisjSet(int max_size) : parent(std::vectorint(max_size)),rank(std::vectorint(max_size, 0)) {for (int i 0; i max_size; i)parent[i] i;}int find(int x) {return x parent[x] ? x : (parent[x] find(parent[x]));}void to_union(int x1, int x2) {int f1 find(x1);int f2 find(x2);if (rank[f1] rank[f2])parent[f2] f1;else {parent[f1] f2;if (rank[f1] rank[f2])rank[f2];}}bool is_same(int e1, int e2) {return find(e1) find(e2);}
};并查集示例 题目 如果两个usera字段一样或者b字段一样、或者c字段一样就认为是同一个人请合并user并返回合并后的人数
struct User {string a;string b;string c;User(string a1, string b1, string c1) : a(a1), b(b1), c(c1){}
}; 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客 知乎并查集 待定引用 待定引用 待定引用
