我想知道是否有一种编程方法来确定数组是否具有完美的山脉图案,没有山谷。 (图中的示例)
来源: https://leetcode.com/problems/valid-mountain-array/
编辑:
我在 C: 中的尝试
#include<stdio.h>
int AscOrDes(int a[], int first, int last)
{
int i;
for(i=first; i<last; i++)
{
if(a[i]>a[i+1])
return(1);
else if(a[i]<a[i+1])
return(2);
}
return 0;
}
int main() {
int a[1000],n,i,big=0,r1,r2;
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
for(i=0; i<n; i++)
{
if(a[i]>=a[big])
big=i;
}
r1=AscOrDes(a, 0, big);
r2=AscOrDes(a, big, n);
if(r1==2 && r2==1 && big!=0 && big!=n-1)
printf("True");
else
printf("False");
return 0;
}
上面的代码没有对于以下输入不起作用:
8
1 3 2 5 4 3 2 0
它给出输出:
True
即使它不是完美的山数组。
我在程序中所做的是检查哪个元素是最大的(|| |),并检查最大元素左侧的元素是否按升序排列,右侧的元素是否按降序排列(山应该如何)。
big
), and checked if the elements on the left side of the largest element are in ascending order and those on the right side are in descending order (how the mountain should be).
你的 C 代码的问题在于你的
AscOrDes
函数可以确定一个序列是严格递增还是递减,但在遇到不同趋势时会过早停止。例如,在序列
1 3 2 5
中,函数会在看到
3 > 2
时返回
1
(递减),即使后面的序列是递增的。
以下是解决此问题的 C 代码的更正版本:
#include <stdio.h>
#include <stdbool.h>
bool isMountainArray(int arr[], int n) {
if (n < 3) {
return false;
}
int i = 0;
// 向上攀登
while (i < n - 1 && arr[i] < arr[i + 1]) {
i++;
}
// 峰值不能是第一个或最后一个元素
if (i == 0 || i == n - 1) {
return false;
}
// 向下攀登
while (i < n - 1 && arr[i] > arr[i + 1]) {
i++;
}
// 检查是否到达了数组的末尾
return i == n - 1;
}
int main() {
int a[1000], n;
printf("输入数组的大小:");
scanf("%d", &n);
printf("输入数组元素:");
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
if (isMountainArray(a, n)) {
printf("True\n");
} else {
printf("False\n");
}
return 0;
}
以下是代码的工作原理:
-
处理基本情况:
如果数组的元素少于 3 个,它就不能形成山脉,因此返回
false
。 - 向上攀登: 代码从数组的开头开始,只要当前元素小于下一个元素就继续前进。这表示数组的递增部分。
-
检查峰值:
在递增部分结束后,代码检查峰值是否不是数组的第一个或最后一个元素。如果是,则该数组不是山脉数组,因此返回
false
。 - 向下攀登: 从峰值开始,代码继续前进,只要当前元素大于下一个元素。这表示数组的递减部分。
-
验证并返回:
如果代码到达数组的末尾,则表示该数组是一个有效的山脉数组,因此返回
true
。否则,返回false
。
此代码现在将正确地确定给定数组是否是山脉数组,而不会遇到之前解决方案中遇到的问题。
标签:python,arrays,c,algorithm From: 73091436