3/26/2016 vmware oa @ hackerrank 60min

WayneBit 发表于 2016-4-15 06:17
https://www.hackerrank.com/challenges/detect-the-domain-name

非常感谢，就是原题
但是最后只做了四道题，其中一题还有一个test case没过。。。不知道有没有面试

mrhohn 发表于 2016-4-3 22:04
好吧，查了下，的确是有O(N + K)解法的…

http://stackoverflow.com/questions/24518682/count-subseq ...

第二题自己写了一个，确实O(N+K)就行，觉得比这个的稍简洁好理解一点…就是一个dp吧…

def kSeq(a,k):
    ret = 0
    mods = [0] * k
    for i in a:
        m = i%k
        mods = mods[-m:] + mods[:-m]
        mods[m] += 1
        ret += mods[0]
    return ret


哎这两天要做VM的OA了，现在改成60min5个题了……不知道题目是不是一样。。

哦不对。。我这不是O(N+K)， 是O(NK)的。。改一下不要每次更新mods。。只要找个变量记一下当前的值应该加在哪一位上就行了…

其实第二题 o（n） 就可以搞了  比如说 1 2 3 4 1  那么先求出累计和的数组 就是 1 2 6 10 11.
然后再遍历一遍，每个数都除以3，把余数寸成一个数组 1 2 0  1 2.。。找出余数相同的即可