【动态规划】【二分查找】C++算法 466 统计重复个数

简介: 【动态规划】【二分查找】C++算法 466 统计重复个数

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

二分查找

力扣:466 统计重复个数

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

例如,str == [“abc”, 3] ==“abcabcabc” 。

如果可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。

例如,根据定义,s1 = “abc” 可以从 s2 = “abdbec” 获得,仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串,其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ,以满足 str = [str2, m] 可以从 str1 获得。

示例 1:

输入:s1 = “acb”, n1 = 4, s2 = “ab”, n2 = 2

输出:2

示例 2:

输入:s1 = “acb”, n1 = 1, s2 = “acb”, n2 = 1

输出:1

提示:

1 <= s1.length, s2.length <= 100

s1 和 s2 由小写英文字母组成

1 <= n1, n2 <= 106

动态规划

inxs[i] 记录s1中’a’+i的下标,升序。

分两步:

一,动态规划求dp[i]。dp[i]的含义是:s1[i,m_c1)+s1+s1… 包括s2的最短前缀长度。

dp[i]独立计算:

通过ch遍历s2, ii是s1对应的下标。如果s1不存在ch,则直接返回0。

如果inxs[ch-‘a’]存在大于等于ii的下标ij,则ch和ij对应。ii=ij+1。

如果不存在 ,iTurn ++ ii = inxs[ch-‘a’].front()+1

dp[i] = m_c1*iTurn + ii - i ;

这一步时间复杂度:O(nnlogn)

二,循环i,看[s1,n1]能否包括i个s2。

极端情况,时间复杂度O(108)

s1是100个a,n1是106。s2是’a’。

代码

核心代码

class Solution {
public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    m_c1 = s1.length();
    m_c2 = s2.length();
    vector<int> inxs[26];
    for (int i = 0; i < m_c1; i++)
    {
      inxs[s1[i] - 'a'].emplace_back(i);
    }
    vector<int> dp(m_c1);//dp[i]的含义是:s1[i,m_c1)+s1+s1.... 包括s2的最短前缀长度
    for (int i = 0; i < m_c1; i++)
    {
      int ii = i;
      int iTrun = 0;
      for (int j = 0; j < m_c2; j++)
      {
        const auto& inx = inxs[s2[j] - 'a'];
        if (inx.empty())
        {//某个字符不存在
          return 0;
        }
        const auto it = std::lower_bound(inx.begin(), inx.end(), ii);
        if (inx.end() != it )
        {
          ii = *it+1;
        }
        else
        {
          ii = inx.front() + 1;
          iTrun++;
        }
      }
      dp[i] = m_c1 * iTrun + ii-i;
    }
    const int iHas = m_c1 * n1;
    int iNeed = 0;
    int inx = 0;
    for (int i = 0; ; i++)
    {
      iNeed += dp[inx];
      inx = (inx + dp[inx]) % m_c1;
      if (iNeed > iHas)
      {
        return i/n2;//i最多包括多少个s2
      }
    }
    return 0;
  }
  int m_c1,m_c2;
};

测试用例

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 s1, s2; 
  int n1, n2;
  {
    Solution sln;
    s1 = "acb", n1 = 4, s2 = "ab", n2 = 2;
    auto res = sln.getMaxRepetitions(s1, n1, s2, n2);
    Assert(2, res);
  }
  {
    Solution sln;
    s1 = "acb", n1 = 1, s2 = "acb", n2 = 1;
    auto res = sln.getMaxRepetitions(s1, n2, s2, n2);
    Assert(1, res);
  }
}

优化

inx 取值范围[0,m_c1),所以m_c1+1次必定重复。 重复的部分只计算一次。

vBuf[inx],消耗了first个s2 时,s1消耗了second个字符 ,即s1消耗了second/m_c1个 ,还消耗了s1[0,second%m_c1)。

class Solution {
public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    m_c1 = s1.length();
    m_c2 = s2.length();
    vector<int> inxs[26];
    for (int i = 0; i < m_c1; i++)
    {
      inxs[s1[i] - 'a'].emplace_back(i);
    }
    vector<int> dp(m_c1);//dp[i]的含义是:s1[i,m_c1)+s1+s1.... 包括s2的最短前缀长度
    for (int i = 0; i < m_c1; i++)
    {
      int ii = i;
      int iTrun = 0;
      for (int j = 0; j < m_c2; j++)
      {
        const auto& inx = inxs[s2[j] - 'a'];
        if (inx.empty())
        {//某个字符不存在
          return 0;
        }
        const auto it = std::lower_bound(inx.begin(), inx.end(), ii);
        if (inx.end() != it )
        {
          ii = *it+1;
        }
        else
        {
          ii = inx.front() + 1;
          iTrun++;
        }
      }
      dp[i] = m_c1 * iTrun + ii-i;
    }
    const int iTotal = m_c1 * n1;
    int iHas = 0;
    int inx = 0;
    vector<pair<int,int>> vBuf(m_c1,std::pair<int,int>(-1,-1));//消耗了first个s2 时,s1消耗了second个字符
    vBuf[0] = std::pair<int, int>(0, iHas);
    for (int i = 0; ; i++)
    {
      iHas += dp[inx];
      inx = (inx + dp[inx]) % m_c1;
      if (iHas > iTotal)
      {
        return i/n2;//i最多包括多少个s2
      }
      if (-1 == vBuf[inx].first)
      {
        vBuf[inx] = std::make_pair(i+1, iHas);
      }
      else
      {
        const int subHas =iHas -  vBuf[inx].second ;
        const int subI = (i+1) - vBuf[inx].first;
        i += (iTotal-iHas) / subHas * subI;
        iHas += (iTotal - iHas) / subHas*subHas;
      }
    }
    return 0;
  }
  int m_c1,m_c2;
};

