题目一
给定一个长度为len的整数数组 arr,如果它是有效的凸数组就打印输出字符串"true",否则打印输出"false"。
如果数组arr 满足下述条件,那么它是一个有效的凸数组:
- len >= 3
- 在 0 < i < len - 1 条件下,存在 i 使得:
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[len - 1]
有效凸数组图示如下:
样例1
输入
arr = [2,1]
输出
false
运用单指针方法
题目二
输入一个长度为len的数组a和一个整数peak,你需要将数组a构造成一个最大值下标等于peak的有效凸数组,你需要打印出该有效凸数组。下面对构造完成的有效凸数组做进一步的限制,要求构造的有效凸数组至少包含一个等腰三角区或直角三角区(当peak=len-1或者peak=0时有效凸数组不含有等腰三角区)。
-
等腰三角区底边中线元素为数组最大值,下标为peak。要求等腰三角区内的数组元素满足
a[peak]>=a[peak-1]>=a[peak+1]>=a[peak-2]>=a[peak+2].... - 直角三角区内的所有元素小于或等于等腰三角区的最小元素。
- 直角三角区内的元素有序,且大值的下标(相比于小值)更接近peak。
输出描述
输出完成构造的有效凸数组。
#include<stdio.h>
int main(){
int len,peak,num,a[10001]={},b[10001]={},s;
scanf("%d %d",&len,&peak);
for(int i=1;i<=len;i++){//
scanf("%d",&a[i]);
}
for(int i=1;i<len;i++){
for(int j=i+1;j<=len;j++){
if(a[i]>a[j]){
a[i]^=a[j];
a[j]^=a[i];
a[i]^=a[j];
}
}
}
int cn=len;
b[peak]=a[cn--];
for(s=1; peak+s<len && peak-s>=0 ;s++){
b[peak-s]=a[cn--];
b[peak+s]=a[cn--];
}
//如果m-s<0会跳出,这时就知道右边其实更长
if(peak-s>=0) for(;peak-s>=0;s++) b[peak-s]=a[cn--];
else for(;peak+s<len;s++) b[peak+s]=a[cn--];
for(int i=0;i<len;i++){
printf("%d ",b[i]);
}
}
心得
这题卡人的地方就是怎么找到peak两边配套的数,怎么把剩余的空位根据peak的位置补上数。
其实只要使用一个s=1 用 s++,peak-s>=0 && m+s<n,让计算机判断,如果peak-s<0,则说明右边更长;如果peak+s》n,则说明左边更长,然后依据相同的循环条件赋值到底。