首页 > 2020.08.16 字节跳动第二场笔试(包含124题代码)
头像
joshua0509
编辑于 2020-08-17 11:52
+ 关注

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;
}


全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