【2022-10-31每日一题】481. 神奇字符串[Medium]
2022-10-31
2分钟阅读时长
2022-10-31每日一题：481. 神奇字符串
难度：Medium
标签：双指针 、 字符串
神奇字符串 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
方法一：双指针
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
// 速度最快
func magicalString(n int) int {
// 122 n小于4直接返回1
if n < 4 {
return 1
}
s := make([]byte, n)
copy(s, "122") // 初始化前三个位置
ans := 1
for i, j := 2, 3; j < n; i++ {
num := 3 - (s[j-1] - '0')
for size := s[i] - '0'; size > 0 && j < n; j++ {
s[j] = num + '0'
if num == 1 {
ans++
}
size--
}
}
return ans
}
// 写法二
func magicalString(n int) (ans int) {
s := make([]int, 0, n)
s = append(s, 1, 2, 2)
for i := 2; len(s) < n; i++ {
pre := s[len(s)-1]
cur := 3 - pre
for j := 0; j < s[i]; j++ {
s = append(s, cur)
}
}
for _, c := range s[:n] {
if c == 1 {
ans++
}
}
return ans
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
方法二：构造
写法1
func magicalString(n int) int {
s := make([]byte, 0, n + 1)
s = append(s, 1, 2, 2)
c := []byte{2}
for i := 2; len(s) < n; i++ {
// 1^3=2, 2^3=1，在 1 和 2 之间转换
c[0] ^= 3
s = append(s, bytes.Repeat(c, int(s[i]))...)
}
return bytes.Count(s[:n], []byte{1})
}
打表法
const mx int = 1e5
var acc [mx + 1]int
func init() {
s := make([]byte, 0, mx+1)
s = append(s, 1, 2, 2)
c := []byte{2}
for i := 2; len(s) < mx; i++ {
// 1^3=2, 2^3=1，这样能在 1 和 2 之间转换
c[0] ^= 3
s = append(s, bytes.Repeat(c, int(s[i]))...)
}
for i := 0; i < mx; i++ {
acc[i+1] = acc[i] + int(2-s[i]) // 2-1=1，2-2=0，这样就只统计了 1
}
}
func magicalString(n int) int {
return acc[n]
}