作者推荐
本文涉及知识点
二分查找
力扣: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;
}
};