LeetCode 466. 统计重复个数
2020-04-20 16:01:05来源:博客园 阅读 ()
LeetCode 466. 统计重复个数
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 466. 统计重复个数
题目
由 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
一句话:求n1个s1拼接形成的S1删除若干字符后可以分成多少个由n2个s1拼接形成的S2;
思路1-寻找“循环节”然后根据循环节倍数关系求解
“循环节”是指若干个s1拼接起来删除若干字符后能得到一个S2,看图解:
所以,思路是先找“循环节”,然后看n1个s1拼接的S1中有多少个这样的循环节片段,再处理循环节前后剩余的一丢丢残余的s1片段,就能从S1中得到N个完整的s1,N/n2就得到了题目要求解的M值;
步骤:
- 从n1个s1中顺序匹配s2中的字符,记录完整匹配s2的数量,每匹配完一个s1就记录当前匹配到的s2的数量并记录匹配完第一个s1时s2中的待匹配字符索引位置;
- 在后续中若某次匹配完s1后在s2中的停止处索引等于首次的说明找了“循环节”,就可以按照上面说的思路开始数学计算;
- 若始终未找到循环节,则只能暴力匹配完n1个s1,有两种情况:
- s2中的字符有的在s1中不存在,0匹配(可做特例先行判断,避免后面的无意义计算);
- n1个s1处理后的长度恰只够一个S2,1匹配;
算法复杂度:
- len1为s1长度,len2为s2长度,n1即题中n1个s1的n1
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(len1 \ast len2\right)}} $ 最坏时为n1\(\ast\)len1\(\ast\)len2
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n1\right)}} $ 需要n1长度数组存s2的匹配数
算法源码示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年4月19日 下午7:12:10
* @Description: 466. 统计重复个数
*
*/
public class LeetCode_0466 {
}
class Solution_0466 {
/**
* @author: ZhouJie
* @date: 2020年4月19日 下午7:12:31
* @param: @param s1
* @param: @param n1
* @param: @param s2
* @param: @param n2
* @param: @return
* @return: int
* @Description: 1-先尝试寻找循环体,便于计算可拼接的S2数量;
*
*/
public int getMaxRepetitions_1(String s1, int n1, String s2, int n2) {
int len1 = s1.length();
int len2 = s2.length();
// 特例判断
if (n1 == 0 || n2 == 0 || n1 * len1 < n2 * len2) {
return 0;
}
// 特例-若s2中字符有不在s1中的直接返回
char[] cs2 = s2.toCharArray();
for (char c : cs2) {
if (s1.indexOf(c) == -1) {
return 0;
}
}
char[] cs1 = s1.toCharArray();
// 寻找循环体时s2的下标
int index = 0;
int count = 0;
// 在s2中首次匹配到的字符索引位置
int firstIndex = 0;
// 记录在s1的第i次拼接时匹配到的s2的总数
int[] countRdecoder = new int[n1];
for (int i = 0; i < n1; i++) {
for (int j = 0; j < len1; j++) {
// 这是一个往复匹配,匹配到s1中的s2时就右移index,完全匹配s2时记录count并重置index
if (cs2[index] == cs1[j]) {
index++;
if (index == len2) {
count++;
index = 0;
}
}
}
// 首次匹配完时s1的停止位置
if (i == 0) {
firstIndex = index;
}
// 截至本次总匹配s2的数量
countRdecoder[i] = count;
// 若本次的停止位index与第一次时的停止位相同说明找到了循环体,开始数学计算并返回
if (i != 0 && index == firstIndex) {
// 第一部分:找到循环体时循环体内的匹配s1数量乘以n1个s2中有多少个这样的循环体片段(n1 - 1) / i)
int part1 = ((n1 - 1) / i) * (countRdecoder[i] - countRdecoder[0]);
// 第二部分:除去第一部分后剩余部分s2拼接起来可匹配s1的数量
int part2 = countRdecoder[(n1 - 1) % i];
// 总匹配s1的数量除以n2(n2个s1)即得题目要求的M
return (part1 + part2) / n2;
}
}
// 若未找到循环体 ,则直接暴力求解,这种情况基本只能是0或1了
return countRdecoder[n1 - 1] / n2;
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12739885.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:java面向对象
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash