字节秋季笔试四道编程题（2021-09-12）

傷城~ 2022-09-11 04:27 239阅读 0赞

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

【2021-09-04】美团秋招笔试五道编程题（附题目）  
【2021-09-03】贝壳秋招笔试四道编程题（前三道ac）  
【2021-09-01】阿里巴巴秋招笔试两道编程题  
【2021-09-01】华为秋招机试三道编程题（附题目，后两题AC）  
【2021-08-29】美团秋招笔试四道编程题  
【2021-08-29】字节跳动秋招笔试四道编程题  
【2021-08-26】腾讯音乐秋招笔试编程三道题  
【2021-08-25】华为秋招机试三道编程题  
【2021-08-23】阿里巴巴秋招笔试两道编程题  
【2021-08-22】腾讯秋招笔试五道编程题  
【2021-08-22】美团秋招笔试五道编程题（待更新）  
【2021-08-21】网易秋招机试四道编程题（待更新）  
【2021-08-14】荣耀秋招机试三道编程题（已更新）  
【2021-08-18】华为秋招机试三道编程题（已更新）  
【2021-08-18】阿里秋招笔试两道编程题  
【2021-08-15】美团秋招笔试五道编程题（已更新）  
【2021-08-12】携程秋招笔试三道编程题  
【2021-08-11】华为秋招机试三道编程题(已更新)  
【2021-08-09】阿里巴巴秋招笔试两道编程题  
【2021-08-08】拼多多秋招笔试四道编程题  
【2021-08-08】美团秋招笔试五道编程题  
【2021-08-08】好未来秋招三道编程题  
【2021-08-07】网易互娱秋招笔试三道编程题  
【2021-08-04】华为秋招两道编程题

### 文章目录 ###

*  第一道：小M的多任务下载器
 *   *  题目描述
     *  参考代码
 *  第二道：寻找对称的二叉树特定节点（100%）
 *   *  题目描述
     *  参考代码：
 *  第三道：进攻防御（100%）
 *   *  题目描述
     *  参考代码
     *   *  CPP版本
 *  第四道：数组游戏（100%）
 *   *  题目描述
     *  参考代码
     *   *  CPP版本

# 第一道：小M的多任务下载器 #

## 题目描述 ##

小M的程序设计大作业是编写一个多任务下载器，在做到计算任务并发数的时候遇到了困难。

在一次下载中，总共包含N个任务，每个任务会在第x秒开始、并持续y秒。小M想要知道，在一次下载中，同时最多会有多少个任务正在下载。

**输入描述**  
第一行输入一个正整数N，代表总共有N个任务  
之后共N行，每行包含两个正整数x、y，x代表任务开始的时间，y代表任务的持续时间。

2
    1 2
    2 3

**输出描述**  
输出包含一个整数，代表最高的任务并发数

**解释**  
第一个任务在第一秒开始，持续两秒;第二个任务在第二秒开始，持续三秒。故在第二秒时有两个任务同时在进行，最大并发数为2。

## 参考代码 ##

可以参考力扣会议室II

