题目描述
给定一个长度为n的整数数组a，元素均不相同，问数组是否存在这样一个片段，只将该片段翻转就可以使整个数组升序排列。其中数组片段[l,r]表示序列a[l], a[l+1], …, a[r]。原始数组为
a[1], a[2], …, a[l-2], a[l-1], a[l], a[l+1], …, a[r-1], a[r], a[r+1], a[r+2], …, a[n-1], a[n]，
将片段[l,r]反序后的数组是
a[1], a[2], …, a[l-2], a[l-1], a[r], a[r-1], …, a[l+1], a[l], a[r+1], a[r+2], …, a[n-1], a[n]。
思路
一个数组保存原始数据，另一个数组保存排序后的数据
找到两个数组对应元素不相同的最左边和最右边下标
比较这个范围内的数组元素是否满足对称关系，如果满足，输出yes，否则输出no
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt())
{
int len = scanner.nextInt();
int[] array = new int[len];
int[] copy = new int[len];
for(int i=0;i<len;i++)
{
array[i] = scanner.nextInt();
copy[i] = array[i];
}
Arrays.sort(copy);
int left = 0,right = len-1;
while(left<len && copy[left]==array[left]) left++;
while(right>=0 && copy[right]==array[right]) right--;
int i;
for(i=0;i<=right-left;i++)
{
if(copy[left+i]!=array[right-i])
break;
}
if(i>right-left)
System.out.println("yes");
else
System.out.println("no");
}
}
}
|
考察点