米哈游（原神）首超腾讯，登顶榜首（内含算法原题）

发表于

米哈游首超腾讯

近日，第三方机构 data.ai 公布 2023 年中国游戏厂商及应用出海收入 30 强。

其中米哈游超越腾讯，首次登顶年度出海收入榜榜首。

国内共有 27 家手游发行商海外营收超 1 亿美元，米哈游和腾讯则是仅有的「海外营收超 10 亿美元」的两家。

米哈游在 2023 大获成功，主要是依靠于其 2023 年 4 月份推出的《崩坏：星穹铁道》。

该游戏位于 2023 年度手游榜单中的第三名，属于米哈游登顶收入总榜的核心因素。

…

回归主线。

来做一道「米哈游」相关的面试原题。

题目描述

平台：LeetCode

题号：481

神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：

  • 神奇字符串 s 的神奇之处在于，串联字符串中 '1' 和 '2' 的连续出现次数可以生成该字符串。

s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22 11 2 11 22 ......" 。

每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。

给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。

示例 1：

1
2
3
4
5
ini复制代码输入：n = 6

输出：3

解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。

示例 2：

1
2
3
ini复制代码输入：n = 1

输出：1

提示：

  • 1<=n<=1051 <= n <= 10^51<=n<=105

双指针 + 构造 + 打表

我们将相关的字符串分为三类：题目描述的神奇字符串 s 称为“原串”，对 s 进行连续段划分所得的串叫“划分串”，对划分串进行计数的串叫“计数串”。

解题的核心思路：由于划分串是对原串的划分，同时计数串又与原串相同，因此可得三类串均只有 1 和 2 两种数值。即可知划分串的每段长度只能是「长度为 1」或「长度为 2」，利用划分串的每段构造长度有限，我们可以通过「简单分情况讨论」的方式进行构造。

具体的，我们需要利用「原串和计数串的相同的性质」对 s 进行构造：不难发现计数串总是不长于原串，因此我们可以使用变量 i 来记录当前构造到原串位置，使用变量 j 来记录计数串对应到的实际位置。

不失一般性假设当前构造到 s 中的某一位为 last，而计数串对应的实际位置为 t，由于两者均只有 1 和 2 两种可能，我们可以对其进行简单的分情况讨论（可见代码注释）。

一些细节：由于神奇字符串起始字符固定，构造逻辑固定，因此神奇字符串唯一固定。
我们可以采取 static 代码块的方式进行打表预处理（Java 中的 static 代码块只会在类加载的过程执行一次，而 LC 的测评机制是实例化多个 Solution 对象来跑多个样例，但 Solution 类仍只会被加载一次，即 static 在多个样例测评中只会被执行一次。

Java 代码：

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
Java复制代码class Solution {
    static int N = 100010;
    static int[] f = new int[N];
    static {
        StringBuilder sb = new StringBuilder();
        sb.append("01"); // 首位多加一个 0 作为哨兵
        for (int i = 1, j = 1, cnt = 0; i < N; j++) {
            int last = sb.charAt(sb.length() - 1) - '0', t = sb.charAt(j) - '0';
            if (last == 1) {
                if (t == 1) {
                    // 当原串当前字符是 1，而计数串当前字符为 1 
                    // 往后构造形成的原串只能是 12，原串指针后移一位
                    sb.append("2");
                    f[i] = ++cnt; i++;
                } else {
                    // 当原串当前字符是 1，而计数串当前字符为 2
                    // 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
                    sb.append("12");
                    f[i] = ++cnt; f[i + 1] = ++cnt; i += 2;
                }
            } else {
                if (t == 1) {
                    // 当原串当前字符是 2，而计数串当前字符为 1 
                    // 往后构造形成的原串只能是 21，原串指针后移一位
                    sb.append("1");
                    f[i] = cnt; i++;
                } else {
                    // 当原串当前字符是 2，而计数串当前字符为 2
                    // 往后构造形成的原串只能是 221，原串指针后移两位
                    sb.append("21");
                    f[i] = f[i + 1] = cnt; i += 2;
                }
            }
        }
    }
    public int magicalString(int n) {
        return f[n];
    }
}

