音乐网站建设的目的,手工做衣服网站有哪些,小程序搭建的方式,小程序开发的服务怎么样1. 题目
由 n 个连接的字符串 s 组成字符串 S#xff0c;记作 S [s,n]。例如#xff0c;[abc,3]“abcabcabc”。
如果我们可以从 s2 中删除某些字符使其变为 s1#xff0c;则称字符串 s1 可以从字符串 s2 获得。例如#xff0c;根据定义#xff0c;“abc”…1. 题目
由 n 个连接的字符串 s 组成字符串 S记作 S [s,n]。例如[abc,3]“abcabcabc”。
如果我们可以从 s2 中删除某些字符使其变为 s1则称字符串 s1 可以从字符串 s2 获得。例如根据定义“abc” 可以从 “abdbec” 获得但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1 和 s2每个最多 100 个字符长和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2其中 S1[s1,n1] 、S2[s2,n2] 。
请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。
示例
输入
s1 acb,n1 4
s2 ab,n2 2返回
2来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-the-repetitions 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 957. N 天后的牢房查找循环节 机器人大冒险
题目意思是 给你s1,自己加自己共n1次然后s2也一样有n2次 后者在前者里找自己的完整子序最多出现了多少次
参考题解
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, j0;unordered_mapint,pairint,int m;//j, cnt1, cnt2while(cnt1 n1){for(i 0; i len1; i){if(s1[i]s2[j])j;if(jlen2)//循环单个s2j0,cnt2;//完整个数}cnt1;//s1的个数if(!m.count(j))//j停在什么位置m[j] make_pair(cnt1, cnt2);//记录停在j位置时的cntelse{ //再次找到同一个 j 时产生循环节了int lastcnt1 m[j].first;//上次的cntint lastcnt2 m[j].second;int gap1 cnt1-lastcnt1;//做差中间间隔有多少个int gap2 cnt2-lastcnt2;int num (n1-cnt1)/gap1;//剩余的够多少个循环cnt1 num*gap1;//cnt1 直接到接近结束cnt2 num*gap2;}}return cnt2/n2;//n1个s1可以找到cnt2个s2可以找到cnt2/n2 个(n2*s2)}
};4 ms 6.3 MB
