8月13日bilibili笔试

前言

8月13日bilibili的在线笔试。一共是三十道选择题和三道编程题。平心而论是比较非常简单的。

选择题

选择题里比较有印象的是给定一个CRC的生成式 x^4+x+1，然后求1101011111的crc校验码，我不会，瞎选的。这个应该是计算机网络中第二层的时候我记得讲过，完全记不起来怎么算。

眼前一亮的是考了CSRF的防御手段，还考了docker的底层实现。总的来说广度还是非常不错的。

不过我现在有点怀疑这些有选择题的公司，是不是都是用的牛客的题库？

编程

算24点

第一题上来就非常刺激，这题看似容易，其实陷阱有点多。后来去leetcode看了一眼，emmm hard…. 放第一题是不是不合适啊。

public boolean Game24Points(int[] arr) {
    return fun(new double[]{arr[0], arr[1], arr[2], arr[3]});
}

public boolean fun(double[] arr) {
    if (arr.length == 2) {
        // 循环跳出
        return helper(arr[0], arr[1]);
    }

    // 缩减
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            // 缩减一位

            double[] small = new double[arr.length - 1];
            int smallLength = small.length - 1;
            int k = 0;
            int h = 0;
            while (k < arr.length) {
                if (j != k && i != k) {
                    small[h] = arr[k];
                    h++;
                }
                k++;
            }

            // 根据四则运算来做
            small[smallLength] = arr[i] + arr[j];
            if (fun(small)) {
                return true;
            }

            small[smallLength] = arr[i] - arr[j];
            if (fun(small)) {
                return true;
            }

            small[smallLength] = arr[j] - arr[i];
            if (fun(small)) {
                return true;
            }

            small[smallLength] = arr[i] * arr[j];
            if (fun(small)) {
                return true;
            }

            small[smallLength] = arr[i] / arr[j];
            if (fun(small)) {
                return true;
            }
        }
    }

    return false;
}

public boolean helper(double i, double j) {
    if (i + j == 24) {
        // + 只有一种
        return true;
    } else if (j - i == 24 || i - j == 24) {
        // - 有两种
        return true;
    } else if (i * j < 24.000001 && i * j > 23.999999) {
        // x 只有一种
        return true;
    } else if (i != 0 && j / i < 24.000001 && j / i > 23.999999) {
        return true;
    } else if (j != 0 && i / j < 24.000001 && i / j > 23.999999) {
        return true;
    }
    return false;

}

稍微解析一下：首先是helper这个函数，就是给你两个数字，然后判断这两个数字能否经过加减乘除四则运算来得到。加法、乘法很简单。减法你需要考虑是a-b还是b-a，也不难；除法就还需要多考虑一层0不能做除数。

然后通过不断缩小数组来完成我们的功能。

判断括号表达式是否合法

public boolean IsValidExp(String s) {
    int length = s.length();
    if (length == 0) {
        return true;
    }
    Deque<Character> deque = new LinkedList<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '{' || c == '(' || c == '[') {
            deque.addLast(c);
        } else if (c == '}' || c == ')' || c == ']') {
            if (deque.isEmpty()) {
                return false;
            }
            if (c == '}') {
                if (deque.getLast() == '{') {
                    deque.removeLast();
                } else {
                    return false;
                }
            } else if (c == ')') {
                if (deque.getLast() == '(') {
                    deque.removeLast();
                } else {
                    return false;
                }
            } else {
                if (deque.getLast() == '[') {
                    deque.removeLast();
                } else {
                    return false;
                }
            }

        }
    }
    if (deque.isEmpty()) {
        return true;
    } else {
        return false;
    }
}

emmm 感觉是最基础的题目了吧。我做的时候不小心把一个括号给打错了，导致过了80%….

找钱问题

题目都懒得打…太简单了…

public int GetCoinCount(int N) {
    int remain = 1024 - N;
    if (remain <= 0) {
        return 0;
    }
    int coin64 = remain / 64;
    remain = remain - coin64 * 64;
    int coin16 = remain / 16;
    remain = remain - coin16 * 16;
    int coin4 = remain / 4;
    remain = remain - coin4 * 4;
    return (coin4 + coin16 + coin64 + remain);
}