字节跳动笔试题

  昨天字节跳动笔试题目，没有ac一道，我很受打击。打算以后每笔试或面试一次，都仔细钻研，记录下自己的收获。也欢迎朋友们指出我写博客中的错误或给出更简单的方法。

1.田忌赛马问题

  两个小组A、B，每个小组有n个同学。已知每位同学的速度。两个小组进行赛跑获取积分，每次派出一名同学，胜者+1，败者-1，平局+0。问A组最多积多少分。输入n代表n名同学，在输入n个数代表A组每人速度，又n个数代表B组每人速度。

输入样例：
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
输出样例：
1
0
0

  这道题一开始搞错了策略，在这个题上花费了不少时间也才过了50多的用例。后来听说是田忌赛马问题，看了看其他人的博客后发现正解思路应该是这样：
  先给两组数据排序。
  （1）A组最快>B组最快：让他俩比赛，A组积分+1
  （2）A组最快<B组最快：让A组最慢与B组最快比，积分-1
  （3）A组最快=B组最快：再分类讨论：
    （a）A组最慢>B组最慢：他俩比赛,积分+1
    （b）其他情况：A组最慢与B最快比，
      （b1）A最慢=B最快：他俩比，积分不变
      （b2）A最慢<B最快，他俩比，积分-1

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;//比赛数 
    vector<int> a(n,0);//a组速度 
    vector<int> b(n,0);//b组速度 
    for(int i=0;i<n;i++){
        cin>>a[i];
    } 
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    
    int res = 0;
    int ab = 0,bb = 0, ae = n-1, be = n-1;
    while( ae>=ab && be>=bb ){
        if(a[ae]>a[be]){ // >
            res++;
            ae--;
            be--;
        } else if(a[ae]<a[be]){  //< 
            res--;
            ab++;
            be--;
        } else {  //=
            if(a[ab]>b[bb]){
                res++;
                ab++;
                bb++;           
            } else{
                if(a[ab]<b[be]){
                res--；
                } 
                ab++;
                be--;   
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
} 

2.取扑克牌问题

  n张卡牌堆成一堆，每张卡牌上都有一个整数代表该牌得分。两人A,B交替从牌堆顶拿牌。第一次可以拿1~2张牌，后面每次拿牌，最多拿上个人拿牌数的两倍，最少拿1张，直到牌全部拿完。假设两个人都会采取最优策略让自己得分最大化，求先手拿牌人的得分。
  
  这是一个动态规划问题，我们可以用一个二维数组f[i][j]，表示从第i个位置开始拿，拿1~ j+1张牌，最大得分是多少。
  设有n张卡牌存放在数组a[n]，建立二维数组f[n+1][n]
  建立辅助数组sum[n],sum[i]表示a[n-1]累加至a[i]的和。
  f[n][j]=0,j=0,1,...,n-1。表示在数组第n个位置拿不到牌。
f[i][j] = max(j=0,1,...,n-i-1 min(sum[i]-f[i+j+1][k] ,k=0,1,...,min(n-i-j-1,j2+1)) )
  min表达式含义：假设A从i位置开始取了j+1张牌，B则从i+j+1位置开始挑选k+1张牌,k=0,1...,min(n-1-i-j,j2+1)，用sum[i]-f[i+j+1][k]即A的得分。由于B会采取最佳策略，所以A得分会是最少的情况。
  max表达式含义：已计算出A从i位置取j+1张牌的积分，j=0,...,n-i-1。那A选择得分最多的情况。

#include<iostream>
#include<vector>
using namespace std;
int main(){
    //输入卡牌数量及卡牌分数 
    int n;
    cin>>n;
    vector<int> a(n,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    
    //计算sum[i]辅助数组 
    vector<int> sum(n+1,0);
    for(int i=n-1;i>=0;i--){
        sum[i]=sum[i+1]+a[i];       
    }
    
    vector<int> temp(n,0);
    vector<vector<int> > f(n+1,temp);                                                                                     
  //递推式 
    for(int i=n-1;i>=0;i--){//从第i个位置开始取 
        int t1=INT_MIN; 
        for(int j=0;i+j+1<=n;j++){ //从第i个位置取j+1个 ，直到取不到 
            int t2 = INT_MAX;     
            for(int k=0;k<2*(j+1) && i+j+1+k<=n;k++){//另一方从第i+j+1位置取k+1个 
                int t3 = sum[i]-f[i+j+1][k];
                t2 = min(t2,t3); 
            }
            t1 = max(t1,t2);
            f[i][j]=t1; 
        } 
    }   
    
    cout<<f[0][1]<<endl; 
    return 0;
} 

自己就写了两个测试用例
1.输入4，1，1，1，1  输出2
2.输入5，3，-4，1，1，7  输出5

3.坐圆桌问题

  n个人围着圆桌吃饭，要求每相邻两个人的身高差距不能超过m，有多少种安排方法。输入n和m,n=1,...,10,m=1,...,1000000。后面n行输入代表每个人的身高。
  笔试那会一看就没思路，所以就放弃了。后来问了一同参加笔试的校友，发现题目好像没那么难。询问校友后思路如下：先固定第一人位置；然后依次寻找后面的人能否放在第二个位置上，如果有人能放在这个位置上，递归寻找放在第三个位置上的人，直到找到最后一个位置上的人，如果该人满足放置条件，则增加一种安排方法。如果后面的人不能放在某个位置上，再寻找后面的人。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void bt(vector<int>& p,int c,int n,int &res,int m){
    if(c==n-1){
         if(abs(p[c]-p[c-1])<=m && abs(p[0]-p[c])<=m){ //判断最后一个位置的人加入进来是否满足情况 
            res++;
         }
         return;
    }
    for(int i=c;i<n;i++){
        swap(p[i],p[c]);
        if(abs(p[c]-p[c-1])<=m){ //i位置上的人可以放在c位置上
            bt(p,c+1,n,res,m);
        }
        swap(p[i],p[c]);
    }   
}
int main(){
    int n;//人数
    int m;//身高差限制
    cin>>n>>m;
    vector<int> h(n,0);//身高
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    if(n==1){//一个人的情况 
        return 1;
    }
    int res=0;
    bt(h,1,n,res,m);
    cout<<res<<endl;
    return 0;
}

自己也写了几个简单的测试用例
1.输入7，100，1，2，3，4，5，6，7  输出720
2.输入4，2，1，2，3，4  输出2
3.输入4，1，5，6，7，8  输出0

4.01背包问题

  这个应该是最不应该做不出来的，因为题目就是课本上01背包原题。可惜被测试用例的数据范围给吓到了。
  f[i][j]表示背包容量为i，放前j个物品的最大价值。构建数组f[n+1][m+1]。v[j]表示第j-1个物品的价值，a[j]表示第j-1个物品的质量。
  f[0][j]=0,j=0,1,...,n-1，f[i][0]=0,i=0,1,...,n-1
  i>=a[j-1]时，f[i][j] = max(f[i-a[j-1]][j-1]+v[j-1],f[i][j-1])
  i<a[j-1]时，f[i][j] = f[i][j-1]

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;//背包容量,物品个数
    cin>>n>>m;
    vector<int> a(m,0); //物品质量 
    vector<int> v(m,0);//物品价值 
    for(int i=0;i<m;i++){
        cin>>a[i]>>v[i];
    }
    vector<int> temp(m+1,0);
    vector<vector<int> > f(n+1,temp);
        
    for(int i=1;i<=n;i++){//质量为i时 
        for(int j=1;j<=m;j++){ //装前j个物品 
            if(i>=a[j-1]){
                f[i][j] = max(f[i-a[j-1]][j-1]+v[j-1],f[i][j-1]);
            } else {
                f[i][j] = f[i][j-1];
            }
        }
    }
    cout<<f[n][m]<<endl; 
} 

  测试用例：容量为5，3个物品，每个物品的质量与价值依次为：2、3；3、4；4、5。输出最大价值为7。
  下图为优化空间输出后的代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;//背包容量,物品个数 
    cin>>n>>m;
    vector<int> a(m,0); //物品质量 
    vector<int> v(m,0);//物品价值 
    for(int i=0;i<m;i++){
        cin>>a[i]>>v[i];
    }
    vector<int> temp(2,0);
    vector<vector<int> > f(n+1,temp);
    
    for(int j=1;j<=m;j++){//装前j个物品时 
        for(int i=1;i<=n;i++){ //背包容量为i时 
            if(i>=a[j-1]){
                f[i][1] = max(f[i-a[j-1]][0]+v[j-1],f[i][0]);
            } else {
                f[i][1] = f[i][0];
            }
        }
        for(int i=1;i<=n;i++){
            f[i][0]=f[i][1];
        }
    }
    cout<<f[n][1]<<endl; 
}