【状态压缩】【动态规划】【C++算法】1125.最小的必要团队

简介: 【状态压缩】【动态规划】【C++算法】1125.最小的必要团队

作者推荐

【广度优先搜索】【网格】【割点】【 推荐】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;

};


目录
打赏
0
1
1
0
36
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
22 12
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
27 15
|
30天前
|
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
48 5
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
基于GA遗传算法的多机无源定位系统GDOP优化matlab仿真
本项目基于遗传算法(GA)优化多机无源定位系统的GDOP,使用MATLAB2022A进行仿真。通过遗传算法的选择、交叉和变异操作,迭代优化传感器配置,最小化GDOP值,提高定位精度。仿真输出包括GDOP优化结果、遗传算法收敛曲线及三维空间坐标点分布图。核心程序实现了染色体编码、适应度评估、遗传操作等关键步骤,最终展示优化后的传感器布局及其性能。
基于深度学习的路面裂缝检测算法matlab仿真
本项目基于YOLOv2算法实现高效的路面裂缝检测,使用Matlab 2022a开发。完整程序运行效果无水印,核心代码配有详细中文注释及操作视频。通过深度学习技术,将目标检测转化为回归问题,直接预测裂缝位置和类别,大幅提升检测效率与准确性。适用于实时检测任务,确保道路安全维护。 简介涵盖了算法理论、数据集准备、网络训练及检测过程,采用Darknet-19卷积神经网络结构,结合随机梯度下降算法进行训练。
一级倒立摆平衡控制系统MATLAB仿真,可显示倒立摆平衡动画,对比极点配置,线性二次型,PID,PI及PD五种算法
本课题基于MATLAB对一级倒立摆控制系统进行升级仿真,增加了PI、PD控制器,并对比了极点配置、线性二次型、PID、PI及PD五种算法的控制效果。通过GUI界面显示倒立摆动画和控制输出曲线,展示了不同控制器在偏转角和小车位移变化上的性能差异。理论部分介绍了倒立摆系统的力学模型,包括小车和杆的动力学方程。核心程序实现了不同控制算法的选择与仿真结果的可视化。
30 15