算法可以发掘本质，如：
一，若干师傅和徒弟互有好感，有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。
二，有无限多1X2和2X1的骨牌，某个棋盘若干格子坏了，如何在没有坏的格子放足够多骨牌。
三，某个单色图，1表示前前景，0表示后景色。每次操作可以将一个1，变成0。如何在最少得操作情况下，使得没有两个1相邻（四连通）。
四，若干路人，有些人是熟人，如何选出最多的人参加实验。为了避免熟人影响实验的效果，参加的人不能是熟人。
一二是二分图的最大匹配，三是二分图的最小点覆盖，四是二分图最大独立集。 而这三者是等效问题。
本文涉及知识点
线段树
LeetCode 2213. 由单个字符重复的最长子字符串
给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数 下标 数组 queryIndices ，这两个都用来描述 k 个查询。
第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。
返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询 之后 s 中仅由 单个字符重复 组成的 最长子字符串 的 长度 。
示例 1：
输入：s = “babacc”, queryCharacters = “bcb”, queryIndices = [1,3,3]
输出：[3,3,4]
解释：
- 第 1 次查询更新后 s = “bbbacc” 。由单个字符重复组成的最长子字符串是 “bbb” ，长度为 3 。
- 第 2 次查询更新后 s = “bbbccc” 。由单个字符重复组成的最长子字符串是 “bbb” 或 “ccc”，长度为 3 。
- 第 3 次查询更新后 s = “bbbbcc” 。由单个字符重复组成的最长子字符串是 “bbbb” ，长度为 4 。
因此，返回 [3,3,4] 。
示例 2：
输入：s = “abyzz”, queryCharacters = “aa”, queryIndices = [2,1]
输出：[2,3]
解释：
- 第 1 次查询更新后 s = “abazz” 。由单个字符重复组成的最长子字符串是 “zz” ，长度为 2 。
- 第 2 次查询更新后 s = “aaazz” 。由单个字符重复组成的最长子字符串是 “aaa” ，长度为 3 。
因此，返回 [2,3] 。
提示：
1 <= s.length <= 105
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 105
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length
用向量实现的线段树
template<class TSave>
class CVectorSave
{
public:
CVectorSave(int iMinIndex,int iMaxIndex, TSave tDefault) :m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex){
m_vec.assign((iMaxIndex-iMinIndex+1)*4, tDefault);
}
TSave& Ref(int iNodeNO) {
return m_vec[iNodeNO];
}
const int m_iMinIndex, m_iMaxIndex;
protected:
vector<TSave> m_vec;
};
template<class TSave, class TRecord,class TSaveCon = CVectorSave<TSave> >
class CSingUpdateLineTree
{
public:
CSingUpdateLineTree(int iEleSize, TSave tDefault) :m_vSave(0,iEleSize-1, tDefault){
}
CSingUpdateLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) :m_vSave(iMinIndex, iMaxIndex, tDefault) {
}
void Update(int index, TRecord update) {
Update(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, index, update);
}
void Query(int leftIndex, int leftRight) {
Query(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, leftIndex, leftRight);
}
void Init() {
Init(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex);
}
TSave QueryAll() {
return m_vSave.Ref(1);
}
protected:
void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
{
if (iSaveLeft == iSaveRight) {
OnInit(m_vSave.Ref(iNodeNO), iSaveLeft);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
Init(iNodeNO * 2, iSaveLeft, mid);
Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
}
void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
OnQuery(m_vSave.Ref(iNodeNO));
return;
}
if (iSaveLeft == iSaveRight) {//没有子节点
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) {
Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
}
if (mid + 1 <= iQueryRight) {
Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
}
}
void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
if (iSaveLeft == iSaveRight)
{
OnUpdate(m_vSave.Ref(iNodeNO), iSaveLeft, update);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid) {
Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
}
else {
Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
}
OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
}
virtual void OnInit(TSave& save, int iSave) = 0;
virtual void OnQuery(TSave& save) = 0;
virtual void OnUpdate(TSave& save,int iSaveLeft, const TRecord& update) = 0;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
CVectorSave<TSave> m_vSave;
};
template<class TSave = std::tuple<int,int,int>, class TRecord = char, class TSaveCon = CVectorSave<TSave> >
class CMyLineTree :public CSingUpdateLineTree<TSave,TRecord>
{
public:
CMyLineTree(const string& s) :m_s(s), CSingUpdateLineTree<TSave, TRecord>(s.length(), { 0,0,0 }) {
}
void Update(int index, TRecord update) {
m_s[index] = update;
CSingUpdateLineTree<TSave, TRecord>::Update(index, update);
}
protected:
virtual void OnInit(TSave& save, int iSave) override
{
save = { 1,1,1 };
}
virtual void OnQuery(TSave& save) override
{
}
virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
{
save = { 1,1,1 };
}
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
{
int i1 = get<0>(left);//最长前缀
int i2 = max(get<1>(left), get<1>(r));//最长字符串
int i3 = get<2>(r);//最长后缀
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (m_s[mid] == m_s[mid + 1])
{//拼接
i2 = max(i2, get<2>(left) + get<0>(r));
if (mid - iSaveLeft + 1 == i1) {
i1 += get<0>(r);
}
if (iSaveRight - mid == i3) {
i3 += get<2>(left);
}
}
par = { i1,i2,i3 };
}
string m_s;
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
CMyLineTree lineTree(s);
lineTree.Init();
vector<int> vRet;
for (int i = 0; i < queryCharacters.size(); i++) {
lineTree.Update(queryIndices[i], queryCharacters[i]);
const auto [i1, i2, i3] = lineTree.QueryAll();
vRet.emplace_back(i2);
}
return vRet;
}
};
用哈希映射实现
template<class TSave>
class CUnorderMapSave
{
public:
CUnorderMapSave(int iMinIndex, int iMaxIndex, TSave tDefault) :m_iMinIndex(iMinIndex), m_iMaxIndex(iMaxIndex), m_tDefault(tDefault){
}
TSave& Ref(int iNodeNO) {
if (!m_map.count(iNodeNO)) {
m_map[iNodeNO] = m_tDefault;
}
return m_map[iNodeNO];
}
const int m_iMinIndex, m_iMaxIndex;
protected:
const TSave m_tDefault;
unordered_map<int, TSave> m_map;
};
template<class TSave, class TRecord,class TSaveCon >
class CSingUpdateLineTree
{
public:
CSingUpdateLineTree(int iEleSize, TSave tDefault) :m_vSave(0,iEleSize-1, tDefault){
}
CSingUpdateLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) :m_vSave(iMinIndex, iMaxIndex, tDefault) {
}
void Update(int index, TRecord update) {
Update(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, index, update);
}
void Query(int leftIndex, int leftRight) {
Query(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex, leftIndex, leftRight);
}
void Init() {
Init(1, m_vSave.m_iMinIndex, m_vSave.m_iMaxIndex);
}
TSave QueryAll() {
return m_vSave.Ref(1);
}
protected:
void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
{
if (iSaveLeft == iSaveRight) {
OnInit(m_vSave.Ref(iNodeNO), iSaveLeft);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
Init(iNodeNO * 2, iSaveLeft, mid);
Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
}
void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
OnQuery(m_vSave.Ref(iNodeNO));
return;
}
if (iSaveLeft == iSaveRight) {//没有子节点
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) {
Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
}
if (mid + 1 <= iQueryRight) {
Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
}
}
void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
if (iSaveLeft == iSaveRight)
{
OnUpdate(m_vSave.Ref(iNodeNO), iSaveLeft, update);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid) {
Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
}
else {
Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
}
OnUpdateParent(m_vSave.Ref(iNodeNO), m_vSave.Ref(iNodeNO*2), m_vSave.Ref(iNodeNO*2+1), iSaveLeft, iSaveRight);
}
virtual void OnInit(TSave& save, int iSave) = 0;
virtual void OnQuery(TSave& save) = 0;
virtual void OnUpdate(TSave& save,int iSaveLeft, const TRecord& update) = 0;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
TSaveCon m_vSave;
};
template<class TSave = std::tuple<int,int,int>, class TRecord = char, class TSaveCon = CUnorderMapSave<TSave> >
class CMyLineTree :public CSingUpdateLineTree<TSave,TRecord, TSaveCon>
{
public:
CMyLineTree(const string& s) :m_s(s), CSingUpdateLineTree<TSave, TRecord, TSaveCon>(s.length() ,{ 0,0,0 }) {
}
void Update(int index, TRecord update) {
m_s[index] = update;
CSingUpdateLineTree<TSave, TRecord, TSaveCon>::Update(index, update);
}
protected:
virtual void OnInit(TSave& save, int iSave) override
{
save = { 1,1,1 };
}
virtual void OnQuery(TSave& save) override
{
}
virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
{
save = { 1,1,1 };
}
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
{
int i1 = get<0>(left);//最长前缀
int i2 = max(get<1>(left), get<1>(r));//最长字符串
int i3 = get<2>(r);//最长后缀
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (m_s[mid] == m_s[mid + 1])
{//拼接
i2 = max(i2, get<2>(left) + get<0>(r));
if (mid - iSaveLeft + 1 == i1) {
i1 += get<0>(r);
}
if (iSaveRight - mid == i3) {
i3 += get<2>(left);
}
}
par = { i1,i2,i3 };
}
string m_s;
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
CMyLineTree lineTree(s);
lineTree.Init();
vector<int> vRet;
for (int i = 0; i < queryCharacters.size(); i++) {
lineTree.Update(queryIndices[i], queryCharacters[i]);
const auto [i1, i2, i3] = lineTree.QueryAll();
vRet.emplace_back(i2);
}
return vRet;
}
};
再次修改封装类
template<class TSave, class TRecord >
class CSingUpdateLineTree
{
protected:
virtual void OnInit(TSave& save, int iSave) = 0;
virtual void OnQuery(TSave& save) = 0;
virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) = 0;
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};
template<class TSave, class TRecord >
class CVectorSingUpdateLineTree : public CSingUpdateLineTree<TSave, TRecord>
{
public:
CVectorSingUpdateLineTree(int iEleSize, TSave tDefault) :m_iEleSize(iEleSize),m_vSave(iEleSize*4,tDefault){
}
void Update(int index, TRecord update) {
Update(1, 0, m_iEleSize-1, index, update);
}
void Query(int leftIndex, int leftRight) {
Query(1, 0, m_iEleSize - 1, leftIndex, leftRight);
}
void Init() {
Init(1, 0, m_iEleSize - 1);
}
TSave QueryAll() {
return m_vSave[1];
}
protected:
int m_iEleSize;
void Init(int iNodeNO, int iSaveLeft, int iSaveRight)
{
if (iSaveLeft == iSaveRight) {
this->OnInit(m_vSave[iNodeNO], iSaveLeft);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
Init(iNodeNO * 2, iSaveLeft, mid);
Init(iNodeNO * 2 + 1, mid + 1, iSaveRight);
this->OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO*2], m_vSave[iNodeNO*2+1], iSaveLeft, iSaveRight);
}
void Query(int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
this->OnQuery(m_vSave[iNodeNO]);
return;
}
if (iSaveLeft == iSaveRight) {//没有子节点
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (mid >= iQueryLeft) {
Query(iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
}
if (mid + 1 <= iQueryRight) {
Query(iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
}
}
void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
if (iSaveLeft == iSaveRight)
{
this->OnUpdate(m_vSave[iNodeNO], iSaveLeft, update);
return;
}
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (iUpdateNO <= mid) {
Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
}
else {
Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
}
this->OnUpdateParent(m_vSave[iNodeNO], m_vSave[iNodeNO*2], m_vSave[iNodeNO*2+1], iSaveLeft, iSaveRight);
}
vector<TSave> m_vSave;
};
template<class TSave = std::tuple<int, int, int>, class TRecord = char >
class CMyLineTree :public CVectorSingUpdateLineTree<TSave, TRecord>
{
public:
CMyLineTree(const string& s) :m_s(s), CVectorSingUpdateLineTree<TSave, TRecord>(s.length(), { 0,0,0 }) {
}
void Update(int index, TRecord update) {
m_s[index] = update;
CVectorSingUpdateLineTree<TSave, TRecord>::Update(index, update);
}
protected:
string m_s;
virtual void OnInit(TSave& save, int iSave) override
{
save = { 1,1,1 };
}
virtual void OnQuery(TSave& save) override
{
}
virtual void OnUpdate(TSave& save, int iSaveLeft, const TRecord& update) override
{
save = { 1,1,1 };
}
virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) override
{
int i1 = get<0>(left);//最长前缀
int i2 = max(get<1>(left), get<1>(r));//最长字符串
int i3 = get<2>(r);//最长后缀
const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
if (m_s[mid] == m_s[mid + 1])
{//拼接
i2 = max(i2, get<2>(left) + get<0>(r));
if (mid - iSaveLeft + 1 == i1) {
i1 += get<0>(r);
}
if (iSaveRight - mid == i3) {
i3 += get<2>(left);
}
}
par = { i1,i2,i3 };
}
};
class Solution {
public:
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
CMyLineTree lineTree(s);
lineTree.Init();
vector<int> vRet;
for (int i = 0; i < queryCharacters.size(); i++) {
lineTree.Update(queryIndices[i], queryCharacters[i]);
const auto [i1, i2, i3] = lineTree.QueryAll();
vRet.emplace_back(i2);
}
return vRet;
}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s, queryCharacters;
vector<int> queryIndices;
{
s = "babacc", queryCharacters = "bcb", queryIndices = {1,3,3};
auto res = Solution().longestRepeating(s, queryCharacters, queryIndices);
Assert({ 3,3,4 }, res);
}
{
s = "abyzz", queryCharacters = "aa", queryIndices = { 2, 1 };
auto res = Solution().longestRepeating(s, queryCharacters, queryIndices);
Assert({ 2,3 }, res);
}
//CConsole::Out(res);
}
