“谷底”类题目及一些自己的思考_c语言求数字谷底个数

题目：我们把字符串A中符合下列属性的任意连续子串 B 称为“谷底”：存在0<i<B.length-1使得B[0]>B[1]>......B[i-1]>B[i]<B[i+1]<......<B[B.length>=3]。输入一个整数字符串A，输出最长“谷底”和“谷底”长度；如果不含有“谷底”则输出不存在谷底。

我是一个大一新生，这个是我们学校工作室的考核题的内容之一。作为一个还没接触过算法，C语言也接触不久的萌新，可以说这一题对我来说挺有挑战性的。

如果看成一个函数 如图                                                                                         A：代表字符串A    B：代表字符串B

这一题的要点是需要在字符串A中寻找到字符串B并且找到最长的字符串B

我一开始的思路是先找到每一个字符串B的左边第一个字符，然后先找B的单调递减区间，再找单调递增区间，把两个区间合起来组合成一个字符串B的区间，区间的长度为字符串B的长度，在比较每一个字符串B的长度，找到最长的字符串B。后来发现如果这样去解这一个题目的话会使的代码过于冗长，且需要的变量十分的多。

后来我一个同学给了我一个新的思路那就是通过锚定字符串B中最小的字符来确定每一个字符串B的位置，然后从这个位置向两边寻找字符串B的边界。

如图                                                 

  这一种方法无疑比我之前的方法更加方便使用代码实现

上代码

#include<stdio.h>
#include<string.h>//为了使用字符数组
int main()
{
	char number[20] = {};//定义一个字符数组用来储存每一位数字
	int len=0,len_1=0,len_2=0;//用来确定数组长度，谷底区间长度
	int i, k,h;//用来作为数组下标
	printf("输入：");
	getchar();
	gets_s(number);//把数字作为字符串放入数组中
 
	len = strlen(number);//求得字符串长度数。
	for (i = 0; i <= len - 1; i++)
	{
		if (number[i]<number[i - 1] && number[i + 1]>number[i])//用于求出谷底数位置
		{
			for (k = i; number[k + 1] > number[k]; k++){}
				//用于求右峰位置
			for (h = i; number[h - 1] > number[h]; h--){}
				//用于求左峰位置
					len_1 = h + k - 3;//求出谷间长度
			if (len_2 >= len_1)//求出最长谷间长度
				len_1 = len_2;
		}
	}
	printf("输出：%d", len_1);
	if (len_1 == 0)
		printf("解释:不含谷底");
	else
	{
		printf("解释：最长谷底是");
		for (h = h; h <= k; h++)//输出谷间
		{
			printf("%c", number[h]);
			
		}
		printf("长度为：%d", len_1);
	}
	return 0;
}

这就是使用这一种方法的解题代码 

其中的关键在于

for (i = 0; i <= len - 1; i++)
    {
        if (number[i]<number[i - 1] && number[i + 1]>number[i])//用于求出谷底数位置
        {
            for (k = i; number[k + 1] > number[k]; k++){}
                //用于求右峰位置
            for (h = i; number[h - 1] > number[h]; h--){}
                //用于求左峰位置
                    len_1 = h + k - 3;//求出谷间长度
            if (len_2 >= len_1)//求出最长谷间长度
                len_1 = len_2;
        }
    }

• 使用第一个循环来检索数组中的每一个字符元素。
• 使用一个判断来确定每一个字符串B的最小字符。
• 使用两个循环来分别找出左值和右值。
• 使用一个判断来找到最大字符串B长度。

这一个方法不仅可以作用于这一个题目还可以用于其他类似的题目，其符合的条件应该要满足

1、在一长串的数中找一段数

2、每一段数存在对称性

如果这两个条件满足大概率是可以运用这一个方法解决问题的。

 

                                                                                                     第一次写博客，如果有不对的地方欢迎各位大佬的斧正。