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 回复 分享
发布于 2024-09-19 19:25 上海

相关推荐

我是985研究生,最近学校在组织开题,大家都在非常紧张地准备,但我一直进入不了状态,很想做但是心又很浮躁。但我的室友们感觉都非常认真,每天醒来就开始看论文,睡着前最后一件事还是在看论文,我非常焦虑。我感觉自己甚至有点把大家当做假想敌了。这种比较心态还存在于生活的各种方面:看到有钱的同学会非常羡慕,看到朋友圈里面环游世界的留学生同学也会羡慕,看到那些工作后有自己的钱而过上较为阔绰的生活的时候还是羡慕,就仿佛只有自己一个人在阴暗爬行。而且这些比较是每时每刻的,为了不比较,我已经关闭了朋友圈,但是每次偶尔刷一下还是会难受很久。我知道比较是偷走幸福的小偷,但我好像控制不了,感觉自己是一个偷窥别人生活的...
若怜君欢:担心开题搞砸了,幻想拥有别人的生活,本质上是因为自卑,楼主小时候大概率是留守儿童或者父母关系很紧张,导致楼主没有安全感、焦虑、内耗。 这样的情况最好的办法就是建立自信和降低期待,建立自信不是一蹴而就,而是循序渐进,比如告诉自己允许自己第一次没把事情做好,失败了能搞清楚其中缘由而不是全盘否定自己,失败不是终点,放弃才是;降低期待只要记住一句话即可,能伴随你一生的,只有经验和学识,所以你对事情的态度应该更多地去思考它是否能带来学识和经验的增长,而不是仅仅用短期的利益作为唯一期待。 人生不是一成不变的,它是可以迭代更新的,去归纳总结自身的不足并结合实际去改进,去尝试一些新的思路和方法,不要固执钻牛角尖,也不要反复横跳,为自己设立一个高度聚集的精神内核,内核之上可以去尝试一切有利于自己更好的方式 以上就是我个人对生活的理解,共勉
点赞 评论 收藏
分享
04-18 00:32
已编辑
中南大学 Java
点赞 评论 收藏
分享
03-30 19:30
石家庄学院 Java
野蛮的柯基在游泳:都能入股了,还得是Java
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客企业服务