LeetCode1125. 最小的必要团队

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。
示例 1：
输入：req_skills = [“java”,“nodejs”,“reactjs”], people = [[“java”],[“nodejs”],[“nodejs”,“reactjs”]]
输出：[0,2]
示例 2：
输入：req_skills = [“algorithms”,“math”,“java”,“reactjs”,“csharp”,“aws”], people = [[“algorithms”,“math”,“java”],[“algorithms”,“math”,“reactjs”],[“java”,“csharp”,“aws”],[“reactjs”,“csharp”],[“csharp”,“math”],[“aws”,“java”]]
输出：[1,2]
提示：
1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] 由小写英文字母组成
req_skills 中的所有字符串 互不相同
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] 由小写英文字母组成
people[i] 中的所有字符串 互不相同
people[i] 中的每个技能是 req_skills 中的技能
题目数据保证「必要团队」一定存在

动态规划

状态压缩

利用哈希map将字符串转成数字。方便状态压缩。mask &(1 <<i ) 表示第i个技能已经具备。

动态规划的状态

pre[mask] 从前i个人员中选择具备mask技能的最少人数。
dp[mask] 从前i+1个人员中选择具备mask技能的最少人数。

动态规划的转移方程

const int iNewMask = preMask | curMask;
人数必定+1。

动态规划的初始状态

pre[0]=0，其它1000,表示此种状态不存在。

动态规划的填表顺序

依次处理各人员。

动态规划的返回值

vResut[mask] 记录： 转移之前的状态和最后选择的人员。

代码

核心代码

