LeetCode481. 神奇字符串

浅浅的花香味﹌ 2021-09-27 03:26 265阅读 0赞

神奇的字符串 S 只包含 ‘1’ 和 ‘2’，并遵守以下规则：

字符串 S 是神奇的，因为串联字符 ‘1’ 和 ‘2’ 的连续出现次数会生成字符串 S 本身。

字符串 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’ 的数目。

注意：N 不会超过 100,000。

> 示例：  
> 输入：6  
> 输出：3

解题思路:  
分为两个字符串：1表示原始字符串，2表示分组后的字符串  
结合第一个字符串向第二个字符串中添加元素  
结合第二个字符串向第一个字符串中添加元素。

class Solution {
        public int magicalString(int n) {
            if(n <= 0)
                return 0;
            if(n <= 3)
                return 1;
            StringBuilder base = new StringBuilder();
            StringBuilder sub = new StringBuilder();
            base.append("122");
            sub.append("12");
            int index = 0;
            int temp = 0;
            int counts = 1;
            while (base.length() < n){
                index = sub.length();
                temp =  base.charAt(index)-'0';
                sub.append(temp);
                if(temp==2){
                    temp = base.charAt(base.length()-1)-'0';
                    if(temp == 2){
                        base.append("11");
                        if(base.length() <= n)
                            counts += 2;
                        else
                            counts += 1;
                    }else {
                        base.append("22");
                    }
                }else {
       //temp == 1
                    temp = base.charAt(base.length()-1)-'0';
                    if(temp == 2){
                        base.append("1");
                        counts += 1;
                    }else {
                        base.append("2");
                    }
                }
            }
            return counts;
        }
    }

附加：  
提交后，看到其他人的提交，扩展了思维，首先，上面的字符串可以采用数组实现。  
其次，上述代码中的1->2,2-1，可以采用与2异或实现。