字节跳动秋招笔试四道编程题（2021-08-29）

小咪咪 2022-09-09 04:48 234阅读 0赞

> 以下字节笔试编程题代码及思路由@nuoyanli提供，有兴趣的可以去这位[ACM专业打铁选手][ACM]那里找到更多刷题技巧。

### 文章目录 ###

*  第一道：第一题自然数a、b（100%）
 *   *  题目描述
     *  思路
     *  参考代码：
 *  第二道：小明玩游戏（100%）
 *   *  题目描述
     *  思路
     *  参考代码：
 *  第三道： 五子棋（100%）
 *   *  题目描述
     *  思路
     *  参考代码
 *  第四道：扑克牌（100%）
 *   *  题目描述
     *  思路
     *  参考代码

# 第一道：第一题自然数a、b（100%） #

## 题目描述 ##

给定两个自然数a和b，要求对这两个数字做N次操作后，是两个数字的值最终相等。在第i次操作中，选择a或者b对其加i。请计算使a和b相等的最小操作次数。

例如，给定数字a=27和b=20，最少可以进行5步操作后使其相等:

第1步，令b=b+1，此时a为27，b为21  
第2步，令b=b+2此时a为27b为23  
第3步，令b=b+3，此时a为27，b为26  
第4步，令a=a+4，此时a为31,b为26  
第5步，令b=b+5，此时a为31b为31

**输入描述:**  
输入包括t+1行  
第一行是一个正数t(1<=t<=100)，表示下面有t组数据  
接下来有t行，每行包括两个整数a和b(1<=a,b<=10^9)

3
    1 311 1127 20

**输出描述:**  
输出包括t行  
针对每组数据，输出一个整数，为使a和b相等的最小操作次数。

30
    5

## 思路 ##

第 1 次加法加 1，第二次加 2，那么到第 i 次，前面所有的总共加了 1.2.3…i，即 i 的等差数列。如果想要让 a 和 b 相等，首先这个等差数列之和的大小要大于 a 和 b 的差值（否则就算全部加到小的那个数字上，小的数字也无法等于大的数字）。当然，并不是所有情况都是这样，比如 1 和 3，把 1 加到 3 和 3 相等，显然不可能。如果此时还想让 a b 相同，需要满足的条件就是多加的部分是个偶数，这样才能平均分配。例如把 1 和 3 最终加成了 5 和 5 而不是 3 和 3，那么多加的部分就是 4，这个 4 被分成了 2 份 2，平均分给了两个数字。  
综上：两个条件就是等差数列求和大于原本的差值，且和原本的差值多出来的部分是偶数。那么我们先算出满足第一个条件的 i 最小是多少，如果此时满足不了第二个条件，则不停进行 i++ 操作(源代码中是变量 now)，直到满足第二个条件为止。可以证明，最多进行 4 次 i++ 操作就可以使得其一定满足第二个条件。

## 参考代码： ##