class Solution {
public:
	vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
		unordered_map<string, int> mStrIndex;
		for (const auto& s : req_skills)
		{
			if (!mStrIndex.count(s))
			{
				mStrIndex[s] = mStrIndex.size();
			}
		}
		const int iMaskCount = 1 << mStrIndex.size();
		vector<int> pre(iMaskCount, 1000);
		vector<pair<int, int>> vResult(iMaskCount);
		pre[0] = 0;
		int cur = -1;
		for (const auto& v : people)
		{
			cur++;
			int curMask = 0;
			for (const string& s : v)
			{
				if (mStrIndex.count(s))
				{
					curMask |= (1 << mStrIndex[s]);
				}
			}
			auto dp = pre;//不选择当前人员
			for (int preMask = 0; preMask < iMaskCount; preMask++)
			{
				const int iNewMask = preMask | curMask;
				if (pre[preMask] + 1 < dp[iNewMask])
				{
					dp[iNewMask] = pre[preMask] + 1;
					vResult[iNewMask] = std::make_pair(preMask, cur);
				}
			}
			pre.swap(dp);
		}
		vector<int> vRet;
		for (int mask = iMaskCount - 1; mask > 0; )
		{
			vRet.emplace_back(vResult[mask].second);
			mask = vResult[mask].first;
		}
		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()
{	
	vector<string> req_skills;
	vector<vector<string>> people;
	{
		Solution sln;
		req_skills = { "java","nodejs","reactjs" }, people = { {"java"},{"nodejs"},{"nodejs","reactjs"} };
		auto res = sln.smallestSufficientTeam(req_skills, people);		
	//	Assert(vector<int>{0, 2}, res);
	}
	{
		Solution sln;
		req_skills = { "algorithms","math","java","reactjs","csharp","aws" }, people = { {"algorithms","math","java"},{"algorithms","math","reactjs"},{"java","csharp","aws"},{"reactjs","csharp"},{"csharp","math"},{"aws","java"} };
		auto res = sln.smallestSufficientTeam(req_skills, people);
		//Assert(vector<int>{1, 2}, res);
	}
}

2023年1月 第一版

class Solution {
public:
vector smallestSufficientTeam(vector& req_skills, vector<vector>& people) {
m_iBitNum = req_skills.size();
m_iMaskNum = (1 << m_iBitNum);
for (const auto& s : req_skills)
{
m_mSkillNameToIndex[s] = m_mSkillNameToIndex.size();
}
std::unordered_map<int,int> pre;
pre[0] = 0;
std::unordered_map<int, vector> preIndex(1);
for (int i = 0; i < people.size();i++ )
{
const auto& v = people[i];
std::unordered_map<int, int> dp = pre;
std::unordered_map<int, vector> dpIndex = preIndex;
for (const auto& pr : pre)
{
int iNewMask = pr.first;
for (const auto& s : v)
{
iNewMask |= (1 << m_mSkillNameToIndex[s]);
}
const int iNewNum = pr.second + 1;
if ((!dp.count(iNewMask)) || (iNewNum < dp[iNewMask]))
{
dp[iNewMask] = iNewNum;
dpIndex[iNewMask] = preIndex[pr.first];
dpIndex[iNewMask].push_back(i);
}
}
pre.swap(dp);
preIndex.swap(dpIndex);
}
return preIndex[m_iMaskNum - 1];
}
int m_iMaskNum;
int m_iBitNum;
std::unordered_map<string, int> m_mSkillNameToIndex;
};

2023年1月第二版

class Solution {
public:
vector smallestSufficientTeam(vector& req_skills, vector<vector>& people) {
m_iBitNum = req_skills.size();
m_iMaskNum = (1 << m_iBitNum);
for (const auto& s : req_skills)
{
m_mSkillNameToIndex[s] = m_mSkillNameToIndex.size();
}
std::vector pre(m_iMaskNum,1000);
pre[0] = 0;
std::vector<vector> preIndex(m_iMaskNum);
for (int i = 0; i < people.size();i++ )
{
const auto& v = people[i];
std::vector dp = pre;
std::vector<vector> dpIndex = preIndex;
for (int iMask = 0; iMask < m_iMaskNum; iMask++ )
{
int iNewMask = iMask;
for (const auto& s : v)
{
iNewMask |= (1 << m_mSkillNameToIndex[s]);
}
const int iNewNum = pre[iMask] + 1;
if (iNewNum < dp[iNewMask])
{
dp[iNewMask] = iNewNum;
dpIndex[iNewMask] = preIndex[iMask];
dpIndex[iNewMask].push_back(i);
}
}
pre.swap(dp);
preIndex.swap(dpIndex);
}
return preIndex[m_iMaskNum - 1];
}
int m_iMaskNum;
int m_iBitNum;
std::unordered_map<string, int> m_mSkillNameToIndex;
};

2023年1月 第3版

class Solution {
public:
vector smallestSufficientTeam(vector& req_skills, vector<vector>& people) {
m_iBitNum = req_skills.size();
m_iMaskNum = (1 << m_iBitNum);
for (const auto& s : req_skills)
{
m_mSkillNameToIndex[s] = m_mSkillNameToIndex.size();
}
vector vPeoMask;
for (const auto& v : people)
{
int iMask = 0;
for (const auto& s : v)
{
iMask |= (1 << m_mSkillNameToIndex[s]);
}
vPeoMask.push_back(iMask);
}
std::vector pre(m_iMaskNum,1000);
pre[0] = 0;
std::vector preIndex(m_iMaskNum);
for (int i = 0; i < people.size();i++ )
{
const auto& v = people[i];
std::vector dp = pre;
std::vector dpIndex = preIndex;
for (int iMask = 0; iMask < m_iMaskNum; iMask++ )
{
if (1000 == pre[iMask])
{
continue;
}
const int iNewMask = iMask | vPeoMask[i];
if (iNewMask == iMask)
{
continue;
}
const int iNewNum = pre[iMask] + 1;
if (iNewNum < dp[iNewMask])
{
dp[iNewMask] = iNewNum;
auto llNewPeoMask = (1LL) << i;
dpIndex[iNewMask] = preIndex[iMask] | llNewPeoMask;
}
}
pre.swap(dp);
preIndex.swap(dpIndex);
}
vector ret;
for (int i = 0; i < people.size(); i++)
{
const auto llNewPeoMask = (1LL) << i;
if (llNewPeoMask & preIndex[m_iMaskNum - 1])
{
ret.push_back(i);
}
}
return ret;
}
int m_iMaskNum;
int m_iBitNum;
std::unordered_map<string, int> m_mSkillNameToIndex;
};