Leetcode 466 - 统计重复个数

2020-04-24 16:03:13来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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),分别用了 s1Charss2Chars 存储字符串对应的字符序列。

参考资料

  1. https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-by-leetcode-solution/
  2. 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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:剑指Offer_编程题_合并两个排序的链表

下一篇:Spring-Cloud-GateWay