//二分答案，对于1~n是可以凑出来任意数字的，保证这些数字和大于两数差值abs(a-b)，并且数字和减去abs(a-b)的差需要是偶数即可。
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    int main() { 
        int T; cin >> T;
        while(T--) { 
            LL a, b; cin >> a >> b;
            LL k = abs(a - b);
            LL l = -1, r = 1e5;
            while(l + 1 < r) { 
                LL mid = l + r >> 1;
                if(mid*(mid+1)/2 <= k) { 
                    l = mid;
                } else { 
                    r = mid;
                }
            }
            while(l*(l+1)/2 < k || (l*(l+1)/2-k)&1) ++l;
            cout << l << endl;
        }
        return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

方法二：

#include <bits/stdc++.h>
    using namespace std;
    int main() { 
      int t;
      cin >> t;
      while (t--) { 
        int a, b;
        cin >> a >> b;
        int cha = abs(b - a);
        int now = sqrt(cha * 2);
        while (true) { 
          if (now * (now + 1) / 2 >= cha && (now * (now + 1) / 2 - cha) % 2 == 0)
            break;
          now++;
        }
        cout << now << endl;
      }
    }

# 第二道：小明玩游戏（100%） #

## 题目描述 ##

例如，给定数字a=27和b=20，最少可以进行5步操作后使其相等:

**输入描述:**  
输入包括t+1行  
第一行是一个正数t(1<=t<=100)，表示下面有t组数据  
接下来有t行，每行包括两个整数a和b(1<=a,b<=10^9)

3
    1 311 1127 20

**输出描述:**  
输出包括t行  
针对每组数据，输出一个整数，为使a和b相等的最小操作次数。

30
    5

## 思路 ##

由于每天的进步都是正数，所以我们可以先进行一个前缀和，算出每一天的三个属性分别是多少。对于每一个技能，如果第  i i i 天的属性足以学习这个技能，那么  i + 1 i+1 i\+1 天肯定也可以学习（因为  i + 1 i+1 i\+1 天的属性肯定比  i i i 高）；同理，如果第  i i i 天的属性学习不了这个技能，那么 i − 1 i-1 i−1 天肯定也学习不了。  
满足单调的条件之后，我们采用二分法来判断结果即可。

## 参考代码： ##

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e5 + 5;
    struct node { 
      int a, b, c;
    };
    node grow[maxn], pre[maxn];
    int main() { 
      int n, m, a, b, c;
      cin >> n >> m;
      for (int i = 1; i <= n; i++) { 
        cin >> a >> b >> c;
        pre[i].a = pre[i - 1].a + a;
        pre[i].b = pre[i - 1].b + b;
        pre[i].c = pre[i - 1].c + c;
      }
      for (int i = 1; i <= m; i++) { 
        cin >> a >> b >> c;
        int l = 1, r = n, ans = -1;
        while (l <= r) { 
          int mid = (l + r) / 2;
          if (pre[mid].a >= a && pre[mid].b >= b && pre[mid].c >= c) { 
            ans = mid;
            r = mid - 1;
          } else
            l = mid + 1;
        }
        cout << ans << " ";
      }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道： 五子棋（100%） #

## 题目描述 ##

假设存在一个五子棋棋盘，大小未知。上面只摆放了一些白色的棋子，现在你的手中还有1个白色棋子，要求找出在棋盘的哪些位置摆放这个棋子，能够使棋盘上出现五颗棋子连成线。

备注:棋盘上当前不存在连成一条线的五个棋子，但至少存在一个点能够凑出五子一线(不限于横、竖、斜线)。本题用例中不存在放置一子后出现六子一线的情况。

**输入描述:**  
第一行输入一个正整数n，表示棋盘的宽度，棋盘总共可以容纳n^2个棋子。  
第2到n+1行输入n个数字。每次输入n个数，其中1代表有棋子，0代表没有棋  
子

**输出描述:**  
如果有n个可放置点，输出n行  
每行输出两个数字，以空格分隔，分别代表放置点在棋盘上的行数和列数输出顺序需要按照行数从小到大、列数从小到大的顺序。

## 思路 ##

由于数据范围很小，可以枚举每一个位置是否下棋，然后对整个棋盘进行  c h e c k check check，来判断此时棋盘是否有连成五子的情况。具体  c h e c k check check 的方式就是枚举棋盘的每一个位置，从这个位置向八个方向延伸  5 5 5 位，如果一直是  a \[ i \] \[ j \] = 1 a\[i\]\[j\]=1 a\[i\]\[j\]=1，说明这五个位置都有棋，即连成五子。只要有某一个位置的某一个方向能够连成五子，则说明此时的棋盘中有连成五子的情况，即  c h e c k check check 成功，在这个位置下棋可以获胜。

## 参考代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    int a[11][11], n;
    bool check() { 
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) { 
          bool flag1 = true, flag2 = true, flag3 = true, flag4 = true;
          bool flag5 = true, flag6 = true, flag7 = true, flag8 = true;
          for (int k = 0; k <= 4; k++) { 
            if (j + k > n || a[i][j + k] == 0)
              flag1 = false;
            if (j - k < 1 || a[i][j - k] == 0)
              flag2 = false;
            if (i + k > n || a[i + k][j] == 0)
              flag3 = false;
            if (i - k < 1 || a[i - k][j] == 0)
              flag4 = false;
            if (i + k > n || j + k > n || a[i + k][j + k] == 0)
              flag5 = false;
            if (i + k > n || j - k < 1 || a[i + k][j - k] == 0)
              flag6 = false;
            if (i - k < 1 || j + k > n || a[i - k][j + k] == 0)
              flag7 = false;
            if (i - k < 1 || j - k < 1 || a[i - k][j - k] == 0)
              flag8 = false;
          }
          if (flag1 || flag2 || flag3 || flag4 || flag5 || flag6 || flag7 || flag8)
            return true;
        }
      return false;
    }
    int main() { 
      cin >> n;
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
          cin >> a[i][j];
      for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) { 
          if (a[i][j] != 0)
            continue;
          a[i][j] = 1;
          if (check())
            cout << i << " " << j << endl;
          a[i][j] = 0;
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第四道：扑克牌（100%） #

## 题目描述 ##

在一次游戏中，小明的扑克牌中的红桃J和梅花Q找不到了，为了利用剩下的牌做游戏，小明设计了新的游戏规则：

1.  A 2 3 4 5 6 7 8 9 10 J Q K分别为一至十三点，大王和小王为0点
2.  游戏人数为2人，双方轮流从牌堆顶摸牌，每次摸牌后可以选择保留当前牌或者使用当前牌
3.  3使用当前牌后的三回合内可以获得当前牌三倍的点数(例:如果第一回合使用了黑桃10，那么在第一到第三回合结算时黑桃10可以提供30点，第四回合失效)
4.  保留的手牌结算时可以获得一倍的点数(例:如果第一回合保留了10，那么在每回合结算时+10都可以提供10点)
5.  只能使用当前摸到的手牌，不能使用之前保留的手牌
6.  每回合结算时点数大的一方获胜

假设你知道牌堆中每张牌的点数以及对家每回合的选择，请判断你能否保持全胜，如果可以，请输出最后一回合结束结算时你的点数最大为多少

**输入描述**:

输入分为两行，每行 N个数字，空格作为分隔  
第一行为你通过计算得到的对方每回合结算时的点数第二行为你每回合摸到的牌的点数

**输出描述:**  
如果不能保持全胜，输出-1，否则输出最后一回合结算时的最大点数

**示例**

输入： 10 16 31 39 47 41 43 61 61 61 49 44 45 84 117 120 93 70 78 79 106112 119 96 101 122
    01278139711410519112122592131131102
    输出：-1
    说明：第一回合无论使用手牌与否都无法超过对手的点数

## 思路 ##

由于数据范围只有  26 26 26，枚举每一张牌是保留还是使用的两种情况，在  2 26 2^\{26\} 226 的时间内就可以算出结果。我们可以用递归进行枚举

## 参考代码 ##

#include <bits/stdc++.h>
    using namespace std;
    
    int n = 26, ans = -1;
    int a[27], b[27];
    void dfs(int dep, int now, int pre1, int pre2) { 
      if (dep == n) { 
        int sum = now + pre1 + pre2 + 3 * a[dep];
        if (sum > b[dep])
          ans = max(ans, sum);
        return;
      }
      if (a[dep] + now + pre1 + pre2 > b[dep])
        dfs(dep + 1, now + a[dep], 0, pre1);
      if (3 * a[dep] + now + pre1 + pre2 > b[dep])
        dfs(dep + 1, now, 3 * a[dep], pre1);
    }
    int main() { 
      for (int i = 1; i <= n; i++)
        cin >> b[i];
      for (int i = 1; i <= n; i++)
        cin >> a[i];
      dfs(1, 0, 0, 0);
      cout << ans << endl;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

> 恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。

[ACM]: https://nuoyanli.blog.csdn.net/article/details/119979350