后端开发岗,小红书四道题解
单独第一道:
#include<bits/stdc++.h> using namespace std; vector<vector<int> > dir={{0,1},{0,-1},{-1,0},{1,0}}; int Fill(vector<vector<int> >& map, int n, int m) { vector<vector<int> > time(n,vector<int>(m,INT_MAX)); vector<vector<int> > flag(n,vector<int>(m,0)); time[0][0]=0; queue<vector<int>> q; vector<int> tmp(2,0); q.push(tmp); while(!q.empty()){ vector<int> cur=q.front(); q.pop(); for(int i=0;i<dir.size();++i){ int x=cur[0]+dir[i][0]; int y=cur[1]+dir[i][1]; if(x>=0 && x<n && y>=0 && y<m && map[x][y] ==0 && flag[x][y]==0){ time[x][y]=time[cur[0]][cur[1]]+1; flag[x][y]=1; tmp[0]=x;tmp[1]=y; q.push(tmp); } } } return time[n-1][m-1]; } int main(){ int n; int m; int k; cin>>n>>m>>k; vector<vector<int>> map(n,vector<int>(m,0)); for(int i=0;i<k;++i){ int row; int col; cin>>row>>col; map[row][col]=1; } int res=Fill(map,n,m); if(res==INT_MAX){ cout<<0<<endl; }else{ cout<<res<<endl; } return 0; }
一起的三道,
其中第一道:
#include<bits/stdc++.h> using namespace std; int main(){ string str; cin>>str; string cur; stack<int> st; for(int i=0;i<str.size();++i){ if(str[i]=='('){ st.push(i); }else if(str[i]==')'){ st.pop(); }else{ if(st.empty()){ cur=cur+str[i]; } } } stack<char> chstk; for(int i=0;i<cur.size();++i){ if(cur[i]=='<'){ if(!chstk.empty()){ chstk.pop(); } }else{ chstk.push(cur[i]); } } stack<char> res; while(!chstk.empty()){ res.push(chstk.top()); chstk.pop(); } while(!res.empty()){ cout<<res.top(); res.pop(); } cout<<endl; return 0; }第二道:
#include<bits/stdc++.h> using namespace std; vector<vector<int> > dir={{0,1},{0,-1},{-1,0},{1,0}}; int startx=0; int starty=0; int endx=0; int endy=0; int Fill(vector<string >& map, int n) { vector<vector<int> > time(n,vector<int>(n,INT_MAX)); vector<vector<int> > flag(n,vector<int>(n,0)); time[startx][starty]=0; queue<vector<int>> q; vector<int> tmp={startx,starty}; q.push(tmp); while(!q.empty()){ vector<int> cur=q.front(); q.pop(); for(int i=0;i<dir.size();++i){ int x=cur[0]+dir[i][0]; int y=cur[1]+dir[i][1]; if(x==-1){ x=n-1; }else if(x==n){ x=0; } if(y==-1){ y=n-1; }else if(y==n){ y=0; } if(x>=0 && x<n && y>=0 && y<n && (map[x][y] =='.' || map[x][y] =='E' )&& flag[x][y]==0){ time[x][y]=time[cur[0]][cur[1]]+1; if(x==endx && y==endy){ return time[x][y]; } flag[x][y]=1; tmp[0]=x;tmp[1]=y; q.push(tmp); } } } return time[endx][endy]; } int main(){ int n; cin>>n; vector<string> map; for(int i=0;i<n;++i){ string str; cin>>str; for(int j=0;j<str.size();++j){ if(str[j]=='S'){ startx=i; starty=j; } if(str[j]=='E'){ endx=i; endy=j; } } map.push_back(str); } int res=Fill(map,n); if(res==INT_MAX){ cout<<"-1"<<endl; }else{ cout<<res<<endl; } return 0; }
第三道:
woc,刚被我删掉了。。。没保存。。。
好了,重新打了一下:
#include<bits/stdc++.h> using namespace std; int helper(vector<vector<int> > &vec) { vector<vector<int>> dp; sort(vec.begin(),vec.end(),[](vector<int> l,vector<int> r) {return l[0]<r[0] || (l[0]==r[0] && l[1]<r[1]);}); for(vector<int> cur:vec){ int low=0; int high=dp.size(); while(low<high){ int mid=(low+high)/2; if(dp[mid][0]<=cur[0] && dp[mid][1]<=cur[1]) { low=mid+1; } else { high=mid; } } if(high<dp.size()) { dp[high]=cur; } else dp.push_back(cur); } return dp.size(); } int main(){ int n; cin>>n; vector<vector<int>> vec(n,vector<int>(2,0)); for(int i=0;i<n;++i){ cin>>vec[i][0]>>vec[i][1]; } cout<<helper(vec)<<endl; return 0; }