作者推荐
【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子
本文涉及知识点
状态压缩
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;
};
