题目形容
这是 LeetCode 上的 481. 神奇字符串 ，难度为 中等。
Tag : 「模仿」、「结构」、「双指针」、「打表」
神奇字符串 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 <= 10^5$
双指针 + 结构 + 打表
咱们将相干的字符串分为三类：题目形容的神奇字符串 s 称为“原串”，对 s 进行间断段划分所得的串叫“划分串”，对划分串进行计数的串叫“计数串”。
解题的外围思路：因为划分串是对原串的划分，同时计数串又与原串雷同，因而可得三类串均只有 1 和 2 两种数值。即可知划分串的每段长度只能是「长度为 1」或「长度为 2」，利用划分串的每段结构长度无限，咱们能够通过「简略分状况探讨」的形式进行结构。
具体的，咱们须要利用「原串和计数串的雷同的性质」对 s 进行结构：不难发现计数串总是不长于原串，因而咱们能够应用变量 i 来记录以后结构到原串地位，应用变量 j 来记录计数串对应到的理论地位。
不失一般性假如以后结构到 s 中的某一位为 last，而计数串对应的理论地位为 t，因为两者均只有 1 和 2 两种可能，咱们能够对其进行简略的分状况探讨（可见代码正文）。
一些细节：因为神奇字符串起始字符固定，结构逻辑固定，因而神奇字符串惟一固定。
咱们能够采取static代码块的形式进行打表预处理（Java中的static代码块只会在类加载的过程执行一次，而LC的测评机制是实例化多个Solution对象来跑多个样例，但Solution类仍只会被加载一次，即static在多个样例测评中只会被执行一次。
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]; }}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]}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]- 工夫复杂度：$O(n)$，若将
static打表逻辑放到本地进行，可能缩小结构的计算量，但仍会有创立答案数组的 $O(n)$ 开销，因而为均摊 $O(1)$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.481 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布