AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【状态压缩】【动态规划】【C++算法】691贴纸拼词

2024-01-22 151
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【状态压缩】【动态规划】【C++算法】691贴纸拼词

LeetCode:691 贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

示例 1：

输入： stickers = [“with”,“example”,“science”], target = “thehat”

输出：3

解释：

我们可以使用 2 个 “with” 贴纸，和 1 个 “example” 贴纸。

把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。

此外，这是形成目标字符串所需的最小贴纸数量。

示例 2:

输入：stickers = [“notice”,“possible”], target = “basicbasic”

输出：-1

解释：我们不能通过剪切给定贴纸的字母来形成目标“basicbasic”。

提示:

n == stickers.length

1 <= n <= 50

1 <= stickers[i].length <= 10

1 <= target.length <= 15

stickers[i] 和 target 由小写英文单词组成

封装类

假定target串有个n1字符，数量分别为m_vMax[0] m_vMax[1]…m_vMax[n1-1]。

对于某个stickers串，忽略target中没有的字符。target第0 1 2… 个字符在sticker的数量为vNum[0],vNum[1]…

则第0个字符的mask为1*vNum[0]

第1个字符的mask为(m_vMax[0]+1)*vNum[1]

…

第i个字符的mask为：Mul[ 0 , i − 1 ] j \Large^j_{[0,i-1]}[0,i−1]j(vMax[j]+1)*vNum[i]

总mask 为各字符mask之和。

注意： 无论如何vNum[i]都大于等于0，小于等于m_vMax[i]

class CMask
{
public:
  void Add(int iMax)//当前最高位范围[0,iMax]
  {
    m_vMax.emplace_back(iMax);
    m_iMaskCount *= (iMax + 1);
  }
  vector<int> FromMask(int iMask)
  {
    vector<int> vNums;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      vNums.emplace_back(iMask % (m_vMax[i] + 1));
      iMask /= (m_vMax[i] + 1);
    }
    return vNums;
  }
  int ToMask(const vector<int>& vNums,int iMul=1)
  {
    int iMask = 0;
    int iUnit = 1;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      iMask += iUnit * min(m_vMax[i],vNums[i]* iMul);
      iUnit *= (m_vMax[i]+1);
    }
    return iMask;
  }
  int MaskSubVector(int iMask, const vector<int>& vNums, const int iMul = 1)
  {
    int iNewMask = 0;
    int iUnit = 1;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      int cur = iMask % (m_vMax[i] + 1);
      cur -= vNums[i] * iMul;
      cur = max(0, cur);
      iNewMask += iUnit * cur;
      iMask /= (m_vMax[i] + 1);
      iUnit *= (m_vMax[i]+1);
    }
    return iNewMask;
  }
  int NeedGroupCount(const vector<int>& need, const vector<int>& has)
  {
    int iMax = 0;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      if (has[i] <= 0)
      {
        continue;
      }
      iMax = max(iMax,need[i] / has[i]+ (0 != need[i] % has[i]));
    }
    return iMax;
  }
public:
  int MaskCount()const
  {
    return m_iMaskCount;
  } 
  int BitCount()const
  {
    return m_vMax.size();
  }
protected:
  int m_iMaskCount = 1;
  vector<int> m_vMax;
};
class CStrMask : public CMask
{
public:
  CStrMask(const string& target)
  {
    vector<int> vCount;
    for (const auto& ch : target)
    {
      if (mCharToIndex.count(ch))
      {
        vCount[mCharToIndex[ch]]++;
      }
      else
      {
        mCharToIndex[ch] = vCount.size();
        vCount.emplace_back(1);
      }
    }
    for (const auto& cnt : vCount)
    {
      CMask::Add(cnt);
    }
  }
  vector<int> GetVector(const string& s )
  {
    vector<int> vCharNums(m_vMax.size());
    for (const char& ch : s)
    {
      if (mCharToIndex.count(ch))
      {
        auto& i = vCharNums[mCharToIndex[ch]];
        if (i < m_vMax[mCharToIndex[ch]])
        {
          i++;
        }       
      }
    }
    return vCharNums;
  }
protected:
  unordered_map<char, int> mCharToIndex;
private:
  void Add(int iMax) {};
};

