小米笔试9/19-装箱+排序挑战

第一题:装箱(动态规划)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt(), n = sc.nextInt(), c = sc.nextInt(); // 容量 + 玩具个数 + 填充物个数
            int[] a = new int[n + c];
            for (int j = 0; j < n; j++) {
                a[j] = sc.nextInt();
            }
            for (int j = n; j < n + c; j++) {
                a[j] = 1;
            }
            boolean res = checkFull(N, n, a);

            if (res) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        sc.close();
    }

    private static boolean checkFull(int N, int c, int[] a) {
        if (N <= c)
            return true;
        boolean[][] dp = new boolean[a.length][N + 1];
        if (a[0] <= N) {
            dp[0][a[0]] = true;
        }
        for (int i = 0; i < a.length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j <= N; j++) {
                if (a[i] <= j) {
                    dp[i][j] = dp[i - 1][j - a[i]];
                }
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            }
        }

        return dp[a.length - 1][N];
    }
}

第二题:排序挑战(贪心)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = sc.nextInt();
            }
            int[] b = new int[n];
            for (int j = 0; j < n; j++) {
                b[j] = sc.nextInt();
            }
            boolean res = checkCanExchange(a, b, n);
            if (res) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        sc.close();
    }

    private static boolean checkCanExchange(int[] a, int[] b, int n) {
        return checkUp(a, b) || checkUp(b, a) || checkDown(a, b) || checkDown(b, a);
    }

    private static boolean checkDown(int[] a, int[] b) {
        int n = a.length;
        int[] target = new int[n];
        int[] other = new int[n];
        for (int i = 0; i < n; i++) {
            target[i] = a[i];
            other[i] = b[i];
        }
        int pre = 10001;
        for (int i = 1; i < n; i++) {
            int minV = Math.min(target[i], other[i]);
            int maxV = Math.max(target[i], other[i]);
            if (maxV <= pre) {
                target[i] = maxV;
                pre = target[i];
            } else {
                if (minV <= pre) {
                    target[i] = minV;
                    pre = target[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean checkUp(int[] a, int[] b) {
        int n = a.length;
        int[] target = new int[n];
        int[] other = new int[n];
        for (int i = 0; i < n; i++) {
            target[i] = a[i];
            other[i] = b[i];
        }
        int pre = 0;
        for (int i = 0; i < n; i++) {
            int minV = Math.min(target[i], other[i]);
            int maxV = Math.max(target[i], other[i]);
            if (minV >= pre) {
                target[i] = minV;
                pre = target[i];
            } else {
                if (maxV >= pre) {
                    target[i] = maxV;
                    pre = target[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

#小米笔试##25秋招#
全部评论
感谢佬
1 回复 分享
发布于 09-19 17:37 山东
大佬😊
点赞 回复 分享
发布于 09-19 17:45 山东
mark
点赞 回复 分享
发布于 09-19 18:02 江西
谢谢佬
点赞 回复 分享
发布于 09-19 18:05 湖南
膜拜大佬!
点赞 回复 分享
发布于 09-19 18:05 重庆
膜拜佬
点赞 回复 分享
发布于 09-19 21:51 江西
点赞 回复 分享
发布于 09-19 22:07 湖北
第二题为什么要checkUp(a, b)又checkUp(b, a)呢,我看了下函数体这两个的结果应该是等效的吧
点赞 回复 分享
发布于 09-20 11:00 四川
太厉害了,思路简单明了。
点赞 回复 分享
发布于 09-20 11:35 安徽

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
08-15 16:48
想要一个AK:问题很多加微信私聊 (一个赞十道算法题,我看看有多少)
点赞 评论 收藏
分享
23 33 评论
分享
牛客网
牛客企业服务