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]; } }#小米#