bool cmp(pair<int,int> const&a, pair<int, int> const& b) { 
     return a.first < b.first || a.first == b.first && a.second < b.second;
    }
    int main()
    { 
     int n;
     cin >> n;
     vector<pair<int, int>> f;
     f.reserve(2 * n);
     for (int i = 0; i < n; i++) { 
      int x, y;
      scanf_s("%d%d", &x, &y);
      
      f.emplace_back(x, 1);
      f.emplace_back(x+y, -1);
     }
     sort(f.begin(), f.end(), cmp);
     int res = 0;
     int m = 0;
     for (auto const& i : f) { 
      m += i.second;
      res = max(res, m);
     }
     cout << res << endl;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道：寻找对称的二叉树特定节点（100%） #

## 题目描述 ##

给定一颗二叉树，二叉树每个节点都有一个唯一的整数值代表节点，在遍历时，我们使用节点的整数值作为标记;结构对称，是指二叉树从根节点往下看，左右翻转一下，能够重合(不考虑节点内容比较，仅仅是结构)，我们就称这棵二又树树结构对称

输入:二叉树的节点个数N(0<N<60000)、前序和中序遍历结果，分别是第一行、第二行与第三行;各个节点整数值在1到60000之间  
。

输出:判断这棵二叉树是否结构对称，若对称请输出最大值节点在树中对称节点的整数值，不对称请直接输出最大值节点的整数值

**输入描述**  
二叉树的前序和中序 遍历结果，以数组序列表示  
第一行为节点个数N(0<N<60000)前序和中序 遍历结果，输入分别是第二行与第三行

3 
    1 3 4
    3 1 4

**输出描述**  
判断这棵二叉树是否结构对称，若对称请输出最大值节点在树中对称节点的整数值，不对称请直接输出最大值节点的整数值

**解释**  
这颗二叉树根是1，左右子节点分别是3和4，是结构对称的，4是最大值节点，其对称节点是3，所以最后输出为3

## 参考代码： ##

import java.util.*;
    
    public class zj_2021_02 { 
        static HashMap<Integer, Integer> inorder_idx;
        static int[] preorder;
        static int[] inorder;
        static int[] inorder_height;
        static int max_idx = 0;
        static int n;
        static boolean flag = true;
    
        public static void isMirror (int preorder_left, int preorder_right, int inorder_left, int inorder_right, int height) { 
            if (preorder_left > preorder_right || inorder_left > inorder_right) { 
                return;
            }
            int inorder_root = inorder_idx.get(preorder[preorder_left]);
            inorder_height[inorder_root] = height;
            int other_height = inorder_height[n - 1 - inorder_root];
            if (!flag || (other_height != 0 && other_height != height)) { 
                flag = false;
                return;
            }
            int left_size = inorder_root - inorder_left;
            isMirror(preorder_left + 1, preorder_left + left_size, inorder_left, inorder_root - 1, height + 1);
            isMirror(preorder_left + left_size + 1, preorder_right, inorder_root + 1, inorder_right, height + 1);
        }
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt();
            preorder = new int[n];
            inorder = new int[n];
            inorder_height = new int[n];
            for (int i = 0; i < n; i++) { 
                preorder[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++) { 
                inorder[i] = sc.nextInt();
                max_idx = inorder[i] > inorder[max_idx] ? i : max_idx;
            }
            inorder_idx = new HashMap<Integer, Integer>();
            for (int i = 0; i < inorder.length; i++) { 
                inorder_idx.put(inorder[i], i);
            }
            isMirror(0, n - 1, 0, n - 1, 0);
            System.out.println(flag ? inorder[n - 1- max_idx] : inorder[max_idx]);
        }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：进攻防御（100%） #

## 题目描述 ##

一个数组ai表示防御值，一个数组bi表示进攻值，ai的乘积能被bi的乘积整除，输出yes，反之输出no。

思路就是质因数分解， 一个数大于另一个数 那么这个数的质因数分解的幂大于等于另一个数质因数分解的幂

## 参考代码 ##

### CPP版本 ###

public boolean f3(int[] a, int[] b) { 
    	//题目给的不算大，可以用数组，数组放不下可以用 Map 
    	int[] s = new int[100000]; 
    	for(int t : a) { 
    	for(int i= 2; i<= t; i++){ 
    		while(t % i == 0){ 
    			s[i]++; 
    			t/=i;
    		}
    		if(t > 1) s[t]++;
    	}
    }
    for(int t : b) { 
    	for(int i= 2;i <= t; i++) { 
    		while(t % i ==0){ 
    			s[i]--;
    			if(s[i] < 0 peturn false; 
    			t/=i;
    		}
    		if(t>1){ 
    		s[t]--;
    		if(s[t]< 0) return false;
    	}
    	return true;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第四道：数组游戏（100%） #

## 题目描述 ##

双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。

凯凯在小黑板上写下一串有正有负的数列，猫咪从左到右，每碰到一个数，可以选择选取或者不选取。在选取过程中，要保证所有选取的数的和始终为非负。在这个限制条件下求最多可以选取多少个数。小猫咪表示“我太难了”

你能帮帮它么?

**输入描述**  
会有多组询问  
首先输入一个数字t(1<=t<=10)接下来有t组数据  
每组数据里，首先会有一个数n，表示接下来这个数列的长度为n  
然后接下来一行会有n个数字，从左到右表示题目所说的数列。

2
    6
    4 -4 1 -3 1 -3
    5
    1 2 3 4 5

**输出描述**  
对于每一个提问，请依次输出正确的答案

5
    5

**解释**  
第一组数据:选取第1，3，4，5，6个数第二组数据:因为全部是正数，所以全取。

## 参考代码 ##

### CPP版本 ###

#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <queue>
    using namespace std;
    // 4 -4 1 -3 1 -3
    
    int f(vector<int>&nums) { 
        int sum = 0;
        int ans = 0;
        queue<int> que;
        for (int z : nums) { 
            if (sum + z >= 0) { 
                ans++;
                sum += z;
                if (z < 0) que.push(z);
            }
            else { 
                if (!que.empty() && z > que.front()){ 
                    sum -= que.front();
                    sum += z;
                    que.pop();
                    que.push(z);
                }
            }
        }
        return ans;
    }
    
    int main()
    { 
        int t;
        cin >> t;
        vector<int> vec;
        vector<vector<int>> vvint;
        while (t--)
        { 
            int n;
            cin >> n;
            while (n--)
            { 
                int k;
                cin >> k;
                vec.push_back(k);
            }
            vvint.push_back(vec);
    
            vec.clear();
        }
    
        for (int i = 0; i < vvint.size(); i++) { 
            cout << f(vvint[i]) << endl;
        }
        return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

> 关注TechGuide，大厂笔经面经闪电速递！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/1419a6faf16a4832bdd864c67d748444.png