动态规划

动态规划的状态表示

pre[iMask] 表示利用前i-1个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。1000表示无法达成。

dp[iMask] 表示利用前i 个贴纸，达到未完成的字符状态为iMask的消耗的最少贴纸数。

动态规划的转移方程

iPreMask 当前贴纸 使用的贴纸数量 如果状态发生变化，则更新状态。

动态规划的填表顺序

对于每个合法的iPreMask，计算当前贴纸最多需要多少份。三层循环：第一层，枚举各贴纸。第二层，枚举pre各状态。第三层：枚举当前贴纸使用的数量。每次处理还要枚举各字符。

故总时间复杂度为：O(50*2151515)

动态规划的初始状态

pre[iMaskCount-1=0 其它值为1000。

动态规划的返回值

pre[0]

代码

核心代码

class Solution {
public:
  int minStickers(vector<string>& stickers, string target) {
    CStrMask mask(target);
    vector<vector<int>> vMaskToCounts(mask.MaskCount());
    for (int i = 0; i < mask.MaskCount(); i++)
    {
      vMaskToCounts[i] = mask.FromMask(i);
    }
    vector<int> vPre(mask.MaskCount(), 1000);
    vPre[mask.MaskCount() - 1] = 0;
    for (const auto s : stickers)
    {
      auto vCharNums = mask.GetVector(s);
      vector<int> dp = vPre;//不选择
      for (int iPre = 0; iPre < mask.MaskCount(); iPre++)
      {
        if (vPre[iPre] >= 1000)
        {
          continue;
        }
        const int iSelMax = mask.NeedGroupCount(vMaskToCounts[iPre], vCharNums);
        for (int iSel = 1; iSel <= iSelMax; iSel++)
        {
          const int iNewMask = mask.MaskSubVector(iPre, vCharNums, iSel);
          dp[iNewMask] = min(dp[iNewMask], vPre[iPre] + iSel);
        }
      }
      vPre.swap(dp);
    }
    return (vPre[0] >= 1000) ? -1 : vPre[0];
  }
};

测试用例

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> stickers;
  string target;
  {
    Solution sln;
    stickers = { "travel", "quotient", "nose", "wrote", "any" }, target = "lastwest";
    auto res = sln.minStickers(stickers, target);
    Assert(4, res);
  }
  {
    Solution sln;
    stickers = { "with", "example", "science" }, target = "thehat";
    auto res = sln.minStickers(stickers, target);
    Assert(3, res);
  }
  {
    Solution sln;
    stickers = { "notice", "possible" }, target = "basicbasic";
    auto res = sln.minStickers(stickers, target);
    Assert(-1, res);
  }
  {
    Solution sln;
    stickers = { "right", "ten", "year", "share", "period", "paper", "expect", "village", "home", "happen", "ring", "sat", "even", "afraid", "paint", "self", "range", "camp", "note", "read", "paragraph", "run", "basic", "fill", "week", "his", "star", "power", "any", "colony", "object", "free", "dark", "said", "chick", "true", "glad", "child", "room", "lost", "am", "cry", "quiet", "crease", "while", "race", "fun", "found", "dream", "once" }, target = "materialhalf";
    auto res = sln.minStickers(stickers, target);
    Assert(4, res);
  }
  {
    Solution sln;
    stickers = { "indicate","why","finger","star","unit","board","sister","danger","deal","bit","phrase","caught","if","other","water","huge","general","read","gold","shall","master","men","lay","party","grow","view","if","pull","together","head","thank","street","natural","pull","raise","cost","spoke","race","new","race","liquid","me","please","clear","could","reply","often","huge","old","nor" }, target = "fhhfiyfdcwbycma";
    auto res = sln.minStickers(stickers, target);
    Assert(9, res);
  }
}

