8月22日美团笔试

前言

2020年08月22日下午四点开始做的，普通编程四题，另外是还有一道什么特殊编程题？

是在赛码网上做的，允许使用自己的IDE来做，但是体感稍微有点问题。

第一题

给定三个规则，然后判断给定的字符串符不符合要求：

• 首字母必须是大写或者小写字母。
• 整个字符串必须只能有大写字母，小写字母或者数字。
• 整个字符串必须要有数字。

那就老老实实根据它给的规则做呗，其实JDK中的Character里面有现成的函数可以调用，Character.isDigit()判断是否是数字，Character.isUpperCase()判断是否是大写字母，当然自己实现的话也是非常简单。

当然也可以使用正则表达式来做，我不太熟就没用。

我提交的最终的代码是这样的：

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取输入，直到没有整型数据可读
        while(sc.hasNext()){
            String s = sc.nextLine();
            int n = Integer.valueOf(s);
            List<String> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(sc.nextLine());
            }

            for (String s1 : list) {
                if (judge(s1)) {
                    System.out.println("Accept");
                } else {
                    System.out.println("Wrong");
                }
            }
        }


    }

    private static boolean judge(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }
        // 首字母必须是大写或者小写字母
        char c = s.charAt(0);
        if (isAlpha(c)) {
            boolean hasDigit = false;
            for (int i = 1; i < s.length(); i++) {
                char cur = s.charAt(i);
                if (isDigit(cur) || isAlpha(cur)) {
                    if (isDigit(cur)) {
                        hasDigit = true;
                    }
                } else {
                    return false;
                }
            }
            if (hasDigit) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    private static boolean isAlpha(char c) {
        if (('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z')) {
            return true;
        } else {
            return false;
        }
    }

    private static boolean isDigit(char c) {
        if (('0' <= c && c <= '9')) {
            return true;
        } else {
            return false;
        }
    }
    
}

这题就代码来说，是非常简单的，毫无难度可言，但是似乎赛码网的输入输出判定有点问题，我记得我一开始也是卡在18%，然后改了一下输出就过了。

第二题

外卖跑腿费计算。给定N个订单，从中选择M个订单。其中每个订单由两部分组成，分别是基础费用和物品的重量，最终的收益是基础费用加上物品重量乘以2。然后要你选择收益最大的M个订单的编号，如果有多个符合要求的，按照字典序排序。

这题其实读懂很简单，无非就是把它给你的两个数字按照a+2b算出一个结果，然后排序就好了啊….

这题的坑点在于，算了我给个例子就明白了：

假设给定你三个订单，它们的和分别是3 3 4，现在要你从中选出两个订单，那第三个订单肯定是要的，然后按照上面的要求，1号订单和2号订单的利润都是3，那我应该选择1号订单，所以最后的结果应该是3 1，但是题目坑就坑在，跟你玩了个文字游戏，你最后应该输出的是1 3…..

然后我卡在这里卡了很久，甚至还用小顶堆去重新写了一遍…浪费了比较多的时间。下面给出我用小顶堆的解法…

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String[] s1 = s.split(" ");
            int n = Integer.parseInt(s1[0]);
            int m = Integer.parseInt(s1[1]);
            Map<Money, Integer> map = new HashMap<>();
            int index = 0;
            List<Money> list = new ArrayList<>();
            PriorityQueue<Money> maxHeap = new PriorityQueue<>(m, (Money m1, Money m2) -> {
                return m1.sum - m2.sum;
            });
            
            for (int i = 0; i < n; i++) {
                String[] s2 = sc.nextLine().split(" ");
                Money money = new Money(Integer.parseInt(s2[0]), Integer.parseInt(s2[1]), index);
                if (maxHeap.size() != m) {
                    maxHeap.offer(money);
                } else if (maxHeap.peek().sum < money.sum) {
                    maxHeap.poll();
                    maxHeap.offer(money);
                }
                map.put(money, index);
                index++;
            }
            for (Money money : maxHeap) {
                list.add(money);
            }
            
            // 这样输出是怕最后还卡空格....
            for (int i = 0; i < m - 1; i++) {
                Money money = list.get(i);
                System.out.print(map.get(money) + 1 + " ");
            }
            Money money = list.get(m - 1);
            System.out.print(map.get(money) + 1);
        }
    }

    static class Money {
        public int v;
        public int w;
        public int index;
        public int sum;

        public Money(int v, int w, int index) {
            this.v = v;
            this.w = w;
            this.index = index;
            this.sum = v + 2 * w;
        }

        @Override
        public String toString() {
            return "Money{" +
                    "v=" + v +
                    ", w=" + w +
                    ", index=" + index +
                    '}';
        }

    }
}

第三题

给定一个数组，长度是N，然后给定1-N全排列中的一个顺序，比如数组是[1,3,5]，那么对应的全排列可以是[1,3,2]，意味着第一次从数组的第一个位置断开，然后数组就分成了两部分，输出这两部分较大的那个部分的和。我是用暴力法做的，

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            arr[sc.nextInt()-1] = -1;
            System.out.println(helper(arr));
        }
    }

    private static int helper(int[] arr) {
        int sum = 0;
        int res = 0;
        for (int i : arr) {
            if (i == -1) {
                res = Math.max(res, sum);
                sum = 0;
            } else {
                sum += i;
            }
        }
        return res;
    }
}

然后就只过了18%，网上看到别人跟我一模一样的思路，也是暴力法，过了64%….唯一的区别就是它是一次性的读取完所有的数据，然后进行处理的，我这边是读一个数字判断一次的，可能是因为这个？？？

第四题

图的题我是真的不会，考虑是不是要去补一补（但是似乎也就笔试有点用）？利用printf(15)骗了18%的通过率2333333。

第五题

给定一个数组，里面的数字各不相同，然后再给定两个数字，分别是A队的人数和B队的人数（我记得应该是A队人数加B队人数等于数组长度，不确定了），要求是A队平均分和B队平均分加起来最大。

我用的是DFS做的，因为一个人要么是A队的，要么是B队的（如果上面A+B人数不等于数组长度，那么还有第三种可能，就是既不是A也不是B），这样的话时间复杂度是O(2ⁿ)，最后只过了18%…..

总结

我做过三个主流平台的题目，分别是leetcode，牛客和赛码，其中leetcode会给定你一个函数，然后你只需要到对应的函数里面去实现功能就好了，不用考虑输入和输出的问题。而另外两家都是需要自己输入和输出，尤其是赛码….这输入输出卡了多少人。

然后从美团的这次笔试中也学到了一些教训：

• 实在不会做可以直接输入样例的答案骗点分（似乎只有赛码后台是包含样例数据的）
• 输入请一次性读完，不要分阶段。