Medium

题目描述

神奇字符串 s 仅由 ‘1’ 和 ‘2’ 组成，并遵循以下规则：

将字符串 s 中连续相同字符的长度序列串联起来，会生成字符串 s 本身。

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 <= 10^5

解题思路

这道题的核心是理解神奇字符串的生成规律：字符串本身描述了自己的结构。

解题思路：

神奇字符串有一个重要特性：字符串的每一位都表示当前组的长度。我们可以用双指针来生成这个字符串：

  • pos：指向当前要填充的位置
  • index：指向描述当前组长度的位置

生成过程：

  1. 初始化字符串为 “1”，pos = 1，index = 0
  2. 当前字符由 (index % 2) + 1 决定（奇数位置填2，偶数位置填1）
  3. 当前组的长度由 s[index] 决定
  4. 填充完一组后，index 指向下一个位置

优化： 我们不需要真正构建整个字符串，只需要在生成过程中统计1的个数即可。

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)，是最直观高效的解法。

代码实现

class Solution {
public:
    int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        
        vector<int> s(n);
        s[0] = 1;
        s[1] = 2;
        s[2] = 2;
        
        int pos = 3;
        int index = 2;
        
        while (pos < n) {
            int cur = (index % 2) + 1;
            int len = s[index];
            
            for (int i = 0; i < len && pos < n; i++) {
                s[pos++] = cur;
            }
            index++;
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 1) count++;
        }
        
        return count;
    }
};

class Solution:
    def magicalString(self, n: int) -> int:
        if n <= 0:
            return 0
        if n <= 3:
            return 1
        
        s = [1, 2, 2]
        pos = 3
        index = 2
        
        while pos < n:
            cur = (index % 2) + 1
            length = s[index]
            
            for _ in range(length):
                if pos >= n:
                    break
                s.append(cur)
                pos += 1
            
            index += 1
        
        return s[:n].count(1)

public class Solution {
    public int MagicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        
        List<int> s = new List<int> {1, 2, 2};
        int pos = 3;
        int index = 2;
        
        while (pos < n) {
            int cur = (index % 2) + 1;
            int len = s[index];
            
            for (int i = 0; i < len && pos < n; i++) {
                s.Add(cur);
                pos++;
            }
            index++;
        }
        
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 1) count++;
        }
        
        return count;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var magicalString = function(n) {
    if (n <= 0) return 0;
    if (n <= 3) return 1;
    
    let s = [1, 2, 2];
    let pos = 3;
    let index = 2;
    
    while (pos < n) {
        let cur = (index % 2) + 1;
        let len = s[index];
        
        for (let i = 0; i < len && pos < n; i++) {
            s.push(cur);
            pos++;
        }
        index++;
    }
    
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要生成前n个字符
空间复杂度O(n)存储生成的字符串