Leetcode 466 - 统计重复个数
2020-04-24 16:03:13来源:博客园 阅读 ()
Leetcode 466 - 统计重复个数
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
提交答案
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
int len1 = s1.length();
int len2 = s2.length();
char[] s1Chars = s1.toCharArray();
char[] s2Chars = s2.toCharArray();
int index2 = 0;
int s2RepeatTimes = 0;
for (int i = 0; i < n1; i++) {
for (int index1 = 0; index1 < len1; index1++) {
if (s1Chars[index1] == s2Chars[index2]) {
index2++;
if (index2 == len2) {
index2 = 0;
s2RepeatTimes++;
}
}
}
}
return s2RepeatTimes / n2;
}
执行用时: 1848 ms , 在所有 Java 提交中击败了 7.32% 的用户
内存消耗: 37.6 MB , 在所有 Java 提交中击败了 100.00% 的用户
题解反思
这道题自己第一遍并没有做出来,提交了一个 超出内存限制 的答案,我想先分享一下自己写的错误答案吧,这也是我看到这道题的第一思路。
class Solution {
public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
final char[] s1Chars = s1.toCharArray();
final char[] s2Chars = s2.toCharArray();
final Stack<Character> s1Stack = fillStack(n1, s1Chars);
Stack<Character> s2Stack = fillStack(n2, s2Chars);
int repetitions = 1;
while (s1Stack.size() != 0) {
if (s2Stack.size() == 0) {
++repetitions;
s2Stack = fillStack(n2, s2Chars);
}
final Character s1Top = s1Stack.peek();
final Character s2Top = s2Stack.peek();
if (s1Top.equals(s2Top)) {
s1Stack.pop();
s2Stack.pop();
} else {
s1Stack.pop();
}
}
if (s2Stack.size() != 0) {
--repetitions;
}
return repetitions;
}
private Stack<Character> fillStack(int n, char[] chars) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < n; i++) {
for (char c : chars) {
stack.push(c);
}
}
return stack;
}
}
我自己的思路是非常粗暴的,我想先把 S1 和 S2 都构建出来成为两个栈,然后分别从 S1 和 S2 中向外 peek
一个值,当两者相同时,即匹配成功,再分别从 S1 和 S2 中删除栈顶的值(pop()
),每次将 S2 对应的栈中的值删除完后,就再次填充一下 S2 栈,并累计加一重复的次数。
整体的思路很简单直接,但是当自己提交了答案遇到了超出内存限制的问题后才恍然大悟,在做这道题时考虑的真的是太少了。题目中已经明说了s1?和 s2(每个最多 100 个字符长)且 0 ≤ n1 ≤ 106?和 1 ≤ n2 ≤ 106
,这样的话比较差的情况就是动辄 10000 个元素的栈,着实很费内存的。这里也将犯得这个错误记录下来。
看了官方的题解[1],整体的思路是先找到循环节,再此之后,通过计算就可以计算出来的。但是自己其实没有理解如何用代码实现这样的方式,虽然能理解这其中表达的思想。这里暂且放下这种解决方案,待日后算法精进一些还需再来看。
最终,从liweiwei1419[2]的解法里获得了启发,其实整体感觉我们的思路是类似的,都是先通过循环一遍 S1,在其中分别找到对应 S2 的值。但数据结构上的选择差了很多,我是用栈,结果就内存超限了,但他用的是指针来实现的。
分别循环 S1 字符序列,新建一个 index2 用来指示 s2 对应的位置,若在当前索引下字符能够匹配成功,则移动 s2 对应的指针,当 s2 对应的指针位置已经移动到最后时,就将指针调回 0,并为 s2 重复的次数加一。但最后还需要注意的是,题目中要求的是 S2(大写的 S) 最大的值,而我们得到的 s2 重复的次数,因此,在最终返回结果是需要 s2RepeatTimes / n2
向下取整。
复杂度分析
- 时间复杂度:
O(n*s)
,即 S1 序列的最大长度。 - 空间复杂度:
O(s1 + s2)
,分别用了s1Chars
和s2Chars
存储字符串对应的字符序列。
参考资料
- https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-by-leetcode-solution/
- https://leetcode-cn.com/problems/count-the-repetitions/solution/bao-li-jie-fa-you-hua-jie-fa-java-dai-ma-by-liweiw/
本文首发于「愚一笔记」。
原文链接:https://www.cnblogs.com/foolaris/p/12766857.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 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