hulu笔试的第三题与第四题有老哥会了吗

RT#hulu#
全部评论
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cstdlib> using namespace std; int n; int a[5100][5100]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int vis[5100][5100]; struct node {     int x,y,dis;     node(){}     node(int xx,int yy,int ddis):x(xx),y(yy),dis(ddis){} }; vector<node> ve; int bfs() {     queue<node> q0,q1;     ve.clear();     q0.push(node(0,0,0));     vis[0][0]=1;     while(1)     {         bool judge=false;         while(!q0.empty())         {             judge=true;             node z=q0.front();q0.pop();             if(z.x==n-1&&z.y==n-1) return z.dis;             for(int i=0;i<4;i++)             {                 int nx=z.x+dir[i][0];                 int ny=z.y+dir[i][1];                 if(nx<0||nx>=n||ny<0||ny>=n) continue;                 if(vis[nx][ny]) continue;                 if(a[nx][ny]==0) q0.push(node(nx,ny,z.dis));                 else q1.push(node(nx,ny,z.dis+1));                 vis[nx][ny]=1;             }         }         if(!judge)         {             int sz=(int)ve.size();             for(int i=0;i<sz;i++)             {                 q1.push(ve[i]);                 vis[ve[i].x][ve[i].y]=1;             }             ve.clear();         }         while(!q1.empty())         {             node z=q1.front();q1.pop();             if(z.x==n-1&&z.y==n-1) return z.dis;             for(int i=0;i<4;i++)             {                 int nx=z.x+dir[i][0];                 int ny=z.y+dir[i][1];                 if(nx<0||nx>=n||ny<0||ny>=n) continue;                 if(vis[nx][ny]) continue;                 if(a[nx][ny]==0)                 {                     q0.push(node(nx,ny,z.dis));                     vis[nx][ny]=1;                 }                 else ve.push_back(node(nx,ny,z.dis+1));             }         }     } } int main() {     while(scanf("%d",&n)!=EOF)     {         for(int i=0;i<n;i++)             for(int j=0;j<n;j++)                 scanf("%d",&a[i][j]);         memset(vis,0,sizeof(vis));         printf("%d\n",bfs());     }     return 0; } 第三题
点赞 回复 分享
发布于 2019-09-05 23:45
第四题贴个代码,做法没问题,python没有gc所以一直内存超限。。优化了很久把dp的dict改成反复清空的一维list还是不行,十分郁闷。。 其实思路跟leetcode 813.最大平均值和的分组 差不多,就是把平均数换成了类别数 import sys def largestScore(A: list, K: int) -> float: n = len(A) count = {} # 先计算各个段的场次数方便后面调用 for i in range(n): now = {A[i]} count[i, i+1] = 1 for j in range(i+1, n): now.add(A[j]) count[i, j+1] = len(now) dp = {(1, i): count[0, i] for i in range(1, n+1)} # dp[k, i] 前i个数分成k组的最大分数 for i in range(2, n+1): for j in range(i, n+1): _max = dp[i-1, j-1] + 1 for k in range(i-1, j-1): _max = max(_max, dp[i-1, k] + count[k, j]) dp[i, j] = _max return dp[K, n] _, K = map(int, sys.stdin.readline().strip().split(' ')) A = list(map(int, sys.stdin.readline().strip().split(' '))) print(largestScore(A, K))
点赞 回复 分享
发布于 2019-09-06 21:38
第三题,求最短路
点赞 回复 分享
发布于 2019-09-06 09:31
能发下题目吗?谢谢了🤣
点赞 回复 分享
发布于 2019-09-06 00:30
看到大佬,大佬A了几道
点赞 回复 分享
发布于 2019-09-05 22:31

相关推荐

每晚夜里独自颤抖:1600一个月?
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
点赞
6
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务