9.19 小米笔试第二题
两个数组是否能通过相同位置的无限次交换,使其中一个数组变为有序的
为什么过不了呢,求大佬指出错误
import java.util.*;
/*
2
5
1 3 5 2 4
5 2 3 4 1
7
1 2 3 4 3 2 1
4 3 2 1 2 3 4
* */
public class xiaomi_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int size = in.nextInt();
while(size-- > 0) {
int number = in.nextInt();
int[] arr1 = new int[number];
int[] arr2 = new int[number];
for(int i = 0; i < number; i++){
arr1[i] = in.nextInt();
}
for(int i = 0; i < number; i++){
arr2[i] = in.nextInt();
}
if(judgeAsc(arr1, arr2) || judgeDesc(arr1, arr2)) {
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
// 判断能否升序
private static boolean judgeAsc(int[] arr1, int[] arr2){
int n = arr1.length;
boolean[][] dpNoSwap = new boolean[n][2];
boolean[][] dpSwap = new boolean[n][2];
dpSwap[0][0] = true;
dpSwap[0][1] = true;
dpNoSwap[0][0] = true;
dpNoSwap[0][1] = true;
for(int i = 1; i < n; i++){
// 不交换即可保证顺序
if(dpNoSwap[i - 1][0] && arr1[i - 1] <= arr1[i]){
dpNoSwap[i][0] = true;
}
if(dpNoSwap[i - 1][1] && arr2[i - 1] <= arr2[i]){
dpSwap[i][0] = true;
}
// 前一个没交换,这一次交换
if(dpNoSwap[i - 1][0] && arr1[i - 1] <= arr2[i]){
dpSwap[i][0] = true;
}
if(dpNoSwap[i - 1][1] && arr2[i - 1] <= arr1[i]){
dpSwap[i][1] = true;
}
// 前一轮交换,这轮不交换
if(dpSwap[i - 1][0] && arr2[i - 1] <= arr1[i]){
dpNoSwap[i][0] = true;
}
if(dpSwap[i - 1][0] && arr1[i - 1] <= arr2[i]){
dpNoSwap[i][1] = true;
}
// 前一轮交换,这轮交换
if(dpSwap[i - 1][1] && arr1[i - 1] <= arr1[i]){
dpSwap[i][0] = true;
}
// 前一轮交换,这轮交换
if(dpSwap[i - 1][1] && arr2[i - 1] <= arr2[i]){
dpSwap[i][1] = true;
}
}
return dpSwap[n - 1][0] || dpNoSwap[n - 1][0] || dpSwap[n - 1][1] || dpNoSwap[n - 1][1];
}
// 判断能否降序
private static boolean judgeDesc(int[] arr1, int[] arr2){
int n = arr1.length;
boolean[][] dpNoSwap = new boolean[n][2];
boolean[][] dpSwap = new boolean[n][2];
dpSwap[0][0] = true;
dpSwap[0][1] = true;
dpNoSwap[0][0] = true;
dpNoSwap[0][1] = true;
for(int i = 1; i < n; i++){
// 不交换即可保证顺序
if(dpNoSwap[i - 1][0] && arr1[i - 1] >= arr1[i]){
dpNoSwap[i][0] = true;
}
if(dpNoSwap[i - 1][1] && arr2[i - 1] >= arr2[i]){
dpSwap[i][0] = true;
}
// 前一个没交换,这一次交换
if(dpNoSwap[i - 1][0] && arr1[i - 1] >= arr2[i]){
dpSwap[i][0] = true;
}
if(dpNoSwap[i - 1][1] && arr2[i - 1] >= arr1[i]){
dpSwap[i][1] = true;
}
// 前一轮交换,这轮不交换
if(dpSwap[i - 1][0] && arr2[i - 1] >= arr1[i]){
dpNoSwap[i][0] = true;
}
if(dpSwap[i - 1][0] && arr1[i - 1] >= arr2[i]){
dpNoSwap[i][1] = true;
}
// 前一轮交换,这轮交换
if(dpSwap[i - 1][1] && arr1[i - 1] >= arr1[i]){
dpSwap[i][0] = true;
}
// 前一轮交换,这轮交换
if(dpSwap[i - 1][1] && arr2[i - 1] >= arr2[i]){
dpSwap[i][1] = true;
}
}
return dpSwap[n - 1][0] || dpNoSwap[n - 1][0] || dpSwap[n - 1][1] || dpNoSwap[n - 1][1];
}
}
#小米#