改进简洁版，性能略差

不区分dp pre，因为一个贴纸可以无限使用。无论是pre[iMask]和dp[iMask] 都可增加贴纸。

动态规划的状态表示

状态压缩：如果target第i位已经贴好，则此位为1；否则此位为0。

dp[iMask] 已经完成iMask 消耗的最少贴纸数。

动态规划的转移方程。

对应每个mask，只需要考虑一个当前贴纸。比如： 目标串为aaa，贴纸为a。状态0只考虑一个贴纸。状态1只考虑1个贴纸，总共2个贴纸。状态3只考虑1个贴纸，总共3个贴纸。

如果目标串有多个相同字符，只需要匹配第一字符。“???” 第一张贴纸后，变成"a??" 不需要考虑“?a?"

方案一：第i步匹配第1个a，第j个步匹配第2个a。

方案二：第i步匹配第2个a，第j个步匹配第1个a。

如果方案二，能达到目标，那方案一显然也能达到目标。

iPreMask等于iNewMask 也不用排除，因为新值比旧值大1，必定被淘汰。

class Solution {
public:
  int minStickers(vector<string>& stickers, string target) {
    const int iMaskCount = 1 << target.size();
    vector<int> dp(iMaskCount, 1000);
    dp[0] = 0;
    for (const auto s : stickers)
    {
      int cnt1[26] = { 0 };
      for (const auto& ch : s)
      {
        cnt1[ch - 'a']++;
      }
      for (int iPreMask = 0; iPreMask < iMaskCount; iPreMask++)
      {
        int cnt[26] = { 0 };
        memcpy(cnt, cnt1, sizeof(cnt1));
        int iNewMask = iPreMask;
        for (int j = 0; j < target.size(); j++)
        {
          if (iPreMask & (1 << j))
          {
            continue;//已经拼成
          }
          if (cnt[target[j] - 'a'])
          {
            cnt[target[j] - 'a']--;
            iNewMask |= (1 << j);
          }
        }
        dp[iNewMask] = min(dp[iNewMask], dp[iPreMask] + 1);
      }   
    }
    return (dp.back() >= 1000) ? -1 : dp.back();
  }
};

2023年1月第一版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
for (auto& ch : target)
{
m_mTarget[ch]++;
}
std::unordered_set hasMask;
hasMask.insert(0);
std::unordered_map preMaskNum;
preMaskNum[0] = 0;
for (auto& s : stickers)
{
std::unordered_map mCur;
for (auto& ch : s)
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
std::unordered_map dp = preMaskNum;
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
for (const auto& preMask : preMaskNum )
{
std::unordered_map mPre;
ParseMask(mPre, preMask.first);
bool bAdd = true;
int iNum = preMask.second;
while (bAdd)
{
bAdd = false;
for (const auto it : mCur)
{
if (m_mTarget[it.first] > mPre[it.first])
{
bAdd = true;
mPre[it.first] = min(m_mTarget[it.first], mPre[it.first] + mCur[it.first]);
}
}
if (bAdd)
{
iNum++;
const int iMask = MakeMask(mPre);
if (dp.count(iMask))
{
dp[iMask] = min(dp[iMask], iNum);
}
else
{
dp[iMask] = iNum;
}
}
}
}
preMaskNum.swap(dp);
}
int iMaskTargt = MakeMask(m_mTarget);
if (preMaskNum.end() == preMaskNum.find(iMaskTargt))
{
return -1;
}
return preMaskNum[iMaskTargt];
}
int MakeMask(const std::unordered_map& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map& nums, int iMask)
{
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second+1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second+1);
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
std::string m_target;
std::unordered_map m_mTarget;
};

