首页 > 华为笔试

华为笔试

1.
//1.完美排列
bool judge(vector<int>&perfect_waiguan,vector<int>&perfect_price,vector<int>&waiguan,vector<int>&price,int K,int begin)
{
  for(int i=0;i<K;i++)
  {
    int index=begin+i;
    if(perfect_waiguan[i]!=waiguan[index] ||  perfect_price[i]!=price[index] )
    return false;
  }
  return true;
}
int main()
{
  int K;
  cin>>K;
  vector<int>perfect_waiguan(K,0);
  vector<int>perfect_price(K,0);
  for(int i=0;i<K;i++)
  cin>>perfect_waiguan[i];
  for(int i=0;i<K;i++)
  cin>>perfect_price[i];

  int N;
  cin>>N;
  vector<int>waiguan(N,0);
  vector<int>price(N,0);
  for(int i=0;i<N;i++)
  cin>>waiguan[i];
  for(int i=0;i<N;i++)
  cin>>price[i];
  //遍歷完美排列 6-3=3
  int index=0;
  for(int begin=0;begin<=N-K;begin++)
  {
    if(judge(perfect_waiguan,perfect_price,waiguan,price,K,begin))//是完美排列
    {
      index=begin+1;
      break;
    }
  }
  cout<<index<<endl;
}
2.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//2.DAG
int main()
{
  int h,w;
  cin>>h>>w;
  vector< vector<int> >M(h,vector<int>(w,0));
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin>>M[i][j];
  //DAG
  int p_n=w*h;
  vector< vector<int> >g(p_n,vector<int>(p_n,0));
  int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
  //建圖
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
    {
      int index=w*i+j;
      for(int k=0;k<4;k++)
      {
        int x_new=i+dir[k][0];
        int y_new=j+dir[k][1];
        int index_new=x_new*w+y_new;
        //
        if(x_new<h && x_new>=0 && y_new>=0 && y_new<w && M[i][j]>M[x_new][y_new] )
            g[index][index_new]=1;
      }
    }

    
    //開始拓撲排序
    vector<int>dp(p_n,0);
    vector<int>in(p_n,0);
    vector<int>visited(p_n,0);

    for(int j=0;j<p_n;j++)
    for(int i=0;i<p_n;i++)
        in[j]=in[j]+g[i][j];

    queue<int>q;
    //in=0 push
    for(int i=0;i<p_n;i++)
      if(in[i]==0)
        {
          q.push(i);
          dp[i]=1;
        }
    int MAX=0;
    while(!q.empty())
    {
      int temp=q.front();
      //visit
      visited[temp]=1;
      MAX=max(MAX,dp[temp]);
      q.pop();
      for(int i=0;i<p_n;i++)
      {
        if(g[temp][i]==1 && visited[i]==0)
        {
          //dp
          dp[i]=max(dp[i],dp[temp]+1);
          in[i]--;
          if(in[i]==0)
          q.push(i);
        }
      }
    }
    cout<<MAX<<endl;
}



全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