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];
    }
}

#小米#
全部评论
这题简单,我10分钟就A了,AB序列同时遍历,a和b存在大于等于prev视为可行,取可行a,b的小值做当前值(结束后赋给之前值prev),如果不可行就False,遍历完都可行就True;前面覆盖递增情况,递减情况把A和B取逆序重复一遍即可
2 回复 分享
发布于 09-19 19:25 上海

相关推荐

09-19 19:45
门头沟学院 C++
点赞 评论 收藏
分享
1 1 评论
分享
牛客网
牛客企业服务