算法可以发掘本质,如:
一,若干师傅和徒弟互有好感,有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二,有无限多1X2和2X1的骨牌,某个棋盘若干格子坏了,如何在没有坏的格子放足够多骨牌。
三,某个单色图,1表示前前景,0表示后景色。每次操作可以将一个1,变成0。如何在最少得操作情况下,使得没有两个1相邻(四连通)。
四,若干路人,有些人是熟人,如何选出最多的人参加实验。为了避免熟人影响实验的效果,参加的人不能是熟人。
一二是二分图的最大匹配,三是二分图的最小点覆盖,四是二分图最大独立集。 而这三者是等效问题。
本文涉及知识点
线段树 有序映射
线段树:就求一乐乎,难写。在超时的边缘。
LeetCode715. Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false 。
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
示例 1:
输入
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]
解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true (区间 [10, 14) 中的每个数都正在被跟踪)
rangeModule.queryRange(13, 15); 返回 false(未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字)
rangeModule.queryRange(16, 17); 返回 true (尽管执行了删除操作,区间 [16, 17) 中的数字 16 仍然会被跟踪)
提示:
1 <= left < right <= 109
在单个测试用例中,对 addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次
代码
template<class TSave, class TRecord >
class CRangUpdateLineTree
{
protected:
virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) = 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;
};
template<class TSave, class TRecord >
class CTreeRangeLineTree : public CRangUpdateLineTree<TSave, 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,node->m_iMinIndex,node->m_iMaxIndex);
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;
}
};
template<class TSave=int, class TRecord =int >
class CMyTreeRangeLineTree : public CTreeRangeLineTree<TSave, TRecord>
{
public:
using CTreeRangeLineTree<TSave, TRecord>::CTreeRangeLineTree;
bool queryRange(int left, int right) {
m_bHas = true;
CTreeRangeLineTree<TSave, TRecord>::Query(left, right);
return m_bHas;
}
protected:
bool m_bHas = true;
virtual void OnQuery(TSave& save, int iSaveLeft, int iSaveRight) override
{
m_bHas &= (save == (iSaveRight - iSaveLeft + 1));
}
virtual void OnUpdate(TSave& save, int iSaveLeft, int iSaveRight, const TRecord& update) override
{
save = update*(iSaveRight-iSaveLeft+1);
}
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 RangeModule {
public:
RangeModule() :m_treeLine(1, 1'000'000'000, 0, -1) {
}
void addRange(int left, int right) {
m_treeLine.Update(left, right-1, 1);
}
bool queryRange(int left, int right) {
return m_treeLine.queryRange(left, right - 1);
}
void removeRange(int left, int right) {
m_treeLine.Update(left, right-1, 0);
}
CMyTreeRangeLineTree<> m_treeLine;
};
有序映射
class RangeModule {
public:
RangeModule() {
}
void addRange(int left, int right) {
auto it1 = m_mLeftRight.lower_bound(left);
auto it2 = m_mLeftRight.upper_bound(right);
if (it1 != m_mLeftRight.begin())
{
auto tmp = it1;
--tmp;
if (tmp->second >= left)
{
left = tmp->first;
--it1;
}
}
if (it2 != m_mLeftRight.begin())
{
auto tmp = it2;
--tmp;
if (tmp->second > right)
{
right = tmp->second;
}
}
m_mLeftRight.erase(it1, it2);
m_mLeftRight[left] = right;
}
bool queryRange(int left, int right) {
auto it1 = m_mLeftRight.upper_bound(left);
if (it1 != m_mLeftRight.begin())
{
auto tmp = it1;
tmp--;
return tmp->second >= right;
}
return false;
}
void removeRange(int left, int right) {
auto it1 = m_mLeftRight.lower_bound(left);
auto it2 = m_mLeftRight.upper_bound(right);
int iNewLeft = -1;
if (it1 != m_mLeftRight.begin())
{
auto tmp = it1;
--tmp;
if (tmp->second >= left)
{
iNewLeft = tmp->first;
}
}
int iNewRight = -1;
if (it2 != m_mLeftRight.begin())
{
auto tmp = it2;
--tmp;
if (tmp->second > right)
{
iNewRight = tmp->second;
}
}
m_mLeftRight.erase(it1, it2);
if (-1 != iNewLeft)
{
m_mLeftRight[iNewLeft] = left;
}
if (-1 != iNewRight)
{
m_mLeftRight[right] = iNewRight;
}
}
std::map<int, int> m_mLeftRight;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。