0 和 1 C语言

描述

        研究01串是一件很好玩的事情，现在有一个长度为n的01串，当一个连续的子串中0和1的个数相同，这个子串就是好的子串，现在请你写代码算出这个长度为n的01串中有多少个好的子串。

输入

输入T (1<=T<=10)组数据，每组第一行输入一个整数n (1<=n<=1000)，代表01串的长度，接下来输入一行长度为n的01串。

输出

输出T行，每行一个整数作为答案。

样例输入

2

2

01

4

0101

样例输出

1

4

思路及分析：

        首先要搞懂题目的说明，什么是01串中的好子串。根据题目定义，比如010101 它的划分应当是这样的：

        根据这样的划分，最直观的发现是需要判断的长度，就也就是它的结束位置是不一定的，所以需要通过变量来控制每一个需要判断的子串的长度。同时，还需要判断的开始位置。我们用指针来描述判断的开始位置和结束位置。定义两个指针变量*start和*end。如图：

我们需要从下面几个方面来考虑。        

 1，如何获取字符0和1？

        从上面的动图来看，每动一次*start，就动一次*end，直到*end遇到字符‘’就结束。

2，长度如何截断？

        上面的情况是针对两个长度的子串的情况。根据好子串的定义，我们需要每一次截断的的长度应该为偶数倍，这样是比较合理的，比如0101，第一次截断两个长度，根据上面的动图，就是01，10，01。第二次截断当我们对于4个长度的子串的情况的时候，就是0101。如果每一次循环后截断长度加1，这样如0101，第一次截断长度为2，第二次截断长度为3，就是010，肯定不符合好串的定义。这样截断之后，在返回1中，就可以了。

3，需要循环几次？

        如果我们去找这个规律，比如01010101：

         长度为8的时候，长度为2的需要小循环7次。长度为4的需要小循环5次。长度为6的需要小循环3次。长度为8的需要小循环1次。整个过程，需要大的循环四次，让截断长度从2个变成8个。这样就可以完成全部的情况的判断。当然，你可以多试几个01串。

        通过上面的分析得知：整个过程需要4个循环语句（1个为题目要求的多组输入）。由内到外分别需要循环如何动，如何截断长度，有几个这样的截断长度的循环，要循环几次不同的截断长度，有几组输入。反过来，以01010101举例，01010101.输入01010101一组输入，需要分成上面图片中的4个不同的长度，其中，长度为2的需要7次循环才能找到全部的2个长度的。在让它判断里面的值，判断完0之后要动一次来判断1。

        这样的分析是最直观的。实现代码分为指针形式（由本人实现），和数组形式（由本人的一位好友实现@Idyllic930,有改动。），要注意的是实现的方式不是唯一的，可以用for也可以用while。

//指针形式
#include<stdio.h>

int main(void)
{
	int t = 0;
	scanf("%d", &t);
	int n = 0;
	char arr[1000] = { 0 };

	for (int m = 0; m < t; m++)//题目要求的循环输入
	{
		int i = 0;//总的循环的次数
		int j = 1;//start要回退的值
		int k = 1;//end要截断的长度
		scanf("%d", &n);
		scanf("%s", arr);

		int count_zero = 0;//计数0的个数
		int count_one = 0;//计数1的个数
		int count = 0;//计数01中好子串的个数

		char* start = arr;//start的位置
		char* end = arr + k;//end的位置

		while (i < n / 2)//循环次数
		{
			while (*end != '')
			{
				while(start <= end && *end != '')//判断01串里面的值；
				{
					if (*start == '1')//这个值为1，计数1的变量的值加1；
					{
						count_one++;
					}
					if (*start == '0')//这个值为0，计数0的变量的值加1；
					{
						count_zero++;
					}
					start++;//让start指向下一位
				}
				if (count_zero == count_one)//计数1和计数0是否相等，若相等，计数01中好串的变量加1；
				{
					count++;
				}
				end++;//end指向下一位；
				start -= j;//star退回到他-j位；
				//初始化
				count_zero = 0;
				count_one = 0;
			}
			j += 2;
			i += 1;
			k += 2;
			end = arr + k;
			start = arr;
		}
		printf("%dn", count);
	}
	return 0;
}

结果如下：

#include<stdio.h>
int main()
{
	int t, i;
	scanf("%d", &t);
	for (i = 0; i < t; i++)
	{
		int j = 0;
		int k = 0;
		int count_one = 0;
		int count_zero = 0;
		int count = 0;

		int len = 0;
		int index = 0;
		char arr[100] = { 0 };

		scanf("%d", &len);
		scanf("%s", arr);

		for (j = 1; j < len;)
		{
			for (k = 0; k < len - 1; k++)
			{
				for (index = k, count_zero = 0, count_one = 0; index < (k + 2 * j); index++)
				{
					if (arr[index] == '1')
					{
						count_one++;
					}	
					else if (arr[index] == '0')
					{
						count_zero++;
					}
				}
				if (index > len)
				{
					break;
				}	
				if (count_one == count_zero)
				{
					count++;
				}
					
			}
			j++;
		}
		printf("%dn", count);
	}
	return 0;
}

结果如下：