骨骼onsite

第一题好像是这样，奇数次就返回0
偶数次 从这两个里面重复取combination n//2 次 [(-1, 0) (1, 0)] , [(0, -1) (0, -1)] ， 个数是 2**（n //2)
再在每种combination 算出所有排列 答案就是 2**（n //2)  * (n) !

第四轮看不懂

多谢楼主！第四轮是三张牌随机抽取吗还是始终只能抽最上面的？

小熊牛牛 发表于 2020-1-13 05:16
第一题好像是这样，奇数次就返回0
偶数次 从这两个里面重复取combination n//2 次 [(-1, 0) (1, 0)] , [(0 ...

一般来说，在全部n个元索中，如果有a个i、b个j, c个k.......个相同的元素，那么把n个元素排成一列的方法总数，可以通过以下公式进行计算：
n! / (a! + b! + c! + ...), 其中a + b + c + ... = n

对于这题，上下和左右分别是一对，所以用循环把所有上下，左右的组合加起来，应该就是答案了吧。
count = n! /(2! * (n - 2)!) + n! /(4! * (n - 4)!) + n! /(6! * (n - 6)!) + ... + n! / ((n - 2)! * 2!)

第四题在另外一帖里面也看过，感觉有点小歧义，按我的理解这道题是： 给一个array num[], 两个player，每个人一轮可以从array开头拿1-3个数，假设两个人都是optimal，问第一个人最多能拿多少分。
我一个简单的的想法就是从num的尾巴后面开始loop，另外用两个dp array A[]和B[] 来分别存 拿了几张牌 和 能拿多少分。
Initialize 是 B[length - 1] = num[length - 1], A[length -1] = 1;

那dp的关系就是
B[i] = Math.max( nums[i] + B[ A[i+1] + i + 1], nums[i] + nunms[i+1] + B[ A[i+2] + i + 2], nums[i] + nunms[i+1] + nums[i+2] + B[ A[i+3] + i + 3])
A[i]就看上一行里面到底取几张牌最大来决定是1，2还是3.
另外就是数组中有没有负数也会有点影响。按理说如果是牌的话应该没有负数才对。

drool 发表于 2019-12-24 12:52
我想这个题应该有个数学解吧？n是奇数不可能回到原点，偶数的话x,y方向成对出现的组合数即是解

貌似是的

匿名者 发表于 2020-1-2 15:29
第三题大家可以搜一下蓄水池采样算法，都看懂就肯定会了

我认为resolver sampling 那就不是range，而是a list of possible values

求问一下最后一轮什么思路啊