481. 神奇字符串
https://leetcode.cn/problems/magical-string/
难度中等59
神奇字符串 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
通过次数8,297提交次数14,522
class Solution {
public int magicalString(int n) {
if(n<3) return 1;
int[] dp = new int[n];
int ans =0;
int index =2;
dp[0] = 1;
dp[1] = -1;
dp[2] = -1;
for(int i=3;i<n;i++)
{
if(dp[index]==-1)
{
dp[i]=dp[i-1]*(-1);
i = i+1;
if(i<n) dp[i]=dp[i-2]*(-1);
}
else
{
dp[i]=dp[i-1]*(-1);
}
index++;
}
for(int i=0;i<n;i++)
{
if(dp[i]==1) ans++;
}
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/68975.html
