1. 題目

由 n 個連接的字符串 s 組成字符串 S，記作 S = [s,n]。例如，["abc",3]=“abcabcabc”。

如果我們可以從 s2 中刪除某些字符使其變?yōu)?s1，則稱字符串 s1 可以從字符串 s2 獲得。例如，根據(jù)定義，“abc” 可以從 “abdbec” 獲得，但不能從 “acbbe” 獲得。

現(xiàn)在給你兩個非空字符串 s1 和 s2（每個最多 100 個字符長）和兩個整數(shù) 0 ≤ n1 ≤ 10⁶ 和 1 ≤ n2 ≤ 10⁶。現(xiàn)在考慮字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

請你找出一個可以滿足使[S2,M] 從 S1 獲得的最大整數(shù) M 。

示例： 輸入： s1 ="acb",n1 = 4 s2 ="ab",n2 = 2返回： 2

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-the-repetitions
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 957. N 天后的牢房（查找循環(huán)節(jié)）
機器人大冒險

題目意思是：
給你s1,自己加自己，共n1次，然后s2也一樣，有n2次
后者在前者里找自己的完整子序，最多出現(xiàn)了多少次

• 參考題解

class Solution { public:int getMaxRepetitions(string s1, int n1, string s2, int n2) {if(n1*s1.size() < n2*s2.size())return 0;int len1 = s1.size(), len2 = s2.size(), cnt1 = 0, cnt2 = 0, i, j=0;unordered_map<int,pair<int,int>> m;//j, cnt1, cnt2while(cnt1 < n1){for(i = 0; i < len1; ++i){if(s1[i]==s2[j])j++;if(j==len2)//循環(huán)單個s2j=0,cnt2++;//完整個數(shù)}cnt1++;//s1的個數(shù)if(!m.count(j))//j停在什么位置m[j] = make_pair(cnt1, cnt2);//記錄停在j位置時的cntelse{ //再次找到同一個 j 時，產(chǎn)生循環(huán)節(jié)了int lastcnt1 = m[j].first;//上次的cntint lastcnt2 = m[j].second;int gap1 = cnt1-lastcnt1;//做差，中間間隔有多少個int gap2 = cnt2-lastcnt2;int num = (n1-cnt1)/gap1;//剩余的夠多少個循環(huán)cnt1 += num*gap1;//cnt1 直接+到接近結(jié)束cnt2 += num*gap2;}}return cnt2/n2;//n1個s1可以找到cnt2個s2，可以找到cnt2/n2 個(n2*s2)} };

4 ms 6.3 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 466. 统计重复个数（循环节）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。