腾讯音乐笔试2022-4-7场

总共3道编程题和一道场景题，总的来说，编程题后两题水题，第一题是组合数学，也有可能是动态规划。

1. k-size字符串的数量（组合数学）

给定字符串总数n，组数 K：

先求出放入 $2 * k$ 个字符的数量，也就是说第一位是AA那么第二组只能是BB,CC.........ZZ，以此往后每一组也是25种情况。也就是 $first = 26 * 25 * 25 * ..... * 25 % mod$ （总共 k个），
然后我们剩下 $last = n-2*k$ 个字符，那么我们需要last个字符分为K组的总情况，将分组好的数据去插入步骤一的相应位置，计算出分组结果为second种情况，这个操作类似n个小球放入m个箱子里面的总情况数量 $C_{m+n-1}^{m-1}$ （允许空箱子的存在）。然后结果就是 $second * first % mod$ ;

由于计算组合数的时候有些问题（中间结果会溢出long，需要使用逆元等方式来解决），计算second的时候出现失误只对了60%，以上是我的理解，如有失误，还请各位大佬斧正。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型
     */
    ll c[1001][1001];
    void init(){
        int mod = 1e6;

        for(int i = 0; i < 1001; i++){
            for(int j = 0; j < 1001; j++){

                if(not j) c[i][j] = 1;
                else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
            }
        }
    }
    int numsOfStrings(int n, int k) {
        ll ans = 0;
        int mod = 1e6;
        init();
        if(k == 1) return 26;
        for(int i = 0; i < k; i++){
            if(i == 0) ans = 26;
            else ans = ans * 25 % mod;
        }
        int last = n - 2 * k;
        //可能有些问题.....
        if(last != 0) ans = ans * c[last+k-1][k-1] % mod;
        else return ans;
    }
};
int main(){
    Solution s = Solution();

    cout << s.numsOfStrings(6,2);
    // s.minMax();
}

2. 计算最后最大值（贪心）

贪心，维护一个大顶堆，每次取出最大值减去x重新放入堆中即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @param x int整型 
     * @return int整型
     */
    int minMax(vector<int>& a, int k, int x) {
        priority_queue<int> q;
        for(auto num : a) q.push(num);
        while(k--){
            int maxx = q.top();
            cout << maxx << endl;
            q.pop();
            q.push(maxx - x);
        }
        return q.top();
        // write code here
    }
};

3.幂的删除多少（构造）

啊这？好水呀。不会真的有人不知道只有一个1才是2的幂吧…

int minCnt(string s) {
        int cnt = 0;
        for(auto ch : s) if(ch == '1') cnt++;
        return cnt-1;
}

4.大文件传输

需求：大文件，确保效率和可靠性
解决方法：断点续传，分片传输，并行传输。这里类比了下载工具IDM的强大功能。

文件先要压缩呀，一般图片用webp格式啥的，就选个效率好的压缩算法先压缩一下，就可以压缩60%左右了（视文件类型决定）。
具体做法是先进行信息传输（文件名，文件大小，双方带宽，预计时间），客户端可以开多个线程并发去请求每个小文件，每个线程offset起始位置和该片段大小。
然后服务端要提升IO效率了，比如说IO多路复用之类的，或者带宽不够，集群来凑，一定要把带宽提上去，而且要跑满。
可靠性，尽量不使用TCP，因为受MTU限制，单次传输的有效数据大小比UDP小，同时为了保证可靠性，可以上QUIC协议啊之类的，或者我们在应用层去做一个可靠性，对于每个请求维护分别维护offset来实现。
如果够壕，那么直接提升硬件！磁盘升固态硬盘呗，磁盘IO提上来了，或者多搞几台服务器
最后注意，传输速率的因素是个水桶效应，不能仅仅提升某一个阶段，应该雨露均沾。比如说不能单单提供网络IO带宽，磁盘读速率提不上来等于白忙活了。
想到了类似迅雷那种，种子传输！老司机都懂的，不需要去访问服务器，而是互相从各个存有资源的客户端下载！（拼友越多，车更快！别说了，快上车！）