​LeetCode刷题实战466:统计重复个数

程序IT圈

共 3406字,需浏览 7分钟

 ·

2021-12-14 01:09

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 统计重复个数,我们先来看题面:
https://leetcode-cn.com/problems/count-the-repetitions/


We define str = [s, n] as the string str which consists of the string s concatenated n times.

For example, str == ["abc", 3] =="abcabcabc".
We define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1.

For example, s1 = "abc" can be obtained from s2 = "abdbec" based on our definition by removing the bolded underlined characters.
You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].

Return the maximum integer m such that str = [str2, m] can be obtained from str1.

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

例如,str == ["abc", 3] =="abcabcabc" 。
如果可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。

例如,根据定义,s1 = "abc" 可以从 s2 = "abdbec" 获得,仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串,其中 str1 = [s1, n1]、str2 = [s2, n2] 。

请你找出一个最大整数 m ,以满足 str = [str2, m] 可以从 str1 获得。

示例                             


示例 1
输入:s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出:2

示例 2
输入:s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出:1


解题

http://www.manongjc.com/detail/16-brgjkiiatjfsbja.html

思路1:可能超时。分析题目可知,字符串S1是由n1个s1连接而成,字符串S2是由n2个s2连接而成,求满足使[S2,M]从S1获得的最大整数M,有点绕口,通俗说,即求S1中包含S2的个数M。最容易想到的方法是初始化M=0,然后遍历S1寻找S2,找到S2后M++,依次继续,直到S1遍历结束。当然,需要注意遍历的条件,即保证S2的长度应该小于等于S1的长度。不过可惜的是,这种思路导致超时问题。

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
       string S1 = "", S2 = "";
        int M = 0;
        for(int i = 0; i < n1; i++) S1 += s1;
        for(int j = 0; j < n2; j++) S2 += s2;
        int k = 0;
        for(int i = 0; i < S1.size(); i++)
        {
            if(S1[i] == S2[k]) k++;
            if(k == S2.size())
            {
                M++;
                k = 0;
            }
        }
        return M;
    }
};


思路2:如果s2在S1中出现了N次,那么S2肯定在S1中出现了N/n2次,这里的大写表示字符串加上重复次数组成的大字符串,即字符串拼接结果。所以,我们只要算出s2出现的次数count_s2,然后除以n2,就可以得出S2在S1中出现的次数了,即可求得M。

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
       int s2_next_index = 0, count_s1 = 0, count_s2 = 0;
       unordered_map<int, pair<int, int>> mp;
       while(count_s1 < n1)
       {
           for(int i = 0; i < s1.size(); i++)
           {
               if(s1[i] == s2[s2_next_index]) s2_next_index++;
               if(s2_next_index == s2.size())
               {
                   s2_next_index = 0; //下一轮循环
                   count_s2++;
               }
           }
           count_s1++;
           if(mp.count(s2_next_index) == 0) mp[s2_next_index] = make_pair(count_s1, count_s2);
           else 
           {
               int last_count_s1 = mp[s2_next_index].first;
               int last_count_s2 = mp[s2_next_index].second;
               int interval_s1 = count_s1 - last_count_s1;
               int interval_s2 = count_s2 - last_count_s2;
               int num = (n1 - count_s1) / interval_s1;
               count_s2 += num * interval_s2;
               count_s1 += num * interval_s1;
           }
       }
       return count_s2 / n2;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-460题汇总,希望对你有点帮助!

LeetCode刷题实战461:汉明距离

LeetCode刷题实战462:最少移动次数使数组元素相等 II

LeetCode刷题实战463:岛屿的周长

LeetCode刷题实战464:我能赢吗



浏览 35
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报