腾讯笔试部分题解(之后有空可能补题解）
第一题 字符串解压缩 AC
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
string solve(string str,int start,int end){
string ans;
for(int i = start;i<=end;){
int cnt = 0;
int val = 0;
string s1;
if(str[i]!='['){
ans+=str[i];
i++;
}else{
cnt++;
i++;
while(str[i]>='0'&&str[i]<='9'){
val = val*10+(str[i]-'0');
i++;
}
i++;
int s = i;
while(cnt>0){
if(str[i]=='['){
cnt++;
}else if(str[i]==']'){
cnt--;
if(cnt == 0){
break;
}
}
i++;
}
int e = i-1;
s1 = solve(str, s, e);
i++;
}
for(int j = 0;j<val;j++){
ans+=s1;
}
}
return ans;
}
int main(){
string s;
cin>>s;
int n = s.size();
cout<<solve(s,0,n)<<endl;
} 第二题 逆序对（好难，树状数组和归并排序可以过50%)
第三题 最少真眼看到L距离 AC
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int solve(vector<pair<int, int>>& vp,int n,int l){
sort(vp.begin(), vp.end());
if(vp[0].first!=0) return -1;
int cnt = 0;
int pre_end = 0;
int end = 0;
for(int i = 0;i<n;){
while(i<n && vp[i].first <= pre_end){
end = max(end,vp[i].second);
i++;
}
cnt++;
pre_end = end;
if(pre_end>=l){
return cnt;
}
}
return -1;
}
int main(){
int n,l;
scanf("%d %d",&n,&l);
vector<pair<int, int>> vp(n);
for(int i = 0;i<n;i++){
scanf("%d %d",&vp[i].first,&vp[i].second);
}
cout<<solve(vp, n, l)<<endl;
}
第四题 看到的建筑数量 AC
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int n;
scanf("%d",&n);
vector<int> v(n,0);
for(int i = 0;i<n;i++){
scanf("%d",&v[i]);
}
stack<int> st1;
stack<int> st2;
vector<int> left(n,0);
vector<int> right(n,0);
vector<int> z(n,0);
for(int i = 0;i<n;i++){
if(st1.empty()||st1.top()>v[i]){
left[i] = st1.size();
st1.push(v[i]);
}else{
left[i] = st1.size();
while(!st1.empty() && v[i]>=st1.top()){
st1.pop();
}
st1.push(v[i]);
}
}
for(int i = n-1;i>=0;i--){
if(st2.empty() || st2.top()>v[i]){
right[i] = st2.size();
st2.push(v[i]);
}else{
right[i] = st2.size();
while(!st2.empty() && st2.top()<=v[i]){
st2.pop();
}
st2.push(v[i]);
}
}
for(int i = 0;i<n;i++){
cout<<left[i]+right[i]+1<<" ";
}
} 第五题 最少休息时间 AC
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int n;
scanf("%d",&n);
vector<int> v1(n);
vector<int> v2(n);
for(int i = 0;i<n;i++) scanf("%d",&v1[i]);
for(int i = 0;i<n;i++) scanf("%d",&v2[i]);
int dp[n+1][2];
memset(dp, 0, sizeof dp);
for(int i = 0;i<n;i++){
if(v1[i]==1){
dp[i+1][0] = (i<1?0:dp[i-1][0])+1;
if(i-1>0 && v1[i-1]==0) dp[i+1][0] = max(dp[i+1][0],dp[i][0]+1);
dp[i+1][0] = max(dp[i+1][0],dp[i][1]+1);
}else if(v1[i]==0){
dp[i+1][0] = max(dp[i+1][0],dp[i][0]);
dp[i+1][0] = max(dp[i+1][0],dp[i][1]);
}
if(v2[i]==1){
dp[i+1][1] = (i<1?0:dp[i-1][1])+1;
if(i-1>0 && v2[i-1]==0) dp[i+1][1] = max(dp[i+1][1],dp[i][1]+1);
dp[i+1][1] = max(dp[i+1][1],dp[i][0]+1);
}else if(v2[i]==0){
dp[i+1][1] = max(dp[i+1][1],dp[i][1]);
dp[i+1][1] = max(dp[i+1][1],dp[i][1]);
}
}
cout<<n-max(dp[n][0],dp[n][1])<<endl;
} 
膜拜一下
投递APP Annie Ltd等公司10个岗位 >