美团2021校招前端笔试题

发表于 更新于 分类于

前言

在美团的校招尾声试着投了下，百度应该是没了，就一直挂着，挺揪心的，不过也无所谓了，当作尝试吧。

早上10点到12点，做的还行把，总共5道，ac了4道，1道确实不会😂

题目

争夺地盘

第一题，感觉是白给的，做做循环累加数量即可

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
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        int q = in.nextInt();
        // 把A想要的p块土地的序号丢到set里面
        Set<Integer> setA = new HashSet<>(p);
        for (int i = 0; i < p; i++) {
            setA.add(in.nextInt());
        }
        // B想要的q块存数组即可
        int[] B = new int[q];
        for (int i = 0; i < q; i++) {
            B[i] = in.nextInt();
        }
        
        // 两个国家共同想要的土地序号存在set里面
        Set<Integer> r = new HashSet<>();
        // 遍历B，如果setA里面也有，加入r里面
        for (int i = 0; i < q; i++) {
            if (setA.contains(B[i])) {
                r.add(B[i]);
            }
        }
        // 现在有两个国家共同想要的土地序号了，直接遍历计数即可
        int cA = 0;
        int cB = 0;
        // 遍历setA找A单独想要的土地序号
        for (int i : setA) {
            if (!r.contains(i)) {
                cA++;
            }
        }
        // 遍历B找到B到哪都想要的土地序号
        for (int i : B) {
            if (!r.contains(i)) {
                cB++;
            }
        }
        // 输出
        System.out.println(cA + " " + cB + " " + r.size());
    }
}

不看输入操作，时间复杂度O(p + 2q)=O(p + q)（应该是这么计算的把😂）

空间复杂度（这里不算数组B）最好情况下O(Math.min(p,q))，也就是setA此时为长度较小的一方，且没有公共的土地序号（r长度为0）

最坏情况下O(p + q)

修改大小写

第二题，感觉还是白给，对大小写计数，然后与长度的1/2相减即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String p = in.next();
        int len = p.length();
        // 大写字符个数
        int upperCount = 0;
        // 计数
        for (int i = 0; i < len; i++) {
            if (p.charAt(i) >= 'A' && p.charAt(i) <= 'Z') {
                upperCount++;
            }
        }
        // 通过大写字符推出小写字符
        int lowerCount = len - upperCount;
        // 为了使数量相同，大写小写应该都是len/2的个数，然后就是和大写或者小写个数相减即可
        System.out.println(len / 2 - Math.min(lowerCount, upperCount));
        // 下面这样写也可以
        // System.out.println(Math.max(lowerCount, upperCount) - len / 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
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        int[] array = new int[len];
        for (int i = 0; i < len; i++) {
            array[i] = in.nextInt();
        }
        
        // 这个dp的意思就是dp[k]，代表1^2^3^4^...^k的值
        int[] dp = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            dp[i] = i ^ dp[i - 1];
        }
        
        // 根据题意，完全可以先把每个元素异或，用result保存
        int result = 0;
        for (int i = 0; i < len; i++) {
            result ^= array[i];
        }
        
        // 本题的核心过程
        for (int i = 1; i <= len; i++) {
            int r = len % i;
            int c = len / i;
            if (c % 2 != 0) {
                result ^= dp[i - 1];
            }
            if (r > 0) {
                result ^= dp[r];
            }
        }
        
        // 输出
        System.out.println(result);
    }
}

这题难点就是上面我标的核心过程这段，我们可假设现在有6个数，也就是说现在要mod1一直到mod6

比如现在位于第一个数n1，那么异或的过程就是

n1 ^ (1 % 6) ^ (2 % 6) ^ (3 % 6) ^ (4 % 6) ^ (5 % 6) ^ (6 % 6)

我们可以列出来一个表，如下

mod1 mod2 mod3 mod4 mod5 mod6
n1 0 1 1 1 1 1
n2 0 0 2 2 2 2
n3 0 1 0 3 3 3
n4 0 0 1 0 4 4
n5 0 1 2 1 0 5
n6 0 0 0 2 1 0

刚开始的时候我列了这个表，试图从横向来找规律，使得能够在O(1)时间内得到异或的结果，不过没想出来

