详谈如何最大化利用career fair

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 1069|回复: 5
收起左侧

[算法题] 求一道题思路

[复制链接] |试试Instant~
我的人缘0
123呆板彻底 发表于 2016-10-23 22:17:45 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (216)
 
 
6% (14)  踩

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
在一个迷宫中,给定起点终点,
迷宫中1代表礼物,2代表墙,3代表空地
要求输出收集完所有礼物以后走到终点的最短路径。如果不可能收集完则输出-1

上一篇:面试的时候求最小值我用了初始最大整数,居然...
下一篇:求问关于k个最小元素
我的人缘0
gc1993114 发表于 2016-10-24 00:06:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (76)
 
 
0% (0)  踩
先数一下有几个礼物,dfs应该可以吧?就是复杂度有点高…可是bfs走重复的点,好像要更新礼物数…不知道怎么弄
回复

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
QDkAc 发表于 2016-10-25 13:21:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (83)
 
 
0% (0)  踩
会两种方法
假设迷宫大小n*m 有k个礼物
第一种复杂度为k! + (nm)^2
做法:
(1)求出任意一对点之间最短路的长度,这可以通过nm次BFS做到
(2)枚举k个礼物经过的顺序,共k!种,相邻两个礼物之间用(1)求得得最短路连接起来

第二种复杂度为nm*2^k
做法
用dis[x][y][S]表示从起点到点(x, y),而且必须已经经过S里面的礼物(S是一个集合)
这样答案就是dis[终点][全集]
具体写代码的时候S可以用一个int表示,用一些位运算的技巧
回复

使用道具 举报

我的人缘0
QDkAc 发表于 2016-10-25 13:32:38 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (83)
 
 
0% (0)  踩
本帖最后由 QDkAc 于 2016-10-25 13:38 编辑
  1. 第二种算法伪代码

  2. Q.push(sx); Q.push(sy); Q.push(0); //太懒了,Q是一个队列,一次压3个弹3个
  3. while (Q.empty() == false){
  4.   int nowx = Q.front(); Q.pop(); int nowy = Q.front(); Q.pop(); int nowS = Q.front(); Q.pop();
  5.   for (int d = 0; d < 4; d++){ //上下左右
  6.     int newx = nowx + dx[d], newy = nowy + dy[d]; //const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0};
  7.     if (newx, newy 超过边界或者是障碍)
  8.       continue;
  9.     //我们假设每个格子有一个0..k-1的label,用l[x][y]表示。可以自己设置一个。没有礼物的地方l[x][y] = -1;
  10.     int newS = nowS; //设置为之前经过的
复制代码
回复

使用道具 举报

我的人缘0
QDkAc 发表于 2016-10-25 13:40:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (83)
 
 
0% (0)  踩
不知道为啥老吞代码 LZ先意会一下 不懂再问我吧

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
bona 发表于 2017-12-24 23:16:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (11)
 
 
15% (2)  踩
最近面的一个startup中的oa题!当时只写了一个greedy/nearest neighbor的解法(并且还有bug),现在想到应该是tsp,但是tsp的解法略复杂,面试的时间短暂,能写完整的实在太挑战了。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-25 17:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表