google mtv

求问最后一题的思路

14417335 发表于 2019-1-3 01:41
请问一下第二题DP以后怎么找最佳方案的combination呢？

我没想出来如何从DP的三维数组中找到这个path。 ...

想了一下，我来自己回答自己吧，如果有更好的办法请告知。

dp在计算的时候同时要记录你的最佳值的来源。这样最后可以从dp[item][cpu]倒着推回去。

（是二维DP。我上面说的三维说错了）

betterztt 发表于 2019-1-3 00:41
想问一下第一题就是算出左子树,右子树,以及整个树的节点-左-右=父节点的节点树,最后选取最大的吗
多谢LZ

对的，就是这个思路

14417335 发表于 2019-1-3 01:41
请问一下第二题DP以后怎么找最佳方案的combination呢？

我没想出来如何从DP的三维数组中找到这个path。 ...

看是否和同一列上一行记录的最高priority和相同，说明有没有选这个任务。我也是当时临时想的，不知道一般是不是这么做的

sakura328 发表于 2019-1-3 02:38
看是否和同一列上一行记录的最高priority和相同，说明有没有选这个任务。我也是当时临时想的，不知道一般 ...

多谢告知。你看看我上面的12楼。我觉得我的思路比较通用些。

14417335 发表于 2019-1-3 01:12
请问第四题我这么做可否达到时间复杂度的要求 O(N*M*M)？

source: abc      target: bababbababc

我先用window做的，但是没有记忆。后面优化是先遍历记录source里每个字母的所有位置在treeset，遍历target的时候记录当前字母在source的位置优化的，如果先用list记录用二分法，整体时间复杂度应该会更快一点，我主要是来不及就偷懒用treeset了。

sakura328 发表于 2019-1-3 02:44
我先用window做的，但是没有记忆。后面优化是先遍历记录source里每个字母的所有位置在treeset，遍历targe ...

厉害！这样你的复杂度就只有 O(N LogM)了。

第三轮是leetcode扒以吴，我用的bfs，问了下怎么优化hashmap少用一点空间，没想出来

用一个hashmap 存bfs时 算出来的结果。每次bfs时，check 一下这个数组（如果知道总共几个站） 或者 hashmap，如果之前算过，直接返回值。如果没算过，再bfs。

14417335 发表于 2019-1-3 02:51
厉害！这样你的复杂度就只有 O(N LogM)了。

达不到O(N lgM). 想一想当source 里有重复字符时。
worst应该是O(NM lgM).

elevator 发表于 2019-1-3 03:33
达不到O(N lgM). 想一想当source 里有重复字符时。
worst应该是O(NM lgM).

全是重复字符的时候，即worst才是O(N logM).  楼主的做法是BS每个N中字符在该list里的位置。你再想想。