亚麻OA 2021

skmdc1991 发表于 2021-1-30 04:42
DFS + Memo coin problem
Time: 4 * N where N = Max len of 4 array (reduced from brute force of N *  ...

这个倒是有一点点可能？  能不能详细说一下你得mem是存什么？  就是key是什么，value是什么？  我当时没想出来有什么好办法可以压时间复杂度得办法。

backtracking/DFS 会TLE吗

论坛匿名用户 发表于 2021-2-1 13:45
这个倒是有一点点可能？  能不能详细说一下你得mem是存什么？  就是key是什么，value是什么？  我当时没 ...

最basic的key 用 index + “，” + budget。 value用count。不过一般这种可以用dp iterative or dfs
+ memo的都可以用2d array来 represent。
我觉得要是纯dfs time complexity应该是b ^ n * (maxLen)
b = budget
n = 4 because given 4 array or given n array
maxLen = Max of size for 4 array

memo reduced to - b * n * maxLen

根据coin是s^n -> s*n
And
1335 Min job schedule dfs后就是n*n*d

你觉得呢？

skmdc1991 发表于 2021-2-12 06:50
最basic的key 用 index + “，” + budget。 value用count。不过一般这种可以用dp iterative or dfs
+  ...

budget的复杂度是10 ** 9

谢谢楼主分享，学习学习。

bydstand 发表于 2021-2-12 07:02
budget的复杂度是10 ** 9

那也还是得走一遍吧？可能像很多题网上的都需要mod下10 ^ 9 + 7. 因为worst case 只要combination里有低于budget就要loop一边。别的有什么办法？楼主最开始的log 的我觉得不feasible。 因为是在建于把其他3个array lock position在binary search最后一个。那其实每一个数都需要lock住其他三个。

skmdc1991 发表于 2021-2-12 12:16
那也还是得走一遍吧？可能像很多题网上的都需要mod下10 ^ 9 + 7. 因为worst case 只要combination里有低 ...

走一遍就是TLE，唯一可行的就是组合成两个10 ** 6的数组，遍历一个二分另一个，就是楼主最新说的解题思路，n*n*log n，n = 10 ** 3

这是社招的吗

三周前oa做过这个 我是四个list先排序 然后二分 类似3Sum 的解法 也过了 就是在找到不valid的值的时候要直接跳出循环 不然会超时

skmdc1991 发表于 2021-2-12 06:50
最basic的key 用 index + “，” + budget。 value用count。不过一般这种可以用dp iterative or dfs
+  ...

主要就是b太大 是 10××9 所以不管怎么弄只要是乘都超时的