阿里0325笔试情况

https://blog.csdn.net/weixin_44484668/article/details/123470439

单选题6个，每题2分，各个类型都有，比较简单。

多选题6个，每题4分，少选给1/3分，也不难，就是有的会比较纠结

编程题三道，一道easy，一道medium，一道hard。

第一题简单字符串模拟（14分），问密码情况，满足三个条件：

比较坑的点在于输出这些英文容易输错（可以cv），ACM模式下很多人不会正确的输入输出导致只有80%正确率，比如int后需要接受空格，字符串可能存在空格的情况。

关于java在ACM中的输入输出可以看我的这篇文章

https://blog.csdn.net/weixin_44484668/article/details/123470439

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        String next = sc.nextLine();
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < t; i++) {
            String str = sc.nextLine();
            if (str.length() < 5 || str.length() > 12) System.out.println("字符串长度不合法");
            else if (!isLetter(str)) System.out.println("非全英文字符串");
            else if (set.contains(str)) System.out.println("字符串存储过了");
            else {
                set.add(str);
                System.out.println("合法字符串");
            }
        }
    }

    private static boolean isLetter(String str) {
        for (int i = 0; i < str.length(); i++) {
            if (!Character.isLetter(str.charAt(i))) return false;
        }
        return true;
    }
}

第二题（20分），没做出来，自己太菜了，做题也少。这道题看着挺简单的，然后0%通过就懵了，时间都花在第二题了，导致第三题没时间做。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int[] nums = new int[5];
            for (int j = 0; j < 5; j++) {
                nums[j] = sc.nextInt();
            }
            Arrays.sort(nums);
//            System.out.println(min1 + "\t" + min2 + "\t" + min3);
            int res = 0;
            if (nums[1] == nums[2]) {
                res = nums[1];
            } else {
                res = nums[1] + Math.min(nums[0], nums[2] - nums[1]);
            }
            System.out.println(res);
        }
    }

0分，没想通。

第三题（30分）背包问题，参考大佬的题解，发现确实是01背包问题，不过贪心也可以过一些案例。

思路是只要斜率k=-a/b不一样，那么两条直线必相交。用一个map存储斜率和对应的条数，比如[1-2],[2-3],[3-4]，那么就和力扣416. 分割等和子集，494. 目标和，1049. 最后一块石头的重量 II这几道题一样了。

只有两个颜色，所以将对应的条数分为两堆，一堆为x（白色），一堆为y（黑色），题目要求xy最大，当且仅当x==y时最大，但是背包问题不一定满足两堆个数一样，所以最后结果就是x(sum-x)。

不得不说背包用来求子集划分问题还是很好用的。

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        //key-斜率，value-个数
        HashMap<Double, Integer> map = new HashMap<>();
        for (int i = 0; i < t; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();//c没用
            double k = 1.0 * a / b;//用double，int会把1.1和1.9斜率算成一样
            map.put(k, map.getOrDefault(k, 0) + 1);
        }
        int sum = 0, n = map.size();
        int[] weight = new int[n], values = new int[n];
        int index = 0;
        for (Map.Entry<Double, Integer> entry : map.entrySet()) {
            sum += entry.getValue();
            weight[index] = entry.getValue();
            values[index] = entry.getValue();
        }
        int w = sum / 2;
        //dp[n][w]:针对所有的条数，不超过一半和的最大和，比如[1,3,3],凑不超过3的最大和，就是[3]了，所以一堆是3，一堆是4，结果12.
        //dp[i][j]:前i个物品，第i个物品的重量是weight[i],价值是value[i],背包容量是j，求最大价值。
        int[][] dp = new int[n + 1][w + 1];
        //base case
        //dp[0][...]=0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= w; j++) {
                if (j >= weight[i - 1]) {//能够装下第i个物品
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];//装不下第i个物品
                }
            }
        }
        System.out.println(dp[n][w] * (sum - dp[n][w]));//一堆和是x，一堆和是y
    }
}

这题我暴力就过了10%的案列，第二题懵了，第三题没时间看。

总结下来就是，时间没分配到位，选择题还检查了一遍（我也服了），以为最后一道题肯定hard所以就放弃了，但是这个确实还是比较接近leetcode原题的，给时间想想应该能想到，或者过多一些case，当然最主要还是太菜了。

#阿里笔试##笔试题目##阿里巴巴#