美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 日本网友拍摄乌龟 竟在照片中发现了两个印度人
  • 黑飞作死!成都查获两起无人机干扰机场案件
  • 领先波音空客!国产“灵雀B”验证机成功首飞
  • 马斯克:读心术是未来 我们已经是半机械人
  • 哈弗HB-03概念SUV现身:宝马X6既视感
  • 空间无敌 广汽传祺GS7预售:15.58万起
  • 高校食堂用上黑科技 餐盘可自己算账
  • 俄罗斯“终结者”机器人现世 枪法不错还会开车
  • 新手女司机试驾奥迪 撞毁21辆新车
  • 史上最轻快!摩拜共享单车再出新品:代号“风轻扬”
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3024|回复: 8

    内推面经 -面试题讨论:最多假期的问题- 唐人社区|北美华人论坛

    [复制链接]

    11

    主题

    28

    帖子

    49

    积分

    新手上路

    Rank: 1

    积分
    49
    QQ
    发表于 2016-10-29 05:02:54 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-面试题讨论:最多假期的问题


      JobHunting
    标 题: 面试题讨论:最多假期的问题


    有4个国家,每个国家的假期不一样。
    有个旅行家只有每个周末可以出发去另外一个国家,有个限制条件比如上周在中国,这
    周在美国的话,下周就不可以再回中国。 但是可以一直呆在一个国家
    比如week 1在美国, week2 可以去中国,但是week3不可以回美国,只有week 4才可以
    再次去美国。
    但是可以从week1 到 week4 一直呆在美国。
    请问你怎么样设计旅行计划,可以保证一年有最多的holiday?

    --

    【返利网站】返利额度最高的海外购物返利网站Topcashback:平均返利7~10%,注册就送$10点我注册
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    22

    主题

    92

    帖子

    135

    积分

    注册会员

    Rank: 2

    积分
    135
    QQ
    发表于 2016-10-29 06:20:33 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    那试试匈牙利算法。

    【 在 yihead (yihead) 的大作中提到: 】
    : 周末出发表明一年一共52个选择。
    : 类似 这种int getMaxHolidays(List<int[]> holidays)



    --

    18

    主题

    77

    帖子

    110

    积分

    注册会员

    Rank: 2

    积分
    110
    QQ
    发表于 2016-10-29 06:32:30 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    周末出发表明一年一共52个选择。
    类似 这种int getMaxHolidays(List<int[]> holidays)

    【 在 sza (sza) 的大作中提到: 】
    : 题目不清楚。4个国家的假期和周末出发有什么关系?而且是先有holiday还是先有旅行
    : 计划?



    --

    10

    主题

    234

    帖子

    247

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    247
    QQ
    发表于 2016-10-29 07:41:27 | 显示全部楼层
    JobHunting
    标  题: 面试题讨论:最多假期的问题


    有4个国家,每个国家的假期不一样。
    有个旅行家只有每个周末可以出发去另外一个国家,有个限制条件比如上周在中国,这
    周在美国的话,下周就不可以再回中国。 但是可以一直呆在一个国家
    比如week 1在美国, week2 可以去中国,但是week3不可以回美国,只有week 4才可以
    再次去美国。
    但是可以从week1 到 week4 一直呆在美国。
    请问你怎么样设计旅行计划,可以保证一年有最多的holiday?

    --

    17

    主题

    89

    帖子

    119

    积分

    注册会员

    Rank: 2

    积分
    119
    QQ
    发表于 2016-10-29 08:47:12 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    Kuhn–Munkres算法?
    --

    31

    主题

    103

    帖子

    168

    积分

    注册会员

    Rank: 2

    积分
    168
    QQ
    发表于 2016-10-29 08:55:34 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    我开始也想这种方法,但是有点绕糊涂了。想举个例。
    week1:0 0 2 0
    week2: 0 0 2 0
    week3: 0 0 2 0
    week4: 2 2 2 5  //此时dp[3]成员都是8, 8, 8, 11
    week4:0 0 7 0  //此时按你的算法求解,最大值是2+2+2+2+7  = 15, 因为dp[3][3]
    (11)的值不能参与和dp[4][2] (7) 叠加。
    但是其实最大路径应该是2+2+0+5+7 = 16.
    不知道我这个反例举得对不.欢迎讨论。

    --

    26

    主题

    104

    帖子

    164

    积分

    注册会员

    Rank: 2

    积分
    164
    QQ
    发表于 2016-10-29 09:09:06 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    查找最多假期,存在重叠子问题, 而且有最优子结构(可以用反证法简单证明), 所
    以可以用动态规划解决。
    二维DP,一个维度是国家,另外一个维度是52,对于dp[i][52] = Max{dp[j][51] + 
    Holiday[j, 52]}, j取限制条件内的值。
    --

    6

    主题

    216

    帖子

    215

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    215
    QQ
    发表于 2016-10-29 09:34:57 | 显示全部楼层
    JobHunting
    标  题: Re: 面试题讨论:最多假期的问题


    题目不清楚。4个国家的假期和周末出发有什么关系?而且是先有holiday还是先有旅行
    计划?

    【 在 yihead (yihead) 的大作中提到: 】
    : 有4个国家,每个国家的假期不一样。
    : 有个旅行家只有每个周末可以出发去另外一个国家,有个限制条件比如上周在中国,这
    : 周在美国的话,下周就不可以再回中国。 但是可以一直呆在一个国家
    : 比如week 1在美国, week2 可以去中国,但是week3不可以回美国,只有week 4才可以
    : 再次去美国。
    : 但是可以从week1 到 week4 一直呆在美国。
    : 请问你怎么样设计旅行计划,可以保证一年有最多的holiday?



    --

    120

    主题

    1331

    帖子

    2718

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    2718
    QQ
    发表于 2016-11-28 02:49:35 | 显示全部楼层
    LZ帖子不给力,勉强给回复下吧
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -面试题讨论:最多假期的问题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -面试题讨论:最多假期的问题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

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