一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1054|回复: 14
收起左侧

[算法题] 求大神指点 G家面经题

[复制链接] |试试Instant~ |关注本帖
queeniejing 发表于 2015-11-18 10:15:39 | 显示全部楼层 |阅读模式

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

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

x
公司有很多office,你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。

这道题应该怎么解? 跪求大神指点啊

评分

1

查看全部评分

本帖被以下淘专辑推荐:

vivianbuan 发表于 2015-11-18 11:52:30 | 显示全部楼层
感觉是个max flow.太久没做图论了。。。手动马克等大神解答
回复 支持 反对

使用道具 举报

tq5124 发表于 2015-11-18 12:02:30 | 显示全部楼层
感觉dp就可以?OPT(i,j)表示在第i个星期呆在j办公室的情况下,从年初到现在获得的假期。然后每次计算OPT(i,j) = max(OPT(i-1, k)),k是所有能在一个周末飞到j办公室的办公室。二维数组保存dp结果,算一遍后求个最大的假期
回复 支持 反对

使用道具 举报

plich 发表于 2015-11-18 23:16:22 | 显示全部楼层
tq5124 发表于 2015-11-18 12:02
感觉dp就可以?OPT(i,j)表示在第i个星期呆在j办公室的情况下,从年初到现在获得的假期。然后每次计算OPT(i, ...

应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

最顺溜的follow up就是问最大假期的方案,那么更新OPT(i,j)的时候顺手记下来trace就行了
回复 支持 反对

使用道具 举报

tq5124 发表于 2015-11-19 01:38:14 | 显示全部楼层
plich 发表于 2015-11-18 23:16
应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

啊把vacation忘掉了。。。thx~
回复 支持 反对

使用道具 举报

 楼主| queeniejing 发表于 2015-11-19 03:38:09 | 显示全部楼层
明白了 谢谢楼上各位大神
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-19 12:05:08 | 显示全部楼层
这题我觉得应该用状态机,就是每次产生节点给能到达的office,然后再产生下一个level的节点,直到最后,取那个level假期最大值。
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-2 12:33:32 | 显示全部楼层
写了一下,感觉复杂度有点高啊。。。求大神们指导。。。
  1. public class MaxHoliday{
  2.         public int findMax(int [][] holiday, int [][]flight,int hour){
  3.                 int [][] dp = new int [flight.length][holiday.length];
  4.                 for(int i = 0; i < holiday.length; i++)
  5.                         dp[i][0] = holiday[i][0];
  6.                 for(int i = 1; i < holiday[0].length; i++){
  7.                         // i stand for week
  8.                         for(int j = 0 ; j < flight.length; j++){
  9.                                 // j is origin office
  10.                                 for(int k = 0; k < flight.length; k++){
  11.                                         // k is destination office
  12.                                         if(flight[j][k]<=hour){//flight time needs to be smaller than some time.
  13.                                                 //new office holiday equals the original holiday + new office holiday
  14.                                                 dp[k][i] = Math.max(dp[k][i],dp[j][i-1] + holiday[k][i]);
  15.                                         }
  16.                                 }
  17.                         }
  18.                 }
  19.                 for(int i = 0; i < dp.length; i++){
  20.                         for(int j = 0; j< dp[0].length; j++){
  21.                                 System.out.print(dp[i][j] + "\t");
  22.                         }
  23.                         System.out.println();
  24.                 }
  25.                 int maxHour = 0;
  26.                 for(int i = 0; i < flight.length; i++){
  27.                         maxHour = Math.max(maxHour, dp[i][holiday.length-1]);
  28.                 }
  29.                 return maxHour;
  30.                
  31.         }
  32.         public static void main(String args[]){
  33.                 int [][] holiday = {//column is week,holiday[i][j] stands for in week i, office j's holiday
  34.                         {0,1,2,1,0},
  35.                         {0,0,0,0,1},
  36.                         {1,1,0,1,2},
  37.                         {2,1,1,2,1},
  38.                         {1,2,3,1,2}};
  39.                 int [][] flight ={//flight[i][j] stands for fly time from city i to city j
  40.                         {0,6,3,5,2},
  41.                         {6,0,1,3,4},
  42.                         {3,1,0,2,1},
  43.                         {5,3,2,0,2},
  44.                         {2,4,1,2,0}};
  45.                 MaxHoliday mh = new MaxHoliday();
  46.                 System.out.println(mh.findMax(holiday,flight,3));
  47.         }
  48. }
复制代码
回复 支持 反对

使用道具 举报

queqichao 发表于 2015-12-2 13:14:04 | 显示全部楼层
假设有N个office,M个week,V(i,j) 是第i个礼拜 office j的假期数。另外建一个有向图图,每个node代表一个office,i->j 表示可以从j到i。
最后做DP,建一个M X N 的table T,T(i,j) 纪录的在第i个礼拜停在office j时,已经休的假的最大值。T(i+1, j) = max(T(i,k), 能从k到j) + V(i + 1, j)
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-2 14:14:50 | 显示全部楼层
杰西Jesse 发表于 2015-12-2 12:33
写了一下,感觉复杂度有点高啊。。。求大神们指导。。。

这样做会有cycle吗..
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-3 00:05:31 | 显示全部楼层

cycle的意思是指? 从A->B->A
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-3 03:38:12 | 显示全部楼层
杰西Jesse 发表于 2015-12-3 00:05
cycle的意思是指? 从A->B->A

就是A->B, B->A reachable 而且这两条边holiday[A][B], holiday[B][A] 和任何holiday[x][y]比较 也是最大的
会不会最后得出的结果是通过不断在这两条边飞来飞去累加而成的。。
我只是粗略看了下code..说的不对的话见谅..
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-5 11:54:58 | 显示全部楼层
这道题好像出现过不少次啊,有大神详细解释下吗?
回复 支持 反对

使用道具 举报

staycrazy 发表于 2016-2-5 13:10:30 | 显示全部楼层
plich 发表于 2015-11-18 23:16
应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

我觉得题意不明。

因为有路径长度限制,可能要走回头路才能达到最大值。比如说:

A---B----C
      |
      D---E----F----.....-----Z

连通情况如上。第二周周末在C,第三周周末却回到了B,第四周才去D。这里B的假期可以重复计算吗?

如果B的假期可以重复计算,那么到达一个假期非常多的办公室之后就可以赖着不走了

如果B的假期不可以重复计算,那么第三周的假期就不能+V(3, B)
回复 支持 反对

使用道具 举报

plich 发表于 2016-2-9 06:10:19 | 显示全部楼层
staycrazy 发表于 2016-2-5 13:10
我觉得题意不明。

因为有路径长度限制,可能要走回头路才能达到最大值。比如说:

举个例子……让我出题的话,第一周B的假期和第30周B的假期不会是一样的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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