字节跳动笔试 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; }
第四题
全在折腾第三题了,题目都没来得及看。。。
#笔试题目##字节跳动#