2023年1月第2版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector> mAllCharNum;
{
std::unordered_set hasMask;
hasMask.insert(0);
for (int i = stickers.size() - 1; i >= 0; i–)
{
std::unordered_map mCur;
for (auto& ch : stickers[i])
{
if (m_mTarget.count(ch))
{
mCur[ch]++;
}
}
const int iCurMask = MakeMask(mCur);
if (hasMask.count(iCurMask))
{
continue;
}
hasMask.insert(iCurMask);
mAllCharNum.push_back(mCur);
}
}
std::unordered_set setPreMask,setHasDo;
setPreMask.insert(m_iTargetMask);
setHasDo.insert(m_iTargetMask);
for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
{
std::unordered_set dp;
for (auto& preMask : setPreMask)
{
std::unordered_map mPre;
ParseMask(mPre, preMask);
for (auto& mCur : mAllCharNum)
{
const int iSubMask = GetSubMask(mPre, mCur);
if (0 == iSubMask)
{
continue;
}
const int iNewMask = preMask - iSubMask;
if (setHasDo.count(iNewMask))
{
continue;
}
if (iNewMask == 0 )
{
return iOpeNum;
}
setHasDo.insert(iNewMask);
dp.insert(iNewMask);
}
}
setPreMask.swap(dp);
vector> mAllTmp;
for (auto& it : setPreMask)
{
std::unordered_map tmp;
ParseMask(tmp, it);
mAllTmp.push_back(tmp);
}
}
return -1;
}
int GetSubMask(const std::unordered_map& mPre, const std::unordered_map& mCur)
{
int iSubMask = 0;
for (auto& cur : mCur)
{
auto pre = mPre.find(cur.first);
if (pre->second )
{
iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-‘a’];
}
}
return iSubMask;
}
int MakeMask(const std::unordered_map& nums)const
{
int iMask = 0;
for (const auto& mm : m_mTarget )
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && ( it->second > 0 ))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
void ParseMask(std::unordered_map& nums, int iMask)
{
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
const int iMul = m_vCharMul[it->first-‘a’];
nums[it->first] = iMask / iMul;
iMask %= iMul;
}
}
void Init()
{
for (auto& ch : m_target)
{
m_mTarget[ch]++;
}
m_iTargetMask = MakeMask(m_mTarget);
int iMul = 1;
for (auto& it : m_mTarget)
{
iMul *= (it.second + 1);
}
for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
{
iMul /= (it->second + 1);
m_vCharMul[it->first - ‘a’] = iMul;
}
}
std::string m_target;
int m_iTargetMask;
std::unordered_map m_mTarget;
int m_vCharMul[26] ;
};

2023年1月第三版

