笔试时间：2022.9.2 19:00-21:00
岗位：游戏开发-服务器开发工程师
笔试平台：牛客

常规八股文19题（20分钟）

算法题（100分钟）

第一题（超难，好题！）

题目

求杨辉三角第n行的乘积，对10^9+7取模，n <= 10^6；
例如 3 = 1 * 2 * 1 = 2， 4 = 1 * 3 * 3 * 1 = 9；

想法与思路

如果要用动态规划计算第n行，需要O(n^2)的时间，太慢了。应该是找规律。
找来找出，好像某一行没有明显数值规律。
灵光一闪想到，杨辉三角和二项式定理有关，于是立马尝试了组合数学，果然可以！

令n=n-1，第n行（按照题目定义是n-1，用n表示比较方便）的数字分别为 ，分别相乘。

问题来了，正常乘肯定爆数字范围，取模的话可能会导致某步不整除，怎么办？
提取分子分母
分子为
分母为
此时只要预处理，就能在O(n)时间内计算出分子和分母。

令P=10^9+7，当前问题变为求
运用费马小定理（考场记得个大概，用了一堆例子硬生生试出来的），
因此，当前问题变成
剩下最后一步啦！

数值范围太大了，不能for循环计算
使用快速幂。

代码如下，欢迎参考！
真是我笔试中遇到最难的题了。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

const int Mod = 1000000007;

int n;
unsigned long long F[1000005];

unsigned long long Pow(unsigned long long x, int y) {
    unsigned long long res = 1, a = x;
    for (; y > 0; y >>= 1){
        if (y&1) res = res * a % Mod;
        a = a * a % Mod;
    }
    return res;
}

int main() {
    cin >> n;
    unsigned long long res = 1;
    n--;
    F[0] = 1;
    for (int i = 1; i <= n; ++i) {
        F[i] = F[i - 1] * i % Mod;
    }
    unsigned long long x = 1, y = 1;
    for (int i = 0; i <= n; ++i) {
        x = x * F[n] % Mod;
        y = y * F[i] % Mod * F[n - i] % Mod;
    }
    res = x * Pow(y, Mod - 2) % Mod;

    cout << res;
    return 0;
}

第二题

题目

给定一个表达式，包含数字，和+,-,^三个符号。假定^的优先级比+,-高。
保证符号个数+1 = 数字个数，保证表达式格式正确。求表达式的解。
例如：输入3+5^2-9，输出1。

想法与思路

从右往左，遇到数字累计，遇到符号操作。如果是加减，考虑是否需要先异或。如果是异或，打个标记，记录累计的异或和（异或满***换律和结合律）。
注意，开头的数字得特殊计算，比如4^4+5 = 5（大坑，不注意这个只有50分）

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;

string s;
int n;
long long res;

int main() {
    cin >> s;
    n = s.length();
    long long last = 0, now = 0, p = 1;
    bool flag = 0;
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == '+' || s[i] == '-' || s[i] == '^') {
            if (s[i] == '+') {
                if (flag == 0)
                    res += now;
                else {
                    last ^= now;
                    res += last;
                    flag = 0; last = 0;
                }
            }
            else if (s[i] == '-') {
                if (flag == 0)
                    res -= now;
                else {
                    last ^= now;
                    res -= last;
                    flag = 0; last = 0;
                }
            }
            else if (s[i] == '^') {
                last ^= now;
                flag = 1;
            }
            now = 0; p = 1;
        }
        else {
            now = now + (s[i] - '0') * p;
            p = p * 10;
        }
    }
    if (flag == 1)
        cout << res + (last^now);
    else
        cout << res + now;
    return 0;
}

第三题

题目

递归，求前n项和

想法与思路

这么水的题为什么放第三题。。

代码

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int recursion(int n ) {
    // write code here
    if (n == 0)
        return 0;
    return recursion(n - 1) + n;
}

第四题

题目

机器学习分大端存储和小端存储，给定一个小端数字，求大端。
样例：输入1，输出16777216。

想法与思路

太坑了！考场我根本不知道什么是大端小端，完全忘记了！
从样例开始猜，计算器一通乱试，发现16777216 = 2^24
以为是24位进制反转，试了一下，得了40分。
想来想去，灵光乍现，如果按照8位分割（Byte概念），分成4块，会不会所谓的“大端”和“小端”是块替换。一想觉得非常合理，样例给定2^0，输出2^24，假设0-31位，刚好符合要求。
又写了一通，拿了80分，最后一个点怎么都调不过了，估计概念漏了啥符号位吧。

输出了一通怨念，最后考完想明白了
正解如下：

1. 输入是正数，就按照现在代码中的方法，分成4块算。

2. 输入是负数，使用去掉符号位，使用补码（原码，反码，补码那块转换）计算出对应每一位的0/1状态，类似的计算。

   代码（只拿了80分，没有考虑输入是负数）

   /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param n int整型 
   * @return int整型
   * C语言声明定义全局变量请加上static，防止重复定义
   */
   /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param n int整型 
   * @return int整型
   * C语言声明定义全局变量请加上static，防止重复定义
   */
   int convert(int n) {
    int temp_a[32];
    memset(temp_a, 0, sizeof(temp_a));
   
    for (int i = 0; n > 0; n>>=1, ++i)
        temp_a[i] = n&1;
   
    int p = 1;
    int res = 0;
    for (int i = 24; i < 32; ++i) {
        res = res + p * temp_a[i];
        p *= 2;
    }
    for (int i = 16; i < 24; ++i) {
        res = res + p * temp_a[i];
        p *= 2;
    }
    for (int i = 8; i < 16; ++i) {
        res = res + p * temp_a[i];
        p *= 2;
    }
    for (int i = 0; i < 8; ++i) {
        res = res + p * temp_a[i];
        p *= 2;
    }
   
    return res;
    // write code here
   }

算法题总得分：100+100+100+80 = 380。做过最难的一次秋招笔试了。