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

作者推荐

【动态规划】458:可怜的小猪

涉及知识点

动态规划 二分查找

力扣: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;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

测试用例

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);
	}

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

优化

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;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

再次优化：动态规划

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;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

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> 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;
}
};

扩展阅读

视频课程

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

群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/135477219"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！