算法

每日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

总体思路

记录下来每个s1对应的位置，匹配的结果。每一次如果要求的匹配已经在数据中，就看可以匹配多少组。

比如，【baab, 40】里面要匹配【baba, 2】，那我就先找到应该匹配哪几位：

  • 第一次匹配：【baabbaabbaabbaabbaab】
  • 找到对应的：【ba b a】，是从s1的下标为0的位置开始匹配的
  • 第二次匹配：【baabbaabbaabbaabbaab】
  • 找到对应的：【 b a b a】，是从s1的下标为2的位置开始匹配的
  • 再往后匹配：【baabbaabbaabbaabbaab】
  • 这一次找对应的，还是从s1的下标为2的位置开始匹配的。

因此，我们就可以记录下来，每一次从s1的某一个位置进行匹配，会匹配到哪个地方。

匹配位置

匹配位置是说，使用一个数组/map，i对应的值为记录从s1的第i位开始，往后走到哪里可以匹配一个完整的s2。

比如：s1=”baab”, s2=”baba”，我用来记忆的map叫做memo，这样的话memo[0] = 6，表示从s1的下标为0的地方，往右走到下标为6的地方可以匹配完一个s2

  • 注：下标为6代表的是，s1重复之后得到的”baabbaabbaab……”这个数组的下标，也就是说其中的【baabba】（下标为0 ～ 5）这些部分可以匹配一个完整的s2。

如果是求memo[2]的话，那结果就等于10，代表下标为2～9的部分（ba【abbaabba】ab）可以匹配一个完整的s2。

因此，我这里设计了一个函数可以实现上述的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int checkWhere(int n, string &s1, int len1, string &s2, int len2) {
    for (int i = 0; i < len2; i++) {
        int n_target = n + len1;
        bool found = false;
        for (; n < n_target; n++) {
            if (s1[n % len1] == s2[i]) {
                n++;
                found = true;
                break;
            }
        }
        if (!found) {
            return -1;
        }
    }
    return n;
}

找到循环体

比如刚才的例子，【baab, 40】里面要匹配【baba, 2】

到第二次寻找的时候，就是从下标为2开始，到下标为2结束。

  • 【baabbaabbaab】
  • 【 b a b a】

再往后一次也是一样的，这样就构成了循环结构。

我在这里使用了一个循环结构的检测，记录的时候不仅记录应该到哪个地方，而且记录了到这个地方的时候我匹配完了几个s2。

也就是说，memo[0] = [6, 1]，memo[2] = [10, 2]。

问题来了：

  • 那我一次匹配的之后，下一次应该匹配谁呢？
    • 结果除以s1的长度取余。比如，memo[0] = [6, 1]，那我下一次就应该去找memo[6 % s1.size()]也就是memo[2]
  • 什么时候发现有循环了？
    • 结果除以s1的长度，发现这个值对应位置已经有结果了。
    • 比如，memo[2] = [10, 2]，s1的长度为4，10%4==2，memo[2]刚才已经算出来了，所以就开始循环了！
  • 我们的循环需要计算什么？
    • 我们需要知道这个循环里面，消耗了多少s1，找到了多少s2
    • 实际上的做法，就是对memo进行处理，不断计算直到发现memo开始循环，记录下这时候s1消耗了多少个与s2出现了多少个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    int checkWhere(int n, string &s1, int len1, string &s2, int len2, map<int, pair<int, int>>& memo) {
        for (int i = 0; i < len2; i++) {
            int n_target = n + len1;
            bool found = false;
            for (; n < n_target; n++) {
                if (s1[n % len1] == s2[i]) {
                    n++;
                    found = true;
                    break;
                }
            }
            if (!found) {
                return -1;
            }
        }
        return n;
    }

    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        map<int, pair<int, int>> memo;
        int now_n = 0;  // from the nth letter of s1, to which will have one s2
        int len1 = s1.size(), len2 = s2.size();
        int max_n = len1 * n1;
        int now_num_s2 = 0;
        int n, temp;
        while (now_n < max_n) {
            n = now_n % len1;
            if (memo.find(n) != memo.end()) {
                // now already found
                // 之前用了now_n这么多个，也就是用了now_n//len1这么多个s1，并且找到了now_num_s2这么多个s2
                // 现在需要做什么？现在需要跳回到data[n][0]这个位置，并且可以得到now_num_s2 - memo[n][1]这么多个s2
                // 需要用到多少s1呢？
                int need_n = n / len1 * len1 + memo[n].first;
                while (need_n % len1 != n) {
                    need_n = need_n / len1 * len1 + memo[need_n % len1].first;
                }
                // 现在到了need_n这么多位的s1，也就是用了need_n/len1这么多个s1，就拿到了now_num_s2 - memo[n][1]这么多个s2
                // 还剩下max_n - now_n这么多个可以挥霍
                int add_whole = (max_n - now_n) / (need_n / len1 * len1);
                now_num_s2 += add_whole * (now_num_s2 - memo[n].second + 1);
                now_n += add_whole * (need_n / len1 * len1);
                while (now_n < max_n) {
                    temp = memo[now_n % len1].first;
                    now_n = now_n / len1 * len1 + temp;
                    if (now_n > max_n) {
                        break;
                    }
                    now_num_s2 += 1;
                }
                return now_num_s2 / n2;
            }
            temp = checkWhere(n, s1, len1, s2, len2, memo);
            if (temp == -1) {
                return 0;
            }
            now_n = now_n / len1 * len1 + temp;
            if (now_n > max_n) {
                break;
            }
            now_num_s2 += 1;
            memo[n] = pair<int, int>(temp, now_num_s2);
        }
        return now_num_s2 / n2;
    }
};