谷歌 出了一点小插曲的山景城昂赛

三亩一分地儿 发表于 2019-9-9 15:42
没人问第四题吗 感觉挺难得 没有思路，哪位高人指点下？

没理解错的话 可以二分   参考LC410

请问楼主第一题怎么做的？
我的想法是，如果矩阵n * n，原问题直接暴力算也就O(n)
follow up 1 的话，一开始把入口到出口的映射全算出来，O(n^2)， 之后query只用O(1)?
follow up 2的话，一开始把每一层到下一层的映射，以及到上一层的映射都算出来，O(n^2)， update的时候由修改的点往上更新，O(n)。query的时候还是O(1)?

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

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

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

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

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

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

三亩一分地儿 发表于 2019-9-9 15:42
没人问第四题吗 感觉挺难得 没有思路，哪位高人指点下？

面试官给了一点提示：先写一个function，输入一周最多开会时长，输出能否在n周内完成所有的会议。然后原问题就可以利用这个function进行二分。

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

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

Zetecx 发表于 2019-9-9 23:49
请问取log是什么意思？
我的理解是以 currency 那个题目为背景但是不用原方法做（因为原来的方法保证了只 ...

Dijkstra可解， 取log得意思就是把乘法改成加法

第四题 大家可以看丝要令

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

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