再次优化:动态规划

dp[i][j]的含义是:s1[i,m_c1)+s1+s1… 包括s2[j,m_c2)的最短前缀长度

class Solution {
public:
  int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    m_c1 = s1.length();
    m_c2 = s2.length();
    vector<vector<int>> dp(m_c1, vector<int>(m_c2));//dp[i][j]的含义是:s1[i,m_c1)+s1+s1.... 包括s2[j,m_c2)的最短前缀长度
    for (int j = m_c2 - 1; j >= 0; j--)
    {
      vector<int> inxs;
      for (int i = 0; i < m_c1; i++)
      {
        if (s2[j] == s1[i])
        {
          inxs.emplace_back(i);
        }
      }
      if (inxs.empty())
      {
        return 0;
      }
      for (int i = 0, k = 0; i < m_c1; i++)
      {
        while ((k < inxs.size()) && (inxs[k] < i))
        {
          k++;
        }
        dp[i][j] = (inxs.size() == k) ? (m_c1 - i + inxs.front() + 1) : (inxs[k] - i + 1);
        if (m_c2 - 1 == j)
        {
          continue;
        }
        const int inx = (i + dp[i][j]) % m_c1;
        dp[i][j] += dp[inx][j + 1];
      }
    }
    const int iTotal = m_c1 * n1;
    int iHas = 0;
    int inx = 0;
    vector<pair<int, int>> vBuf(m_c1, std::pair<int, int>(-1, -1));//消耗了first个s2 时,s1消耗了second个字符
    vBuf[0] = std::pair<int, int>(0, iHas);
    for (int i = 0; ; i++)
    {
      iHas += dp[inx][0];
      inx = (inx + dp[inx][0]) % m_c1;
      if (iHas > iTotal)
      {
        return i / n2;//i最多包括多少个s2
      }
      if (-1 == vBuf[inx].first)
      {
        vBuf[inx] = std::make_pair(i + 1, iHas);
      }
      else
      {
        const int subHas = iHas - vBuf[inx].second;
        const int subI = (i + 1) - vBuf[inx].first;
        i += (iTotal - iHas) / subHas * subI;
        iHas += (iTotal - iHas) / subHas * subHas;
      }
    }
    return 0;
  }
  int m_c1, m_c2;
};

2023年1月 版

class Solution {

public:

int getMaxRepetitions(string s1, int n1, string s2, int n2) {

int iCnt1 = 0, iCnt2 = 0, index = 0;

std::unordered_map<int, pair<int, int>> mIndexToCnt;

while (true)

{

for (const auto& ch : s1)

{

if (ch == s2[index])

{

index++;

if (s2.length() == index)

{

index = 0;

iCnt2++;

}

}

}

iCnt1++;

if (iCnt1 == n1)

{//已经匹配完毕

return iCnt2 / n2;

}

if (mIndexToCnt.count(index))

{//找到循环节

break;

}

else

{

mIndexToCnt[index] = { iCnt1, iCnt2 };

}

}

int iLoopCnt1 = iCnt1 - mIndexToCnt[index].first;

int iLoopCnt2 = iCnt2 - mIndexToCnt[index].second;

int iRet = iCnt2 + (n1 - iCnt1) / iLoopCnt1 * iLoopCnt2;

int iRemain = (n1 - iCnt1) % iLoopCnt1;

for (int i = 0; i < iRemain; i++)

{

for (const auto& ch : s1)

{

if (ch == s2[index])

{

index++;

if (s2.length() == index)

{

index = 0;

iRet++;

}

}

}

}

return iRet/n2;

}

};


相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
11天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
28 2
|
1月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
65 2
动态规划算法学习三:0-1背包问题
|
1月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
65 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
120 0
动态规划算法学习二:最长公共子序列
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
1月前
|
算法 C++
【算法解题思想】动态规划+深度优先搜索(C/C++)
【算法解题思想】动态规划+深度优先搜索(C/C++)
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
12天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。