class Solution {
public:
int minStickers(vector& stickers, string target) {
m_target = target;
Init();
vector<std::unordered_map<char, int>> mAllCharNum;
   {
     std::unordered_set<int> hasMask;
     hasMask.insert(0);
     for (int i = stickers.size() - 1; i >= 0; i--)
     {
       std::unordered_map<char, int> mCur;
       for (auto& ch : stickers[i])
       {
         if (m_mTarget.count(ch))
         {
           mCur[ch]++;
         }
       }
       const int iCurMask = MakeMask(mCur);
       if (hasMask.count(iCurMask))
       {
         continue;
       }
       hasMask.insert(iCurMask);
       mAllCharNum.push_back(mCur);
     }
   }
   std::unordered_set<int> setPreMask,setHasDo;
   setPreMask.insert(m_iTargetMask);
   setHasDo.insert(m_iTargetMask);
   for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
   {
     std::unordered_set<int> dp;
     for (auto& preMask : setPreMask)
     {
       std::unordered_map<char, int> mPre;
       ParseMask(mPre, preMask);
       char chFristNeedChar = 0;
       for (auto& it : mPre)
       {
         if (it.second > 0)
         {
           chFristNeedChar = it.first;
           break;
         }
       }
       for (auto& mCur : mAllCharNum)
       {
         if ((0 == mCur.count(chFristNeedChar)) || (mCur[chFristNeedChar] <= 0 ))
         {
           continue;
         }
         const int iSubMask = GetSubMask(mPre, mCur);
         if (0 == iSubMask)
         {
           continue;
         }
         const int iNewMask = preMask - iSubMask;
         if (setHasDo.count(iNewMask))
         {
           continue;
         }
         if (iNewMask == 0 )
         {
           return iOpeNum;
         }
         setHasDo.insert(iNewMask);
         dp.insert(iNewMask);
       }
     }
     setPreMask.swap(dp);
     vector<std::unordered_map<char, int>> mAllTmp;
     for (auto& it : setPreMask)
     {
       std::unordered_map<char, int> tmp;
       ParseMask(tmp, it); 
       mAllTmp.push_back(tmp);
     }
   }
   return -1;
 }
 int GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
 {
   int iSubMask = 0;
   for (auto& cur : mCur)
   {
     auto pre = mPre.find(cur.first);
     if (pre->second )
     {
       iSubMask += min(pre->second, cur.second) * m_vCharMul[cur.first-'a'];
     }
   }
   return iSubMask;
 }
 int MakeMask(const std::unordered_map<char, int>& nums)const
 {
   int iMask = 0;
   for (const auto& mm : m_mTarget )
   {
     auto it = nums.find(mm.first);
     if ((nums.end() != it) && ( it->second > 0 ))      
     {
       iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
     }
     else
     {
       iMask = iMask * (mm.second + 1);
     }
   }
   return iMask;
 }
 void ParseMask(std::unordered_map<char, int>& nums, int iMask)
 {
   for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
   {
     const int iMul = m_vCharMul[it->first-'a'];
     nums[it->first] = iMask / iMul;
     iMask %= iMul;
   }
 }
 void Init()
 {
   for (auto& ch : m_target)
   {
     m_mTarget[ch]++;
   }
   m_iTargetMask = MakeMask(m_mTarget);
   int iMul = 1;
   for (auto& it : m_mTarget)
   {
     iMul *= (it.second + 1);
   }
   for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
   {
     iMul /= (it->second + 1);
     m_vCharMul[it->first - 'a'] = iMul;
   }
 }
 std::string m_target;
 int m_iTargetMask;
 std::unordered_map<char, int> m_mTarget;
 int m_vCharMul[26] ;

};

2023年1月 第4版

