英文原文
A magical string s consists of only '1' and '2' and obeys the following rules:
- The string s is magical because concatenating the number of contiguous occurrences of characters
'1'and'2'generates the stringsitself.
The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......" and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.
Given an integer n, return the number of 1's in the first n number in the magical string s.
Example 1:
Input: n = 6 Output: 3 Explanation: The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 105
中文题目
神奇字符串 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
通过代码
高赞题解
题意
字符串 S 的前几个元素如下：S = “1221121221221121122 ……”，我们来研究一下字符串 S 是如何生成的。
- 假设字符串 S 第一个字符为 1 时，那么第二个字符是什么呢？
- 我们不妨假设还存在一个字符串 A 它决定字符串 S 中连续字符的个数且字符串 A 等于字符串 S。
- 所以当字符串 S 的第一个字符为 1 时，字符串 A 的第一个字符也为 1。
- 因为字符串 A 决定字符串 S 中连续字符的个数，所以字符串 S 的第一个字符最多能有 1 个。
- 因为字符串 S 只包含 ‘1’ 和 ‘2’且第一个字符最多能有 1 个，所以第二个字符一定为 2。
- S = 12 所以 A = 12，因为 A 的第二个字符为 2，所以 S 中第二个字符应该出现两次，S = 122。
- S = 122 所以 A = 122，因为 A 的第三个字符为 2，所以 S 的下一个字符也应该出现两次，S = 12211。
- S = 12211 所以 A = 12211，因为 A 的第四个字符为 1，所以 S 的下一个字符出现一次，S = 122112。
- …
之后只需生成一个长度为 n 的字符串 S，统计其中 1 的个数即可。题目中的示例的解释写错了，前 6 个元素应该是 122112，它只给了 5 个元素。
方法一：使用 StringBuilder
- 执行用时：20 ms, 在所有 Java 提交中击败了38.81%的用户
- 内存消耗：37.4 MB, 在所有 Java 提交中击败了70.90%的用户
class Solution { public int magicalString(int n) { // index 表示字符串 A 的索引，根据该索引的字符生成指定个数的字符， int index = 1; StringBuilder s = new StringBuilder(); // 第一个字符为 1 s.append(1); while (s.length() < n) { // 因为需要根据字符串 A，来确定在字符串 S 生成字符的个数 // 所以当字符串 A 越界时，则根据前一个字符进行生成 if (index == s.length()) { // 如果前一个字符为 1，则生成 22。 s.append(s.charAt(s.length() - 1) == '1' ? 22 : 1); index++; } else { // 如果字符串 A 没有越界，则字符串 A 决定生成字符的个数。 // 而字符串 S 的最后一个字符决定生成的字符是 1 还是 2 if (s.charAt(s.length() - 1) == '1') { s.append(s.charAt(index++) == '1' ? 2 : 22); } else { s.append(s.charAt(index++) == '1' ? 1 : 11); } } } // count 统计 1 的个数 int count = 0; // 遍历字符串统计 1 的个数 for (int i = 0; i < n; i++) { if (s.charAt(i) == '1') { count++; } } return count; } }
方法二：使用 int[]
通过观察我们不难发现，只有生成第二个字符时，会出现 index == s.length()，即字符串 A 越界。后面生成字符串时只会越来越多，不可能再出现字符串 A 越界的情况，所以我们可以将前三个字符提前设置好。
- 执行用时：3 ms, 在所有 Java 提交中击败了100.00%的用户
- 内存消耗：37.6 MB, 在所有 Java 提交中击败了59.70%的用户
class Solution { public int magicalString(int n) { if (n == 0) { return 0; } if (n <= 3) { return 1; } int[] array = new int[n]; // 设置初值 array[0] = 1;array[1] = 2;array[2] = 2; // 统计 1 的个数，前三个字符中有 1 个 1 int count = 1; // index 表示字符串 A 的索引，length 表示字符串有效字符的个数， value 表示下次生成的字符 int index = 2, length = 3, value = 1; while (length < n) { // 根据 array[index] 的值决定生成几个 value for (int i = 0; i < array[index] && length < n; i++) { array[length++] = value; // 统计 1 的个数 if (value == 1) { count++; } } // 更换生成的字符，3-1=2，3-2=1，实现 1 和 2 的交替 value = 3 - value; index++; } return count; } }
文中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！
本人博客链接 zyxwmj.top
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 6105 | 11172 | 54.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