C++ 代码：

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
C++复制代码class Solution {
public:
    static const int N = 100010;
    static vector<int> f;
    Solution() {
        if(!f.empty()) return;
        f.resize(N);
        string sb = "01"; // 首位多加一个 0 作为哨兵
        for (int i = 1, j = 1, cnt = 0; i < N; j++) {
            int last = sb[sb.size() - 1] - '0', t = sb[j] - '0';
            if (last == 1) {
                if (t == 1) {
                    sb += '2';
                    f[i++] = ++cnt;
                } else {
                    sb += "12";
                    f[i++] = ++cnt; f[i++] = ++cnt;
                }
            } else {
                if (t == 1) {
                    sb += '1';
                    f[i++] = cnt;
                } else {
                    sb += "21";
                    f[i++] = f[i++] = cnt;
                }
            }
        }
    }
    int magicalString(int n) {
        return f[n];
    }
};
vector<int> Solution::f = {};

Python 代码：

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
Python复制代码class Solution:
    def magicalString(self, n: int) -> int:
        ss = '01' # 首位多加一个 0 作为哨兵
        i, j, cnt = 1, 1, 0
        f = [0] * (n + 10)
        while i <= n:
            last, t = ss[i], ss[j]
            if last == '1':
                if t == '1':
                    # 当原串当前字符是 1，而计数串当前字符为 1 
                    # 往后构造形成的原串只能是 12，原串指针后移一位
                    ss += '2'
                    f[i], cnt, i = cnt + 1, cnt + 1, i + 1
                else:
                    # 当原串当前字符是 1，而计数串当前字符为 2
                    # 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
                    ss += '12'
                    f[i], f[i + 1], cnt, i = cnt + 1, cnt + 2, cnt + 2, i + 2
            else:
                if t == '1':
                    # 当原串当前字符是 2，而计数串当前字符为 1 
                    # 往后构造形成的原串只能是 21，原串指针后移一位
                    ss += '1'
                    f[i], i = cnt, i + 1
                else:
                    # 当原串当前字符是 2，而计数串当前字符为 2
                    # 往后构造形成的原串只能是 221，原串指针后移两位
                    ss += '21'
                    f[i], f[i + 1], i = cnt, cnt, i + 2
            j += 1
        return f[n]

TypeScript 代码：

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
TypeScript复制代码function magicalString(n: number): number {
    let str = '01' // 首位多加一个 0 作为哨兵
    const f = new Array<number>(n + 10).fill(0)
    for (let i = 1, j = 1, cnt = 0; i <= n; j++) {
        const last = str[str.length - 1], t = str[j]
        if (last == '1') {
            if (t == '1') {
                // 当原串当前字符是 1，而计数串当前字符为 1 
                // 往后构造形成的原串只能是 12，原串指针后移一位
                str += '2'
                f[i] = ++cnt; i++
            } else {
                // 当原串当前字符是 1，而计数串当前字符为 2
                // 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
                str += '12'
                f[i] = ++cnt; f[i + 1] = ++cnt; i += 2
            }
        } else {
            if (t == '1') {
                // 当原串当前字符是 2，而计数串当前字符为 1 
                // 往后构造形成的原串只能是 21，原串指针后移一位
                str += '1'
                f[i] = cnt; i++
            } else {
                // 当原串当前字符是 2，而计数串当前字符为 2
                // 往后构造形成的原串只能是 221，原串指针后移两位
                str += '21'
                f[i] = f[i + 1] = cnt; i += 2
            }
        }
    }
    return f[n]
}
  • 时间复杂度：O(n)O(n)O(n)，若将 static 打表逻辑放到本地进行，能够减少构造的计算量，但仍会有创建答案数组的 O(n)O(n)O(n) 开销，因此为均摊 O(1)O(1)O(1)
  • 空间复杂度：O(n)O(n)O(n)

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%