class CCTestHash
{
public:
std::size_t operator()(const std::unordered_map& nums) const
{
return MakeMask(nums);
}
static int MakeMask(const std::unordered_map& nums)
{
int iMask = 0;
for (const auto& mm : m_mTarget)
{
auto it = nums.find(mm.first);
if ((nums.end() != it) && (it->second > 0))
{
iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
}
else
{
iMask = iMask * (mm.second + 1);
}
}
return iMask;
}
static void Init()
 {
  m_mTarget.clear();
   for (auto& ch : m_target)
   {
     m_mTarget[ch]++;
   }
   m_iTargetMask = MakeMask(m_mTarget);
   int iMul = 1;
   for (auto& it : m_mTarget)
   {
     iMul *= (it.second + 1);
   }
   for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
   {
     iMul /= (it->second + 1);
     m_vCharMul[it->first - 'a'] = iMul;
   }
 }
static std::string m_target;
static int m_iTargetMask;
static std::unordered_map<char, int> m_mTarget;
static int m_vCharMul[26];
};
std::string CCTestHash::m_target;
int CCTestHash::m_iTargetMask;
std::unordered_map CCTestHash::m_mTarget;
int CCTestHash::m_vCharMul[26];
class Solution {
public:
int minStickers(vector& stickers, string target) {
CCTestHash::m_target = target;
CCTestHash::Init();
std::unordered_set<std::unordered_map<char, int>, CCTestHash> hasMask;
   {       
     for (int i = stickers.size() - 1; i >= 0; i--)
     {
       std::unordered_map<char, int> mCur;
       for (auto& ch : stickers[i])
       {
         if (m_testHask.m_mTarget.count(ch))
         {
           mCur[ch]++;
         }
       }
       if (0 == mCur.size())
       {
         continue;
       }
       if (hasMask.count(mCur))
       {
         continue;
       }
       hasMask.insert(mCur);
     }
   }
   std::unordered_set<std::unordered_map<char, int>, CCTestHash> setPreMask, setHasDo;
   setPreMask.insert(CCTestHash::m_mTarget);
   setHasDo.insert(CCTestHash::m_mTarget);
   for (int iOpeNum = 1; iOpeNum <= target.length(); iOpeNum++)
   {
     std::unordered_set<std::unordered_map<char, int>, CCTestHash> dp;
     for (auto& mPre : setPreMask)
     {
       char chFristNeedChar = 0;
       for (auto& it : mPre)
       {
         if (it.second > 0)
         {
           chFristNeedChar = it.first;
           break;
         }
       }
       for (auto& mCur : hasMask)
       {
         if ((0 == mCur.count(chFristNeedChar)) || (mCur.find(chFristNeedChar)->second <= 0 ))
         {
           continue;
         }
         auto newMask = GetSubMask(mPre, mCur);
         if (setHasDo.count(newMask))
         {
           continue;
         }
         if (CCTestHash::MakeMask(newMask) == 0)
         {
           return iOpeNum;
         }
         setHasDo.insert(newMask);
         dp.insert(newMask);
       }
     }
     setPreMask.swap(dp);
   }
   return -1;
 }
 std::unordered_map<char, int> GetSubMask(const std::unordered_map<char, int>& mPre, const std::unordered_map<char, int>& mCur)
 {
   std::unordered_map<char, int> vRet;
   for (auto& pre : mPre)
   {
     auto cur = mCur.find(pre.first);
     if (mCur.end() != cur)
     {
       vRet[pre.first] = max(0, pre.second - cur->second);
     }
     else
     {
       vRet[pre.first] = pre.second;
     }
   }
   return vRet;
 }
 /*
 int MakeMask(const std::unordered_map<char, int>& nums)const
 {
   int iMask = 0;
   for (const auto& mm : m_mTarget )
   {
     auto it = nums.find(mm.first);
     if ((nums.end() != it) && ( it->second > 0 ))      
     {
       iMask = iMask * (mm.second + 1) + min(mm.second, it->second);
     }
     else
     {
       iMask = iMask * (mm.second + 1);
     }
   }
   return iMask;
 }
 void ParseMask(std::unordered_map<char, int>& nums, int iMask)
 {
   for (auto it = m_mTarget.begin(); it != m_mTarget.end(); ++it)
   {
     const int iMul = m_vCharMul[it->first-'a'];
     nums[it->first] = iMask / iMul;
     iMask %= iMul;
   }
 }
 */
 CCTestHash m_testHask;

};


扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

