骨骼onsite

xuqicx23 发表于 2019-12-23 08:46
不知道为什么我打的3d dp  i, j,n 保存之后就变成了[j][n]了。希望避免误会，是个3d的array

请问你的遍历顺序是什么样子的? 因为是四个方向, 你怎么保证, 打个比方, 当你走到右下角的时候, 这个点的dp指能包含一条从右上角来的路? 感觉这个可能不能用类似unique path的方式去写..

请问第三题详细点是怎么做？

请问第三题是什么思路？

第三题大家可以搜一下蓄水池采样算法，都看懂就肯定会了

棋盘cell变成六角形那个folluwup如何相对位置来表示得不太懂，楼主能再解释一下吗，感谢！已加米

请问最后一轮的那个返回访问率的function如何能优化到O(1)啊？感谢

"第三轮 coding, 给n个range以及一个n x n的board，要从每个range里面生成随机数字填到对应的column里，每个数字被生成的可能性要相同。"
你能举个例子吗？谢谢

"第四轮 coding, 两个人拿牌，你是先手。 游戏规则是每次可以拿1~3张牌。 现在给一个int array作为牌组，返回最佳策略能得到多少分。"这题是从数组两头拿牌吗？

第一题感觉是蠡口腰儿溜舅很像。那题是一维的，而且多个stay的操作。但那题的优化方法可以借鉴到这题：
不用存全部(2N+1)*(2N+1)个cell，存一半(N+1)*(N+1)就行了
因为走出去再回来距离最远且能影响到答案的走法就是先沿一个方向一直走 N/2 步，再用 N/2步回来。
再远的走法都回不到起点，所以记了也没意义。
这两题我就在想能不能推导出数学公式，给我N，O(1)时间就能算出来。感觉是可以的，无奈太菜推不出来。

请问第3轮用蓄水池抽样等于是从每个range里选n个数，这样复杂度是O(N)吧，N是range，amortized复杂度是N/n?怎么做到O(1)呢