flash网站源码下载,企业管理咨询是做什么,排位及资讯,做网站用小公司还是大公司【问题描述】466. 统计重复个数
由 n 个连接的字符串 s 组成字符串 S#xff0c;记作 S [s,n]。例如#xff0c;[abc,3]“abcabcabc”。如果我们可以从 s2 中删除某些字符使其变为 s1#xff0c;则称字符串 s1 可以从字符串 s2 获得。例如#xff0c;根据定义…【问题描述】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
【解答思路】
1. 暴力解法
在s1的拼接字符串中 遍历找到找到一个 s2记录使用了s1的个数s1总个数/含单个s2循环体/s2总个数 时间复杂度O(N^2) 空间复杂度O(1)
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {char[] c1 s1.toCharArray();char[] c2 s2.toCharArray();/*** index为c2的索引 num1当前使用了ss1的个数 num2当前匹配的ss2的个数*/int index 0 , num1 0, num2 0;while(num1 n1){for(int i 0 ; i c1.length ; i){if(c1[i] c2[index]){if(index c2.length - 1) {index 0;num2 ;}else{index ;} }}num1;}return num2 / n2;}
2. 优化
1.分为 0 ~n1-1次拼接s1记录下第0次 时count即s2出现的次数 和 index即指向s2的坐标 2.循环找寻坏体判断为循坏体的条件是i!0不是第0次 indexpre_index 当前指向s2的坐标第0次拼接结束后指向s2的坐标 3.如果找到了循环体那么return 循环体个数 * (单个循环体包含的s2数目) 除去所有循环体字符串后剩余拼接在一起的形成的字符串可以找出s2个数/ n2可以配合代码看 4.没有找到循环体那就直接返回迄今为止记录到的count数/n2即countRecorder[n-1]/n2 时间复杂度O(N) 空间复杂度O(1)
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {int len1 s1.length();int len2 s2.length();// 有0的话不多说直接滚0if (len1 0 || len2 0 || n1 0 || n2 0) {return 0;}char[] chars1 s1.toCharArray();char[] chars2 s2.toCharArray();int index 0;//记录s2的坐标int count 0;//记录s1包含s2的个数int[] countRecorder new int[n1 1];//记录第i次拼接时候累积的countint pre_index0;//记录第0次结束后的index//开始拼接找循环体( 看作 0~n-1 次)for (int i 0; i n1; i) {// 第i次拼接s1,更新index和countfor (int j 0; j len1; j) {if (chars1[j] chars2[index]) {//匹配成功indexindex;}if (index chars2.length) {//完成一个s2的匹配countindex 0;count;}}countRecorder[i] count;//记录第0次到第i次拼接出现的s2匹配次数countif(i0) {//记录第0次的下标indexpre_index index;}//符合该条件代表找到循环体了可以缩短搜索时间if(i!0 pre_index index) {//System.out.println(countRecorder[0]);int pre countRecorder[0];//第一次拼接的时候记录的countint loop_part ((n1-1) / i) * (countRecorder[i]-pre);//除去循环体部分其他部分合并在一起// x (n1-1)%i -- 除去循环体还等于x个s2拼接 int other_part countRecorder[(n1-1) % i];//返回值为出现的s2的总次数return (loop_partother_part) / n2;}}//未找到循环只能暴力了裂开return countRecorder[n1-1] / n2;}
【总结】
1. 数组拼接题目 重复延长思想 找规律
2. 完全不知道如何入手 过于菜 不断总结整理归纳 参考链接https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-_jian-dan-yi-dong-by-xiang/