卡了一会之后，尝试在纵向上做文章，发现了纵向上数字的规律

首先我们要知道异或，也就是^这个符号的意思，也就是二进制的两个位相同为0，不同为1，也就是

1 ^ 1 == 0, 0 ^ 1 == 1

对于两个相同的数字，他们的二进制表示是一样的，那么异或之后就会为0

OK，回到上边那个表，我们可以每一列进行分析

  • 对于mod1这一列，结果都是0，不太好看出规律
  • 对于mod2这一列，1，3，5对mod2的结果是一样的，2，4，6也是，也就是数据可以分成3组
  • 对于mod3这一列，1，4|2，5|3，6对mod3结果是相同的，也就是数据分成了两组
  • 对于mod4这一列，1，5|2，6|3|4对mod4结果相同，这里3，4没有下一个数字与之对应
  • 对于mod5这一列，1，6|2|3|4|5对mod5结果相同，这里2，3，4，5没有下一个数字与之对应
  • 对于mod6这一列，1|2|3|4|5|6对mod6结果相同，这里每个数都没有没有下一个数字与之对应

那么根据上面的分析，表可以变为

mod1 mod2 mod3 mod4 mod5 mod6
n1 0 1 1 1 1 1
n2 0 0 2 2 2 2
n3 0 1 0 3 3 3
n4 0 0 1 0 4 4
n5 0 1 2 1 0 5
n6 0 0 0 2 1 0

没错，每列都一直在重复，比如

第二列1->0为重复序列

第三列1->2->0为重复序列

第四列1->2->3->0为重复序列

第四列1->2->3->4->0为重复序列

那么结合之前说的异或的性质，如果是偶数次重复且没有剩余元素的话的话，那么本列结果一定为0，

如果奇数次重复且没有剩余元素，那么只要计算一次重复的序列

如果存在剩余元素，那么再单独异或然后加入结果集即可

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
public class Main {
    public static void main(String[] args) {
        // ...
        
        // 本题的核心过程
        // 每次循环计算1列的值
        for (int i = 1; i <= len; i++) {
            // 计算重复序列的次数
            int r = len % i;
            // 计算不足一次重复序列的数字数量
            int c = len / i;
            // 奇数次
            if (c % 2 != 0) {
                // i-1是因为重复序列最后一个数必是0
                result ^= dp[i - 1];
            }
            // 剩余元素加入，不足一次重复序列
            if (r > 0) {
                result ^= dp[r];
            }
        }
        
        // ...
    }
}

刚开始没使用dp来提前计算累计的异或的话，还是超时，使用之后，就可以通过了。

公司管理

1.png

这题完全看不懂啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，最后没时间做了…🤣

矩阵游戏

这题放在第二部分的卷子，刚开始看感觉很难，但是试了试其实不难，递归回到2x2的情况即可

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int n = in.nextInt();
        // 输出次数循环
        while (n > 0) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            // 构造一个2x2数组
            int[][] twoXTwo = {
                    {0, a},
                    {b, c}
            };
            // 对输入的点(x,y)进行递归
            int r = dfs(x, y, twoXTwo);
            // 输出
            System.out.println(r);
            n--;
        }
    }

    static int dfs(int x, int y, int[][] twoXTwo) {
        // 已经在2x2范围内了，直接返回对应位置的值
        if (x < 2 && y < 2) {
            return twoXTwo[x][y];
        }
        // 找到这个坐标最少应该是几x几的格子
        int len = 2;
        int max = Math.max(x, y);
        while (len <= max) {
            len = len * 2;
        }
        
        // 计算这个坐标位于哪个位置，左上，左下，右上，右下
        int div = len / 2;
        int result;
        if (x >= div && y >= div) {
            // 右下角元素
            result = twoXTwo[1][1] + dfs(x - div, y - div, twoXTwo);
        } else if (x < div && y >= div) {
            // 左上角元素
            result = twoXTwo[0][1] + dfs(x, y - div, twoXTwo);
        } else {
            // 左下角元素
            result = twoXTwo[1][0] + dfs(x - div, y, twoXTwo);
        }
        // 根据题意取mod
        return result % 1000000000;
    }
}

后记

总体上感觉很好，难度适中，下次一定还来😂