LeetCode 0481. 神奇字符串

【LetMeFly】481.神奇字符串

力扣题目链接：https://leetcode.cn/problems/magical-string/

神奇字符串 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：

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

示例 2：

输入：n = 1
输出：1

 

提示：

• 1 <= n <= 105

方法一：双指针

我们把神奇字符串“1221121221221121122”称为原始串，把分组后的字符串“1 2 2 1 1”称为新串。（虽然二者相同，但我们仍然加以区分）

我们用一个“指针”locFront指向“新串”该生成的位置，用一个“指针”locEnd指向“原始串”处理到的位置

当原始串处理到$n-1$时，我们就处理（且知道）了原始串前$n$个字符，就知道了前$n$个字符中有多少个“1”

初始时我们知道原始串的前三个字符“122”，其对应新串为“1 2”（1个1，2个2）

原始串该处理第$4$个字符（下标为$3$），新串该处理第$3$个字符（下标为$2$）

因此，初始值$locFront=2,locEnd=3$

之后由“新串”该生成的位置，我们就能求得“原始串”应由一个还是两个连续的字符组成

例如新串的第三个字符应该是“2”，从而我们得知原始串应该再接“2”个1

如此进行下去，我们就得知了原始串的前$n$个字符。

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

AC代码

C++

char str[100010] = "122";
class Solution {
public:
    int magicalString(int n) {
        int locFront = 2, locEnd = 3;
        char nowChar = '1';
		// 摸清原始串的前n个字符
        while (locEnd < n) {
            for (int i = str[locFront] - '0'; i > 0; i--) {
                str[locEnd++] = nowChar;
            }
            locFront++;
            nowChar = nowChar == '1' ? '2' : '1';
        }
        // 统计开始
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += str[i] == '1';
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

What’s more

这道题每次测试 原始串都是相同的

因此我们也可以只进行一次求串操作（第一次调用这个类时，求出原始串的前$10^5$个字符），之后直接统计即可。

// SecondTry  // 坏人做法：只求一次，后续只统计
// 坏坏方法，但是对执行结果的影响不大（数据不多，如果有几千组数据，那么这种坏方法的执行总时间将会大大减少）
char str[100010] = "122";
class Solution {
public:
    int magicalString(int n) {
        static bool first = true;
        if (first) {
            first = false;
            int locFront = 2, locEnd = 3;
            char nowChar = '1';
            while (locEnd < 100000) {
                for (int i = str[locFront] - '0'; i > 0; i--) {
                    str[locEnd++] = nowChar;
                }
                locFront++;
                nowChar = nowChar == '1' ? '2' : '1';
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += str[i] == '1';
        }
        return ans;
    }
};
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

对于这种初始化方法，@Lin 提供了一种方法：

char str[100010] = "122";
int init = []() {
    int locFront = 2, locEnd = 3;
    char nowChar = '1';
    while (locEnd < 100000) {
        for (int i = str[locFront] - '0'; i > 0; i--) {
            str[locEnd++] = nowChar;
        }
        locFront++;
        nowChar = nowChar == '1' ? '2' : '1';
    }
    return 0;
}();


class Solution {
public:
    int magicalString(int n) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += str[i] == '1';
        }
        return ans;
    }
};
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

其中

[]() {
    // ....
}
1
2
3

为C++ lambda函数

而其后紧接着跟随一个()表示对这个函数的调用。

因其处在全局变量中，故这个函数只执行一次。

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127565144