首页 > 字节跳动 Byte camp 2020 第二轮 笔试题 题解
头像
牛客92569745号
编辑于 2020-08-01 12:34
+ 关注

字节跳动 Byte camp 2020 第二轮 笔试题 题解


## T1 Easy
直接双指针一下,判断一下即可
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;
string input;

bool validNumber(const string& str, int i, int j) {
    for (int k = i; k <= j; k++) {
        if (!(str[k] >= '0' && str[k] <= '9')) return false;
    }
    return true;
}

bool validDate(int y, int m, int d) {
    const bool isRunnian = (y == 2004 || y == 2008 || y == 2012 || y == 2016 || y == 2020);
    int months[] = {0, 31, isRunnian?29:28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    return d >= 1 && d <= months[m];
}

int main() {
    cin >> input;
    unordered_map<string, int> validmap;
    for (int l = 0, r = 9; r < input.size(); l++, r++) {
        string cur = input.substr(l, 10);

        if (cur[2] == cur[5] && cur[2] == '-' &&
        validNumber(cur, 0, 1) && validNumber(cur, 3, 4) && validNumber(cur, 6, 9)) {
            int d = stoi(cur.substr(0, 2));
            int m = stoi(cur.substr(3, 2));
            int y = stoi(cur.substr(6, 4));

            if (y < 2001 || y > 2020) continue;
            if (m <= 0 || m >= 13) continue;
            if (!validDate(y, m, d)) continue;

            validmap[cur]++;
        }
    }

    string answer;
    int mx = 0;
    for (auto& p : validmap) {
        if (p.second > mx) {
            mx = p.second;
            answer = p.first;
        }
    }

    cout << answer << endl;
    return 0;
}



## T2 Medium
IPv4 最长前缀匹配原则,ipv4字符串手写一个转化为 `uint32_t` 的函数,手写一个 `ipv4 cidr` 解析器。然后位运算、用一个哈希维护即可
  
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<int, int> ips[35];

pair<uint32_t, uint32_t> parseip(const string& ip) {
    uint32_t answer = 0, seg = 31;
    uint32_t cur_ips[4] = {0};
    string tmp;
    int ids = 0, have_seg = 0;

    for (int i = 0; i < ip.size(); i++) {
        if (ip[i] >= '0' && ip[i] <= '9') {
            tmp += ip[i];
        } else if (ip[i] == '.') {
            cur_ips[ids++] = stoi(tmp);
            tmp.clear();
        } else if (ip[i] == '/') {
            cur_ips[ids++] = stoi(tmp);
            tmp.clear();
            have_seg = true;
        }
    }

    if (!tmp.empty()) {
        if (have_seg) {
            seg = stoi(tmp);
        } else {
            cur_ips[ids] = stoi(tmp);
        }
    }

    answer |= cur_ips[3];
    answer |= cur_ips[2] << 8u;
    answer |= cur_ips[1] << 16u;
    answer |= cur_ips[0] << 24u;

    return {answer, seg};
}

uint32_t make_mask(int seg) {
    uint32_t answer = 0;
    for (int i = 31, j = 0; i >= 0 && j < seg; i--, j++) {
        answer |= 1u << i;
    }
    return answer;
}

int query(const string& _ip) {
    uint32_t ip, seg;
    tie(ip, seg) = parseip(_ip);

    for (int i = 31; i >= 0; i--) {
        const uint32_t mask = make_mask(i + 1);
        if (ips[i].count(ip & mask)) {
            return ips[i][ip & mask];
        }
    }

    return -1;
}

void inc(const string& _ip, int id) {
    uint32_t ip, seg, mask;
    tie(ip, seg) = parseip(_ip);

    mask = make_mask(seg);
    ip &= mask;
    ips[seg - 1][ip] = id;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int id;
        string _ip;
        cin >> id >> _ip;
        inc(_ip, id);
    }

    for (int i = 0; i < m; i++) {
        string _ip;
        cin >> _ip;
        cout << query(_ip) << endl;
    }
    return 0;
}


## T3 Medium
博弈论:A 和 B 轮流取数,一共有 n 个物品,A 是先手,先手第一次可以取 [1, n - 1] 个物品。后续游戏,每个人至少取一个数,最多取前一个人取数的二倍,先取完者胜,都采取最优策略。给定 t 次独立游戏,问 A 获胜的次数是多少?

n 的数据到 1e9
打表发现是斐波那契数列,O(log(1e9)) 预处理,用哈希表维护,O(1) 查询
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_set>

using namespace std;
const int MAX = 1e9;

unordered_set<long long> invalid;
void prepare() {
    long long a = 1, b = 1;
    while (b <= MAX) {
        long long lst = a;
        a = b;
        b = a + lst;
        invalid.insert(b);
    }
}

int main() {
    prepare();
    int t;
    cin >> t;
    int answer = 0;
    for (int i = 0; i < t; i++) {
        int cur;
        cin >> cur;
        if (!invalid.count(cur)) answer++;
    }
    cout << answer << endl;
    return 0;
}


## T4 Medium
1、构建表达式树
2、dfs一遍,重新计算 id
3、dfs一遍,生成结果

复杂度 O(N),这里我偷懒了,没有 delete 释放空间
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>

using namespace std;

class TreeNode {
public:
    TreeNode *left, *right, *memo;
    int id = -1;
    char val;
    TreeNode() : left(nullptr), right(nullptr), val(0), memo(nullptr) {};
};

bool isSymbol(char ch) {
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}

unordered_map<string, TreeNode*> memo;
int id = 1, stridx = 0;

pair<TreeNode*, string> build(const string& str) {
    if (stridx == str.size()) {
        return {nullptr, ""};
    }

    if (str[stridx] == '(' || str[stridx] == ')' || str[stridx] == ',') {
        TreeNode* u;
        string x = string{str[stridx]};
        string buffer;

        stridx++;
        tie(u, buffer) = build(str);
        return {u, x + buffer};
    }

    TreeNode* u = new TreeNode();
    u->id = id++;
    u->val = str[stridx];
    string expr = {str[stridx]};
    const bool iss = isSymbol(str[stridx]);
    stridx++;

    if (iss) {
        string exprl, exprr;
        tie(u->left, exprl) = build(str);
        tie(u->right, exprr) = build(str);
        expr += "(" + exprl + "," + exprr + ")";
    }

    if (memo.count(expr)) {
        u->memo = memo[expr];
    } else {
        memo[expr] = u;
    }
    return {u, expr};
}

void reid(TreeNode* u) {
    if (u == nullptr) return;

    if (!u->memo) u->id = id++;
    if (u->left) reid(u->left);
    if (u->right) reid(u->right);
}

string traverse(TreeNode* u) {
    if (u == nullptr) return "";
    if (u->memo != nullptr) {
        return to_string(u->memo->id);
    }

    string answer = {u->val};
    if (isSymbol(u->val)) {
        answer += "(" + traverse(u->left) + "," + traverse(u->right) + ")";
    }
    return move(answer);
}

int main() {
//    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string exp;
        cin >> exp;

        id = 1;
        stridx = 0;
        memo.clear();

        TreeNode* root = build(exp).first;

        id = 1;
        reid(root);
        cout << traverse(root) << endl;
    }
    return 0;
}


全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