481. Magical String

网友投稿 1113 2022-09-04

481. Magical String

481. Magical String

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 string S itself.

The first few elements of string S is the following: 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 above is the S itself.

Given an integer N as input, return the number of ‘1’s in the first N number in the magical string S.

Note: N will not exceed 100,000.

Example 1:

Input: 6Output: 3Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

思路: 给定1和2组成的字符串,1和2描述了本身1或者2连续出现的次数。给定一个数字N,返回这种字符串前N个数中1的个数。

分析: 1 2 2 1 1 2 1 2 2 1 2 2…… 1 22 11 2 1 22 1 22 11 2 11 22 …… 比如122就确定了1+2+2=5个数除去自身就是后面两个数,可以知道的是,后面两个数是2个1或者两个2.比如11,那么就再影响了了后面两个数不连续。比如22就影响了后面的四个数,可能出现 : 1122 1111 2222 2211 所以我们知道两个事:第一个:表示出现个数的字符串比较短,能决定后面的。第二个:这种决定是不一定的(有多种可能)。 那么有多种可能怎么办呢?我们继续回到题目给出的字符串:发现1,2是间隔的。所以,这个字符串在开头确定的前提下就已经被确定了。 所以我们动态的构造它直到N,在过程中计数。 再来分析规律:比如122后面为什么是11: 1、第三个数2决定了是两个数。 2、第三个数是2决定了该是1了。 归纳一般规律:我们需要知道探究对象前面的是1还是2,还需要知道对应应该添加几个。

class Solution public int magicalString(int n) { StringBuilder sb = new StringBuilder("122"); int count = 1; int slow = 2; //应该指示接下来 int fast = 2; //应该指示当前最末 while(sb.length() < n){ if(sb.charAt(slow) == '1'){ //表示接下来的是1个 if(sb.charAt(fast) == '1') //表示当前是1 sb.append(2); //那么就应该添加2 else if(sb.charAt(fast) == '2'){ sb.append(1); count++; } fast++; }else if(sb.charAt(slow) == '2'){ //表示接下来的是2个 if(sb.charAt(fast) == '1') sb.append(22); else if(sb.charAt(fast) == '2'){ sb.append(11); count += 2; } fast += 2; } slow++; } if(sb.length() > n && sb.charAt(n) == '1') //最后一次如果是append(11),那么有可能多出一个1 count--; return count; }}

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:如何排查 Linux 机器是否已经被入侵?(如何排查癌症)
下一篇:477. Total Hamming Distance
相关文章

 发表评论

暂时没有评论,来抢沙发吧~