8月22日美团笔试

前言

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

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

第一题

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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…..

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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],意味着第一次从数组的第一个位置断开,然后数组就分成了两部分,输出这两部分较大的那个部分的和。我是用暴力法做的,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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%….唯一的区别就是它是一次性的读取完所有的数据,然后进行处理的,我这边是读一个数字判断一次的,可能是因为这个???

第四题

image-20200823141535302

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

第五题

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

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

总结

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

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

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