文章标签：
云数据库 ClickHouse
算法
C++
测试技术
C#
关键词：
动态规划算法
C++算法
算法动态规划
算法c++
动态规划C++
闻缺陷则喜何志丹
目录
相关文章
varin
|
2月前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析：0-1背包问题
0-1背包问题是经典的组合优化问题，目标是在给定物品重量和价值及背包容量限制下，选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决，通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值，利用状态转移方程避免重复计算子问题，从而高效求解最优解。
varin
445 1
陌陌谣
|
6月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下，局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段，已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”，实时捕获每台电脑屏幕上的操作动态。然而，面对海量监控数据，实现高效数据存储与快速检索，已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法，深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”，并通过详尽的代码示例，展现其强大功能与应用价值。
陌陌谣
158 2
游客akle7anmklvj6
|
7月前
|
存储 算法 C++
Windows共享文件：探秘C++实现的B树索引算法奇境
在数字化时代，Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性，在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用，通过C++实现具体代码，展示其构建文件索引、优化数据存储的能力，提升文件检索效率。B树通过减少磁盘I/O操作，确保查询高效，为企业和个人提供流畅的文件共享体验。
游客akle7anmklvj6
297 3
陌陌谣
|
8月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中，迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点，确保高效稳定的网络环境。该算法通过计算最短路径，提升数据传输速率与稳定性，实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用，为企业信息化建设提供有力支持。
陌陌谣
247 15
游客akle7anmklvj6
|
8月前
|
运维 监控 算法
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图（Graph）数据结构，每台电脑作为顶点，网络连接作为边，可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索（DFS）的连通性检测算法，用于判断两节点间是否存在路径，助力故障排查与流量优化。C++的高效性能结合图算法，为保障网络秩序与信息安全提供了坚实基础，未来可进一步优化以应对无线网络等新挑战。
游客akle7anmklvj6
286 8
游客akle7anmklvj6
|
8月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中，公司局域网管理至关重要。哈希表作为一种高效的数据结构，通过哈希函数将关键值（如IP地址、账号）映射到数组索引，实现快速的插入、删除与查找操作。例如，在员工登录验证和设备信息管理中，哈希表能显著提升效率，避免传统线性查找的低效问题。本文以C++为例，展示了哈希表在局域网管理中的具体应用，包括设备MAC地址与IP分配的存储与查询，并探讨了优化哈希函数和扩容策略，确保网络管理高效准确。
游客akle7anmklvj6
157 1
陌陌谣
|
4月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表（Skip List）是一种基于概率的数据结构，适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作，时间复杂度为 $O(\log n)$，优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色，具备实现简单、支持范围查询等优势，是企业网络监控中动态数据管理的理想选择。
陌陌谣
148 0
陌陌谣
|
6月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用，通过C++实现其构建与查询功能，显著提升多维数据处理效率。KD树作为一种二叉空间划分结构，适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法，基于KD树的方案检索效率提升2-3个数量级，但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
陌陌谣
181 17
陌陌谣
|
5月前
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表（ACL）实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表（ACL）的应用，分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型，展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用，并提出性能优化及结合机器学习等未来研究方向。
陌陌谣
151 4
陌陌谣
|
5月前
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制：URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法，旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能，实验表明该方法可将内存占用降至传统方案的八分之一，查询速度提升约40%，假阳性率可控。研究为优化企业网络管理提供了新思路，并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
陌陌谣
160 0

热门文章

最新文章

  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
  • 2
    Visual C++运行库、.NET Framework和DirectX运行库的作用及常见问题解决方案，涵盖MSVCP140.dll丢失、0xc000007b错误等典型故障的修复方法
  • 3
    给我介绍一些C++中引用的使用注意事项
  • 4
    率先实现后量子安全算法技术落地上车！阿里云与小鹏汽车签署后量子加密安全合作协议
  • 5
    要不要做算法、大模型备案？看这个流程图就明白了！
  • 6
    【机器学习算法篇】K-近邻算法
  • 7
    别再用均值填充了！MICE算法教你正确处理缺失数据
  • 8
    从零构建短视频推荐系统：双塔算法架构解析与代码实现
  • 9
    DDMA-MIMO雷达多子带相干累积目标检测算法——论文阅读
  • 10
    137_安全强化：输入过滤与水印 - 实现输出水印的检测算法与LLM安全防护最佳实践
  • 1
    Java 与 C++ 区别深入剖析及应用实例详解
    504
  • 2
    基于 C++ 布隆过滤器算法的局域网上网行为控制：URL 访问过滤的高效实现研究
    160
  • 3
    c++的哈希表、哈希桶的介绍与实现
    128
  • 4
    c++ 红黑树（带头结点）（k，k型）
    139
  • 5
    c++ 红黑树（自平衡二叉搜索树）（k，v型）
    147
  • 6
    c++--多态
    112
  • 7
    c++--继承
    139
  • 8
    c++模板进阶操作——非类型模板参数、模板的特化以及模板的分离编译
    206
  • 9
    c++模板初阶----函数模板与类模板
    158
  • 10
    c与c++的内存管理
    106

    • 相关课程

    更多
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • C++ 入门教程开发文档
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
    • 下一篇
    阿里云弹性公网IP线路类型【BGP(多线)_精品】是什么意思？