LeetCode Magical String

LeetCode 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 Sitself.

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: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

这道题给了一个magic字符串,具体怎么magic题目说得很清楚了。这个字符串只包含字符1和2,依次计算字符串中连续的1或2出现的次数,把这些数字串起来,构成的一个新的字符串和原字符串是完全一样的!然后问字符串中前n个字符出现1的次数。

这是一个模拟题,我们根据magic的规则模拟生成这个字符串,然后统计一下前n个字符中1出现的次数。

模拟的方法就是把字符串中的数当做原字符串中1或2出现的次数,然后不断在原字符串中追加新的字符。比如开始是122:1表示1出现1次;第一个2表示出现两次,因为前面有1出现1次的约束,所以出现两次的只可能是2;第二个2也表示出现两次,因为前面已经出现了两个2了,所以这里不能再接两个2了(要不然就出现4个2了),只能表示出现了两次1,所以我们可以在原字符串中追加两个1,变为12211。如此不断的模拟下去,直到字符串长度满足要求。

完整代码如下:

class Solution {
public:
	int magicalString(int n) {
		string magic = "122";
		int pos = 2;
		while (magic.size() < n) {
			switch (magic[magic.size()-1])
			{
			case '1':
				magic += string(magic[pos] - '0', '2');
				break;
			case '2':
				magic += string(magic[pos] - '0', '1');
				break;
			}
			++pos;
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans += magic[i] == '1' ? 1 : 0;
		}
		return ans;
	}
};

本代码提交AC,用时9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *