秋招-笔试记录

秋招参加面试的公司如果有笔试，已经一并记录在对应的面经里了
因此，这里放的是参加了笔试，但是没有参加面试的一些公司的笔试记录

快速读取

理论上下面这段代码要能够默写出来，算法考试的时候直接用下面的就行了

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
import java.io.*;
import java.util.*;
public class Main {
    static BufferedReader br;
    static StringTokenizer st;
  
    static String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = nextInt();
        bw.write(n + " "); 
        bw.newLine();
        bw.flush();   
        bw.close();
    }
}

网易笔试

  1. n个不等高石柱heights，石柱都等宽为1，一个挡板，左右与某两个石柱平齐，高度不超过两个石柱及之间所有石柱的最低高度，求最大面积
  2. 非降序数组，分k个非空组，设代价为所有非空组中元素和的最大值，求最小代价
  3. 最多买卖两次的魔法物品交易，求最大利润

oppo笔试

（8.16）

  1. 正整数数组a长度为n，现在可以对数组中的每一个数都乘以 x ^ y(1<=x<=9, y为正整数)。求做完乘法操作后的数组中元素，末尾数字0的总数。如：5 6 2， 可以选择 5^1 -> 25, 30, 10，0的总数为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
// 100%
import java.io.*;
import java.util.*;

public class LuckyNumber {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        int fiveCount = 0, twoCount = 0;
        for (int i = 0; i < n; ++i) {
            nums[i] = in.nextInt();
            int five = count(nums[i], 5);
            int two = count(nums[i], 2);
            fiveCount += five;
            twoCount += two;
        }
        System.out.print(Math.max(fiveCount, twoCount));

        // 1是没意义的，因为不会变的更好
        // 10 = 2 * 5 = 1 * 10
        // 所以其实就是看乘以多少个2，或者多少个5
        // 统计5的因数个数和2的因数个数就行了

    }

    public static int count(int num, int x) {
        if (num == 0) {
            return 0;
        }
        int ans = 0;
        while (num % x == 0) {
            ans++;
            num /= x;
        }
        return ans;
    }
}
  1. 正整数数组a（长度为n），和两个正整数x和y。判断数组是否存在两个不同的元素i,j使得：x异或(ai+aj) = y。输出Yes或者No；
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
// 100%
import java.io.*;
import java.util.*;

public class TwoNumberSum {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int y = in.nextInt();

        int z = (x ^ y);

        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = in.nextInt();
        }
        Arrays.sort(nums);
        // 两数之和为z
        int i = 0, j = n - 1;
        boolean exist = false;
        while (i < j) {
            int sum = nums[i] + nums[j];
            if (sum > z) {
                --j;
            } else if (sum < z) {
                ++i;
            } else {
                exist = true;
                break;
            }
        }
        if (exist) {
            System.out.print("Yes");
        } else {
            System.out.print("No");
        }

    }
}
  1. 正整数数组(1<=ai<=10^5)和a b c d。现在需要把数组中的每个元素都变为任意相同的数，求最小的代价。把一个数字增加1代价为a，把一个数字增加2代价为b，把一个数字减少1代价为c，把一个数字减少2代价为d。输出最小代价
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 93.77%
import java.io.*;
import java.util.*;


public class BalanceSeries {
    static int n;
    static int[] nums;

    static int increaseOne;
    static int increaseTwo;

    static int decreaseOne;
    static int decreaseTwo;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        int d = in.nextInt();

        // 增加的最小单位
        increaseOne = Math.min(a, b + c);
        increaseTwo = Math.min(2 * a, b);

        // 减少的最小单位
        decreaseOne = Math.min(c, a + d);
        decreaseTwo = Math.min(2 * c, d);


        nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = in.nextInt();
        }



        // 奇数的情况
        int left = 1, right = 100000 - 1;
        while (left < right - 2) {
            int mid = left + (right - left) / 2;
            // 必须为奇数
            if (mid % 2 == 0) {
                mid += 1;
            }
            long cost1 = calculateCost(mid);
            long cost2 = calculateCost(mid + 2);
            if (cost1 > cost2) {
                left = mid;
            } else {
                right = mid;
            }
        }

        long ans = Math.min(calculateCost(left), calculateCost(right));

        // 偶数的情况
        left = 2;
        right = 100000;
        while (left < right - 2) {
            int mid = left + (right - left) / 2;
            // 必须看奇数
            if (mid % 2 != 0) {
                mid += 1;
            }
            long cost1 = calculateCost(mid);
            long cost2 = calculateCost(mid + 2);
            if (cost1 > cost2) {
                left = mid;
            } else {
                right = mid;
            }
        }

        ans = Math.min(Math.min(calculateCost(left), calculateCost(right)), ans);
        System.out.println(ans);
    }

    public static long calculateCost(int target) {
        long cost = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > target) {
                int twoCount = (nums[i] - target) / 2;
                int oneCount = (nums[i] - target) % 2;
                cost += (long) twoCount * decreaseTwo + oneCount * decreaseOne;
            } else {
                int twoCount = (target - nums[i]) / 2;
                int oneCount = (target - nums[i]) % 2;
                cost += (long) twoCount * increaseTwo + oneCount * increaseOne;
            }
        }
        return cost;
    }
}

饿了么

（9.5）

rw-rw-rw-,chmod gow- a.txt，则权限变为？

包含3个2和3个1的大根堆，有多少种可能？

三道编程题最后一题93.33%

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

public class Main {

    // 异或的运算符号是 ^

    public static void main(String[] args) throws IOException {

        int T = nextInt();
        while (T-- > 0) {
            
            int n = nextInt();
            int b = nextInt();

            int[] arr = new int[n];


            // 最大是2^12
            for (int i = 0; i < n; ++i) {
                arr[i] = nextInt();
               
            }
            int maxVal = 4096;


            // 记录选了一件装备的可能值
            boolean[][] exist = new boolean[n + 1][maxVal + 1];
            exist[0][0] = true;

            for (int i = 0; i < n; ++i) {
                // 选了j件装备
                for (int j = i; j >= 0; --j) {
                    for (int k = 0; k <= maxVal; ++k) {
                        if (exist[j][k]) {
                            exist[j + 1][k ^ arr[i]] = true;
                        }
                    }
                }
            }

            // 计算可能的最优解
            int maxAns = 0;
            int minCnt = 0;
            for (int i = 0; i <= n; ++i) {
                for (int k = 0; k <= maxVal; ++k) {
                    if (exist[i][k]) {
                        int newRes = k + i * b;
                        if (newRes > maxAns) {
                            maxAns = newRes;
                            minCnt = i;
                        }
                    }
                }
            }
            bw.write(minCnt + " " + maxAns);
            if (T != 0) {
                bw.newLine();
            }
        }
    }
}

滴滴笔试

算法题：

第一题是dp

第二题是可以用二分，但是边界很麻烦，最后都没处理好。但是第二题值得一做，未来做的时候如果单二分太麻烦，可以考虑做两次二分处理

虎鲸文娱

（开心，很久没出现过的全过了，做了70min）

算法题：

  1. 根据区间输出结果即可
  2. 给定两个数组a,b，求数组a中有多少个数x满足f(x)>0，其中f(x)=(b1-x)(b2-x)…(bn-x)。数组的长度为10^5，元素的大小为-2^30~2^30之间
  3. 给一个整数n，求满足1<=a<b < c <= n 的三元组(a,b,c),且ab,bc,ac都是完全平方数(n<=2*10^5)

第三题的思路就是首先(a,b,c)都是完全平方数的情况下成立，且(ka,kb,kc)也成立。

c从1到sqrt(n)遍历，找C(n-1,2)求出(a,b)的组合。但是在求k的可能性是，要注意k不要取含有完全平方数的因子，避免和其他结果重复判断

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

public class Main {
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        // 其实就是先求出完全平方数的因子
        int maxSqrt = (int) Math.sqrt(n);
        int ans = 0;

        boolean[] fitsK = new boolean[n + 1];
        Arrays.fill(fitsK, true);

        for (int i = 2; i <= maxSqrt; ++i) {
            int cur = i * i;
            int index = 1;
            while (index * cur <= n) {
                fitsK[index * cur] = false;
                ++index;
            }
        }

        int[] karr = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (fitsK[i]) {
                karr[i] = karr[i - 1] + 1;
            } else {
                karr[i] = karr[i - 1];
            }
        }


        for (int c = 3; c <= maxSqrt; ++c) {
            int possible = (c - 1) * (c - 2) / 2;
            // 求出最大满足题意的k
            int maxK = n / (c * c);

            // 求 <= maxK的非完全平方数的个数
            int possibleK = karr[maxK];
            ans += possible * possibleK;
        }
    }
}