新鲜热乎facebook onsite

最后一题看上去类似burst balloons, dp解法

Find the longest vocation days 是不是類似sliding window, 根據遇到的F和T還有可用的假日調整front, end
O(n)
畢竟是要求連續的最長假日

不知道有沒有誤解?

谢谢楼主分享！

第5轮的第二题的最优解应该是用sliding windows。老规矩贴下我自己写的答案，欢迎大家指出bug：）

def find_longest_vocation(day_off, pto):
    nums_of_days_off = [0]
    for i in range(len(day_off)):
        if day_off[i]:
            nums_of_days_off.append(nums_of_days_off[-1])
        else:
            nums_of_days_off.append(nums_of_days_off[-1] + 1)
    last_work_day = 0
    last_vocation_day = 0
    res = -2 ** 31
    while last_vocation_day < len(day_off):
        if day_off[last_vocation_day]:
            last_vocation_day += 1
            res = max(res, last_vocation_day - last_work_day)
        else:
            if nums_of_days_off[last_vocation_day] - nums_of_days_off[last_work_day] < pto:
                res = max(res, last_vocation_day - last_work_day)
                last_vocation_day += 1
            else:
                last_work_day += 1
    return res


if __name__ == '__main__':
    day_off = [False, False, True, True, False, False, True, True, True, False]
    pto = 3
    print(find_longest_vocation(day_off, pto))

补充内容 (2018-12-7 13:18):
大体思路就是用nums_of_days_off记录下第i天一共有多少天是off days 类似pre sum数组

我又来发题号啦

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

最后, 谢谢楼主哈~~~

补充内容 (2018-12-14 07:07):
修改一下, 内存循环 if (pto < 0) 应该改成 while (pto < 0)

过五关斩六将，真不容易过。

什么是“连behavior 都不是no”？

连behavior 都是no。。多到一个字。。不要在意细节。。

max pto :  蠡口1004