字节跳动笔试 1题代码 3题思路

第一题AC

找厕所

思路：用num数组保存每个有厕所的商铺的位置

然后对于每个商铺去num里面二分找位置，求距离

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;


int main()
{
      int f[1000100];
      int n;
      int num[1000100];
      int len;
      int a,b;
      int p;
      string s;
      cin>>n>>s;
      for (int i=0;i<n;i++) f[i]=10000100;

      len=0;num[0]=-10000100;
      for (int i=0;i<n;i++)
            if (s[i]=='O')
            {
                  len++;
                  num[len]=i;
            }
      len++;num[len]=10000100;

      for (int i=0;i<n;i++)
            if (s[i]=='X')
            {
                  p=upper_bound(num+1,num+len+1,i)-num;
                  //cout<<"p="<<p<<endl;
                  a=i-num[p-1];
                  b=num[p]-i;
                  if (a<b) cout<<a<<' ';
                  else cout<<b<<' ';
            }
            else cout<<0<<' ';
      return 0;
}

第二题：

做题

没看，盲猜DP

第三题：

找老板签字

一个有向无环无权值图的拓扑排序，输入处理可以用stringstream

但是字典序最小怎么找啊！我要傻了

#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<sstream>
#include<string>
#define M 100010
using namespace std;

struct node
{
      int to,bro;

}edge[M];

int head[M];
int inn[M],ott[M],pre[M];
int tail,n;
int begino,endo;
bool check[M];

void build(int a,int b)
{
      edge[tail].to=b;
      edge[tail].bro=head[a];
      head[a]=tail++;
}

void SPFA(int s)
{
      int ans[M];
      int len;

      queue<int>q;
      q.push(s);
      check[s]=true;
      len=1;
      ans[1]=s;
      int num[M];
      int x;

      while (!q.empty())
      {
            int u=q.front();
            q.pop();
            check[u]=false;
            len++;
            ans[len]=M;
            x=0;
            cout<<u<<' ';
            for (int i=head[u];i!=-1;i=edge[i].bro)
            {
                  int v=edge[i].to;
                  ott[u]--;
                  inn[v]--;
                  if (inn[v]==0 && !check[v])
                  {
                        check[v]=true;
                        x++;
                        num[x]=v;
                  }
            }
            sort(num+1,num+1+x);

            for (int i=1;i<=x;i++) q.push(num[i]);
      }
}

int main()
{
      int x;
      int people;
      string s;
      stringstream ss;

      memset(inn,0,sizeof(inn));
      memset(ott,0,sizeof(ott));

      memset(pre,-1,sizeof(pre));
      memset(head,-1,sizeof(head));

      memset(check,0,sizeof(check));

      n=0;
      tail=0;

      while (cin>>people)
      {
            n++;
            getline(cin,s);
            ss.clear();
            ss.str(s);
            while (1)
            {
                  ss>>x;
                  if (ss.fail()) break;
                  inn[people]++;
                  ott[x]++;
                  build(x,people);
            }
      }

      for (int i=1;i<=n;i++)
      {
            if (inn[i]==0) begino=i;
            if (ott[i]==0) endo=i;
      }

      SPFA(begino);

      return 0;
}

#笔试题目##字节跳动#