4.12字节跳动笔试
春招到现在做过最简单的笔试，A了3道，第二题不会，求大佬解答第二题怎么做。下面贴下1、2、4题的代码：
1. 双指针找出左右边界，然后比较区间中每个位置的差值是否相等
#include<iostream>
#include<vector>
using namespace std;
bool solve(vector<int>& a, vector<int>& b){
int left = 0;
int right = a.size()-1;
while(left<a.size()){
if(a[left] == b[left]) left++;
else break;
}
while(right>=0){
if(a[right] == b[right]) right--;
else break;
}
while(left<right){
if((a[left]-b[left])!=(a[right]-b[right]))
return false;
left++;
right--;
}
return true;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> a(n,0);
vector<int> b(n,0);
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
if(solve(a, b)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
2. 一道简单的二分搜索题目，对优惠券数组的排序用计数排序，复杂度O（n），如果用标准库快排只能AC 90%
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int binarysearch(int target, vector<int>& arr){
int left = 0;
int right = arr.size()-1;
while(left<right){
int mid = (left + right)/2 + 1;
if(arr[mid] > target)
right = mid - 1;
else
left = mid;
}
return arr[left]<=target? arr[left]:0;
}
long long solve(vector<int>& tickets, vector<int>& products){
vector<int> count(1000001, 0);
vector<int> order_tickets(tickets.size(),0);
for(auto t:tickets){
count[t]++;
}
int index = 0;
for(int i=0;i<count.size();i++){
for(int j=0;j<count[i];j++){
order_tickets[index++] = i;
}
}
long long min_cost = 0;
for(auto val: products){
int cost_cut = binarysearch(val, order_tickets);
min_cost += (val-cost_cut);
}
return min_cost;
}
int main(){
int n, m;
cin>>n>>m;
vector<int> tickets(n, 0);
vector<int> products(m, 0);
for(int i=0;i<n;i++)
cin>>tickets[i];
for(int i=0;i<m;i++)
cin>>products[i];
cout<<solve(tickets, products)<<endl;
};
4. 单调栈，调了很久才AC，写的有点凌乱
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
void solve(vector<int>& heights){
vector<int> res(heights.size(), 0);
vector<int> st;
for(int i=0;i<heights.size();i++){
if(st.size()==0 || heights[st.back()]>=heights[i]){
st.push_back(i);
}
else{
while(st.size()!=0 && heights[i]>heights[st.back()]){
int top = st.back();
st.pop_back();
int left=-1;
vector<int> tmp;
while(st.size()!=0){
if(heights[st.back()]>heights[top]){
left = st.back();
break;
}
else{
tmp.push_back(st.back());
st.pop_back();
}
}
res[top] = i-left-2;
for(auto i:tmp)
res[i] = res[top];
}
st.push_back(i);
}
}
while(st.size()!=0){
int top = st.back();
st.pop_back();
int left=-1;
vector<int> tmp;
while(st.size()!=0){
if(heights[st.back()]>heights[top]){
left = st.back();
break;
}
else{
tmp.push_back(st.back());
st.pop_back();
}
}
res[top] = heights.size()-left-2;
for(auto i:tmp)
res[i] = res[top];
}
for(int i=0;i<res.size();i++){
if(i==0)
cout<<res[i];
else
cout<<" "<<res[i];
}
cout<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> heights(n, 0);
for(int i=0;i<n;i++)
cin>>heights[i];
solve(heights);
}
}
