做网站宣传,广州建设公司网站,阿里云怎么做淘宝客网站,sae wordpress 安装插件算法可以发掘本质#xff0c;如#xff1a; 一#xff0c;若干师傅和徒弟互有好感#xff0c;有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二#xff0c;有无限多1X2和2X1的骨牌#xff0c;某个棋盘若干格子坏了#xff0c;如何在没有坏…算法可以发掘本质如 一若干师傅和徒弟互有好感有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二有无限多1X2和2X1的骨牌某个棋盘若干格子坏了如何在没有坏的格子放足够多骨牌。 三某个单色图1表示前前景0表示后景色。每次操作可以将一个1变成0。如何在最少得操作情况下使得没有两个1相邻四连通。 四若干路人有些人是熟人如何选出最多的人参加实验。为了避免熟人影响实验的效果参加的人不能是熟人。 一二是二分图的最大匹配三是二分图的最小点覆盖四是二分图最大独立集。 而这三者是等效问题。
本文涉及知识点
线段树
LeetCode2276. 统计区间中的整数数目
给你区间的 空 集请你设计并实现满足要求的数据结构 新增添加一个区间到这个区间集合中。 统计计算出现在 至少一个 区间中的整数个数。 实现 CountIntervals 类 CountIntervals() 使用区间的空集初始化对象 void add(int left, int right) 添加区间 [left, right] 到区间集合之中。 int count() 返回出现在 至少一个 区间中的整数个数。 注意区间 [left, right] 表示满足 left x right 的所有整数 x 。 示例 1 输入 [“CountIntervals”, “add”, “add”, “count”, “add”, “count”] [[], [2, 3], [7, 10], [], [5, 8], []] 输出 [null, null, null, 6, null, 8] 解释 CountIntervals countIntervals new CountIntervals(); // 用一个区间空集初始化对象 countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中 countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中 countIntervals.count(); // 返回 6 // 整数 2 和 3 出现在区间 [2, 3] 中 // 整数 7、8、9、10 出现在区间 [7, 10] 中 countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中 countIntervals.count(); // 返回 8 // 整数 2 和 3 出现在区间 [2, 3] 中 // 整数 5 和 6 出现在区间 [5, 8] 中 // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中 // 整数 9 和 10 出现在区间 [7, 10] 中 提示 1 left right 109 最多调用 add 和 count 方法 总计 105 次 调用 count 方法至少一次
线段树
由于本题无法离散化所以用数组内存必定会超只能用哈希映射或二叉树动态开点二叉树的性能略好就用二叉树。就算用二叉树也刚刚能过。 区间修改查询全部。 由于只用到了查询全部所以查询可以不实现。 save 记录 整个区间 在题目所在区间的数量。 叶子save 的值为1表示在至少一个区间。0表示不在任何区间。
templateclass TSaveint, class TRecord int
class CMyTreeRangeLineTree : public CTreeRangeLineTreeTSave, TRecord
{
public:using CTreeRangeLineTreeTSave, TRecord::CTreeRangeLineTree;
protected:virtual void OnQuery(TSave save) override{}virtual void OnUpdate(TSave save, int iSaveLeft, int iSaveRight, const TRecord update) override{ save update*(iSaveRight-iSaveLeft1);}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, int iSaveLeft, int iSaveRight) override{par left r;}virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}
};本题只会更新1如果需要考虑取消也就是更新为0。需要将懒标记的默认值设置成-1。 CountIntervals():m_treeLine(1,1’000’000’000,0,-1){
}代码
templateclass TSave, class TRecord
class CRangUpdateLineTree
{
protected:virtual void OnQuery(TSave save) 0;virtual void OnUpdate(TSave save, int iSaveLeft,int iSaveRight, const TRecord update) 0;virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, int iSaveLeft, int iSaveRight) 0;virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) 0;
};templateclass TSave, class TRecord
class CTreeRangeLineTree : public CRangUpdateLineTreeTSave, TRecord
{
protected:struct CTreeNode{int Cnt()const { return m_iMaxIndex - m_iMinIndex 1; }int m_iMinIndex;int m_iMaxIndex;TRecord record;TSave data;CTreeNode* m_lChild nullptr, * m_rChild nullptr;};CTreeNode* m_root;TSave m_tDefault;TRecord m_tRecordDef;
public:CTreeRangeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault,TRecord tRecordDef) {m_tDefault tDefault;m_tRecordDef tRecordDef;m_root CreateNode(iMinIndex, iMaxIndex);}void Update(int iLeftIndex, int iRightIndex, TRecord value){Update(m_root, iLeftIndex, iRightIndex, value);}TSave QueryAll() {return m_root-data;}void Query(int leftIndex, int leftRight) {Query(m_root, leftIndex, leftRight);}
protected:void Query(CTreeNode* node, int iQueryLeft, int iQueryRight) {if ((node-m_iMinIndex iQueryLeft) (node-m_iMaxIndex iQueryRight)) {this-OnQuery(node-data);return;}if (1 node-Cnt()) {//没有子节点return;}CreateChilds(node);Fresh(node);const int mid node-m_iMinIndex (node-m_iMaxIndex - node-m_iMinIndex) / 2;if (mid iQueryLeft) {Query(node-m_lChild, iQueryLeft, iQueryRight);}if (mid 1 iQueryRight) {Query(node-m_rChild, iQueryLeft, iQueryRight);}}void Update(CTreeNode* node, int iOpeLeft, int iOpeRight, TRecord value){const int iSaveLeft node-m_iMinIndex;const int iSaveRight node-m_iMaxIndex;if ((iOpeLeft iSaveLeft) (iOpeRight iSaveRight)){this-OnUpdate(node-data, iSaveLeft, iSaveRight, value);this-OnUpdateRecord(node-record, value);return;}if (1 node-Cnt()) {//没有子节点return;}CreateChilds(node);Fresh(node);const int mid node-m_iMinIndex (node-m_iMaxIndex - node-m_iMinIndex) / 2;if (mid iOpeLeft) {this-Update(node-m_lChild, iOpeLeft, iOpeRight, value);}if (mid 1 iOpeRight) {this-Update(node-m_rChild, iOpeLeft, iOpeRight, value);}// 如果有后代至少两个后代this-OnUpdateParent(node-data, node-m_lChild-data, node-m_rChild-data,node-m_iMinIndex,node-m_iMaxIndex);}void CreateChilds(CTreeNode* node) {if (nullptr ! node-m_lChild) { return; }const int iSaveLeft node-m_iMinIndex;const int iSaveRight node-m_iMaxIndex;const int mid iSaveLeft (iSaveRight - iSaveLeft) / 2;node-m_lChild CreateNode(iSaveLeft, mid);node-m_rChild CreateNode(mid 1, iSaveRight);}CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {CTreeNode* node new CTreeNode;node-m_iMinIndex iMinIndex;node-m_iMaxIndex iMaxIndex;node-data m_tDefault;node-record m_tRecordDef;return node;}void Fresh(CTreeNode* node){if (m_tRecordDef node-record){return;}CreateChilds(node);Update(node-m_lChild, node-m_lChild-m_iMinIndex, node-m_lChild-m_iMaxIndex, node-record);Update(node-m_rChild, node-m_rChild-m_iMinIndex, node-m_rChild-m_iMaxIndex, node-record);node-record m_tRecordDef;}
};templateclass TSaveint, class TRecord int
class CMyTreeRangeLineTree : public CTreeRangeLineTreeTSave, TRecord
{
public:using CTreeRangeLineTreeTSave, TRecord::CTreeRangeLineTree;
protected:virtual void OnQuery(TSave save) override{}virtual void OnUpdate(TSave save, int iSaveLeft, int iSaveRight, const TRecord update) override{ save update*(iSaveRight-iSaveLeft1);}virtual void OnUpdateParent(TSave par, const TSave left, const TSave r, int iSaveLeft, int iSaveRight) override{par left r;}virtual void OnUpdateRecord(TRecord old, const TRecord newRecord) override{old newRecord;}
};class CountIntervals {
public:CountIntervals():m_treeLine(1,1000000000,0,0){}void add(int left, int right) {m_treeLine.Update(left, right,1);}int count() {return m_treeLine.QueryAll();}CMyTreeRangeLineTree m_treeLine;
};测试用例
CountIntervals countIntervals ; // 用一个区间空集初始化对象countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中auto res countIntervals.count(); // 返回 6// 整数 2 和 3 出现在区间 [2, 3] 中// 整数 7、8、9、10 出现在区间 [7, 10] 中Assert(6, res);countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中res countIntervals.count(); // 返回 8// 整数 2 和 3 出现在区间 [2, 3] 中// 整数 5 和 6 出现在区间 [5, 8] 中// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中// 整数 9 和 10 出现在区间 [7, 10] 中Assert(8, res);扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
