字节跳动笔试 100 100 50 0, 第三题考完后补充了

第一题

找厕所，只要往左右两边找就可以了，这样的话复杂度 , 但是应该有的解法

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

int main() {
    int N = 0;
    cin >> N;
    vector<char> str(N);
    for (int i = 0; i < N; i++) {
        cin >> str[i];
    }
    for (int i = 0; i < N; i++) {
        int j = 0;
        while (true) {
            if (i - j >= 0 && str[i - j] == 'O') {
                break;
            }
            if (i + j < N && str[i + j] == 'O') {
                break;
            }
            j++;
        }
        if (i == N - 1) {
            cout << j << endl;
        }
        else {
            cout << j << " ";
        }
    }
    return 0;
}

第二题

按顺序做题，每道题的花费的时间为cost[i], 给定题的数目n, 总时间m, 求为了做第i道题，前面i-1题中至少要放弃几道题?

input:
2
5 5
1 2 3 4 5
4 4
4 3 2 1
output:
0 0 1 2 4
0 1 2 2

相当于01背包，设前i道题中，相加不超过j的题的数目最大为dp[i][j], 此题相当于求i - dp[i][m-a[i]]

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

int main() {
    int T = 0;
    cin >> T;
    for (int t = 0; t < T; t++) {
        int n = 0;
        int m = 0;
        cin >> n >> m;
        vector<int> cost(n);
        for (int i = 0; i < n; i++) {
            cin >> cost[i];
        }

        vector<int> dp(m + 1);
        if (n == 0) {
            cout << 0 << endl;
            continue;
        }
        cout << 0 << " ";
        for (int i = 1; i < n; i++) {
            int w = cost[i - 1];
            for (int j = m; j >= w; j--) {
                dp[j] = max(1 + dp[j - w], dp[j]);
            }
            if (i == n - 1) {
                cout << i - dp[m - cost[i]] << endl;
            } else {
                cout << i - dp[m - cost[i]] << " ";
            }

        }


    }
    return 0;
}

第三题

就是拓扑排序，但是处理输入输出太不熟练了，花了好多时间。一开始直接用vector<vector<int>>存，后来又发现领导id可以是负数, 改来改去也没写对。。。最后过50%好像完全是因为输出-1</int>

附上我考完后重做的吧

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

void topoSort(map<int, vector<int>>& adj, map<int, int>& inDegree, vector<int>& res) {
    priority_queue<int, vector<int>, greater<int>> zeroDegree;
    // 入度为0的入队
    for (auto it = inDegree.begin(); it != inDegree.end(); it++) {
        if (it->second == 0) {
            zeroDegree.push(it->first);
        }
    }

    while (!zeroDegree.empty()) {
        int cur = zeroDegree.top();
        zeroDegree.pop();
        res.push_back(cur);
        // cur相连的点，入度减1
        for (auto adjId : adj[cur]) {
            inDegree[adjId]--;
            if (inDegree[adjId] == 0) {
                zeroDegree.push(adjId);
            }
        }
    }

}

int main() {
    map<int, vector<int>> adj;
    map<int, int> inDegree;
    string line;
    while (getline(cin, line)) {
        istringstream iss(line);
        int cur = 0;
        iss >> cur;
        inDegree[cur] = 0;

        int adjId = 0;
        while (iss >> adjId) {
            adj[adjId].push_back(cur);
            inDegree[cur]++;
        }
    }

    vector<int> res;
    topoSort(adj, inDegree, res);

    if (res.size() == adj.size()) {
        for (int i = 0; i < res.size(); i++) {
            if (i == res.size() - 1) {
                cout << res[i] << endl;
            } else {
                cout << res[i] << " ";
            }
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}

第四题

全在折腾第三题了，题目都没来得及看。。。