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

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
23
37
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务