2020.08.16 字节跳动第二场笔试（包含124题代码）

因为字节跳动的笔试不能本地IDE编辑，所以考完试后，凭着记忆再写一下代码，如有笔误，希望大佬们可以指正！谢谢！

【第一题】一棵二叉树，每个节点都有唯一的正整数值代表节点，在遍历时，我们使用节点的整数值作为标记，求二叉树叶子节点个数。

输入：第一行为二叉树节点个数。第二行和第三行分别为前序和中序遍历结果

输出：二叉树叶子节点个数

思路：直接按照建树的方式（不用建树），搜索到只有一个节点的时候累加叶子节点数量

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 30005;
int pre[maxn];
int mid[maxn];

void dfs(int prel, int prer, int midl, int midr, int& ans) {
    if(prel > prer) return;
    if(prel == prer) {++ans; return;}

    int root = pre[prel];
    int index = midl - 1;
    for(int i = midl; i <= midr; ++i) {
        if(mid[i] == root) {index = i; break;}
    }

    int lnum = index - midl;
    int rnum = midr - index;
    dfs(prel + 1, prel + lnum, midl, index - 1, ans);
    dfs(prel + lnum + 1, prer, index + 1, midr, ans);
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("a.txt", "r", stdin);
#endif
    //faster_cin_cout;

    int n;
    while(cin >> n) {
        for(int i = 1; i <= n; ++i) cin >> pre[i];
        for(int i = 1; i <= n; ++i) cin >> mid[i];
        int ans = 0;
        dfs(1, n, 1, n, ans);
        cout << ans << endl;
    }
    
    return 0;
}

【第二题】编码协议：给出一个十六进制数组成的字符串，问最少去掉几个字符，使得剩下的字符串不存在‘0010’

输入：t(样例数）

接下来依次出入t个字符串s

输出：每个字符串对应的最少去掉字符数

思路：查找下有几个“0010”就是答案了，细节：下一次查找的时候，需要从1的下一个0开始查找

代码：

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("b.txt", "r", stdin);
#endif
    //faster_cin_cout;

    int n;
    string s;
    string p = "0010";
    while(cin >> s) {
        int cnt = 0;
        size_t found = s.find(p, 0);
        while(found != string::npos) {
            ++cnt;
            found += 3;
            if(found >= s.size()) break;
            found = s.find(p, found);
        }
        cout << cnt << endl;
    }
    return 0;
}

【第三题】N个视频，每个视频时长为L_i秒，在其中插M个广告。一个视频里两个广告必须间隔一段时间（间隔时间可以为0），间隔时长为整数。

帮忙计算间隔时间最大可设置多少秒，如不能插入M条广告，输出0。

ps:考试过程中补充：可无限插入广告

输入：N，M

第二行输入N个整数L_i

输出：最大间隔

暂时没有好的思路，希望路过的大佬们都可以留下你们的解法！

【第四题】寻觅：在n个正整数中，任意挑选k个（不可重复挑选，0 <= k <= n）,数字和记为sum。另有一个正整数m，请问sum % m最大是多少？

输入：n,m

第二行输入n个正整数

输出：sum % m的最大值

思路：考虑到n = 35，而且m很大，所以简单的01背包肯定不能直接用，因为背包容量太大了。可以分成两半进行搜索，然后找<m的最大值即可；

代码：

#include<bits/stdc++.h>
using namespace std;

int a[40];
void dfs(int left, int right, int sum, set<int>& s) {
    if(left > right) return;
    s.insert(sum);
    dfs(left + 1, right, sum + a[left], s);
    dfs(left + 1, right, sum, s);
}

int main(void)
{
#ifndef ONLINE_JUDGE
    freopen("d.txt", "r", stdin);
#endif
    //faster_cin_cout;

    int n, m;
    while(cin >> n >> m) {
        for(int i = 1; i <= n; ++i) cin >> a[i];

        set<int> left;
        set<int> right;
        dfs(1, n/2, 0, left);
        dfs(n/2+1, n, 0, right);
        vector<int> rights(right.begin(), right.end());

        int ans = 0;
        for(int l : left) {
            auto r = lower_bound(rights.begin(), rights.end(), m - l);
            if(r == rights.end()) {
                ans = max(ans, rights.back() + l);
            } else if(r != rights.begin()) {
                r--;
                ans = max(ans, *r + l);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

#笔试题目##字节跳动#