0922字节跳动笔试100+100+90+8
第一题，100%
先判断距离右边最近的厕所，然后从左往右遍历，比较距离左右厕所的最小值，输出。
#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
int main(){
int n;
string s;
cin >> n >> s;
vector<int> right(n, INF);
int p = INF;
for(int i = n - 1; i >= 0; i--){
if(s[i] == 'O'){
p = i;
}
right[i] = p - i;
}
p = -INF;
for(int i = 0; i < n; i++){
if(s[i] == 'O'){
p = i;
}
cout << min(i - p, right[i]) << " ";
}
return 0;
} 第二题100% 优先队列，每次pop掉最大的，注意pop掉的后面要放回去，因为本身t可能很大。我这里直接把全部都放回去，发现也过了，挺暴力的。按道理还是应该比较处理下。
#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
int main(){
int T, n, time, t;
cin >> T;
while(T--){
cin >> n >> time;
priority_queue<int> q;
ll sum = 0;
for(int i = 0; i < n; i++){
cin >> t;
vector<int> v;
while(sum + t > time){ //
sum -= q.top();
v.emplace_back(q.top());
q.pop();
}
cout << i - q.size() << " "; // 输出结果
v.emplace_back(t);
for(auto t : v){ //全部放回去，挺暴力的
q.push(t);
sum += t;
}
}
cout << endl;
}
return 0;
}
第三题90% 不知道哪里错了。
拓扑排序，每次找到入度为0的点，进行排序。
坑：
1，输入的问题，有点坑.
2，输出问题，最后不能有空格
3，这道题直接输出-1得50%。
4，最大的坑，没告诉数据范围，差点想用map了，想了下数据应该不太强，就没用，数组开大。
5，用set来找入度为0的点，这样找到就是最小的点。找到就break,，然后删除他。
#include<bits/stdc++.h>
#define INF 10000000
using namespace std;
typedef long long ll;
const int N = 1000000;
int main(){
string s;
int t, tmp;
vector<vector<int>> v(N);
vector<int> indegree(N, 0);
set<int> si;
while(getline(cin, s)){
istringstream ss(s);
ss >> tmp;
si.insert(tmp);
while(ss >> t){
v[t].push_back(tmp);// t - > tmp
indegree[tmp]++;
si.insert(t);
}
}
int size = (int)si.size();
queue<int> q;
for(auto a : si){
if(indegree[a] == 0){
q.push(a);
si.erase(a);
break;
}
}
vector<int> re;
while(!q.empty()){
int f = q.front(); q.pop();
re.emplace_back(f);
for(auto a : v[f]){
indegree[a]--;
}
for(auto a : si){
if(indegree[a] == 0){
q.push(a);
si.erase(a);
break;
}
}
}
if(re.size() == size){
cout << re[0];
for(int i = 1; i < size; i++) cout << " " << re[i];
cout<<endl;
}else{
cout<<-1<<endl;
}
return 0;
} 第四题，8% 思路：无
不会，应该是dp? 随便写了点，输出max(a,b)，过了8%，就不贴代码了，太菜了哎。
#笔试题目##字节跳动#
投递淘天集团等公司10个岗位 >