讨论一道点餐公司面经

关于 pickup 和 deliver 的 follow up吧算是。

游客，本帖隐藏的内容需要积分高于 20 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

地理好像没见过，在刷题网的 讨论板块上见的。

补充内容 (2021-1-2 01:53):
这题要求 subarray。 最初描述里 写的中文： 子数组。可能有的朋友没有看到🤣

Stanial 发表于 2020-12-15 12:17
我不确定是不是理解了你的意思，这道题所求的是最长的有效path，如果memo[start][end]里面只是保存子数组 ...

我可能理解错了，所以问题是最长subarray还是subsequence？

Stanial 发表于 2020-12-15 12:22
我可能理解错了，所以问题是最长subarray还是subsequence？

最长subarray。 题目里写的是 子数组，可能不是英文，不是那么容易引起注意🤣

会不会和蠡口散而parenthesis的那道题差不多

agraynel 发表于 2020-12-1 15:06
会不会和蠡口散而parenthesis的那道题差不多

有一点儿像，但不完全一样
e.g.
1. ( ( ) )
2. P1 P2 D1 D3

1 是合理的，但是 2 就不行。

感觉应该是dp，但是 状态方程不好想。
P1 D1, 这是基本case，然后这个 P1 P2 D2 D1， 可以通过 里面的 P2 D2 得来。

剩下有些case 不太好判断，比如  P1 P2 D1 D2；P1 P2 D1 P3 D2 D3. 像这些交叉的 不好处理。
可以弄个hashmap，存P 的 index，遇到D的话，只能mark 为 potential 合理的，比如 对于 P2 D1 P3 D2, 遇到 D2，然后发现map里有P2，那只能说 P2 .. D2 这段有可能是合理的，后面再看到D3，然后发现有P3，还有 someway 再回来 revisit check 一下 P2 .. D2这段，才发现是合理的，这样才能 mark  整个是 合理的。

楼主加油 我没考到这个followup 考的是generate path。。

agraynel 发表于 2020-12-2 05:48
楼主加油 我没考到这个followup 考的是generate path。。

求另外两题 非常感谢！ 已加米哈哈

fernando 发表于 2020-12-2 05:57
求另外两题 非常感谢！ 已加米哈哈

全部高频面经题 最近三个月地里的帖子都有

fernando 发表于 2020-12-2 05:06
感觉应该是dp，但是 状态方程不好想。
P1 D1, 这是基本case，然后这个 P1 P2 D2 D1， 可以通过 里面的 P2  ...

我也觉得大概思路是这样。就是在确定了之前p的index之后，还需要在validate从p到现在的d是否valid。不清楚是否更有解，但这个解肯定是make sense的。

beat1percent 发表于 2020-12-3 06:06
我也觉得大概思路是这样。就是在确定了之前p的index之后，还需要在validate从p到现在的d是否valid。不清 ...

嗯 不知道有没有比较简洁或者 稍微 generic way。感觉会有不少corner case，而且容易写错😂

谢谢楼主提供资源，我这几天想了一下，终于写出来了，用了heap，complextiy 是 O(n log n), 楼主来评判下吧

游客，本帖隐藏的内容需要积分高于 30 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.