Google kickstart Round G 2020

首次参加Google kick start的线上比赛，获得了1337/6700(提交了答案的选手)的成绩，提升空间还是比较大。第3题的Test3本应该过的。之前也是很久没有刷HackerRank了。这里的提交方式和HackerRank的很相似。好处是可以用自己的编辑器来做题，相比于LeetCode中的编辑器更好一点，之前用LeetCode的Vim编辑模式老是错误地显示光标模式。不过这次因为用例不知道怎么用Vim调，所以暂时用了CodeRunner来写的。

Kick_Start

给定字符串S，求有多少种字符串是以`KICK`开头，`START`结尾的。

方法一：比较简单，由于读题花的时间比较长，而且不确定用例是否严格，担心5长度的切片过不了大的测试用例。所以提交地比较慢。

def solve(s):
    k = ans = 0
    for i in range(len(s)):
        head = s[i:i+5]
        if head.startswith('KICK'):
            k += 1
        elif head.startswith('START'):
            ans += k
    return ans

Maximum Coins

求二维矩阵中斜边（左到右）最大的路径和。

方法一：这题也比较简单，直接就过了。

1
2
3

def solve(g, n):
    return max(sum(g[j][j+i] for j in range(n) if 0<=i+j<n)
               for i in range(-n+1, n))

Combination Lock

有这么W个密码锁，锁上数字是从1~N。给你一个锁的初始状态，问最小需要多少步能将这些锁上的数字调成一样。

这题比赛的时候Case3没有跑过，TLE了。但是原理上基本都想对了。此题和LeetCode上462很像，但是那题比较简单，因为没有环。

比赛时没有过的代码：

from collections import deque
T = int(input())

def solve(ary):
    i, n = 0, len(ary)
    return sum(ary[~i]-ary[i] for i in range(n//2))
        
for case in range(1, T+1):
    W, N = map(int, input().split())
    wheels = sorted(map(int, input().split()))
    q = deque(wheels)
    ans = float('inf')
    cur = solve(q)
    for _ in range(W):
        l, r = (W-1)//2, (W)//2
        a, b = q[0], q[r]
        left = q.popleft()
        q.append(left + N)
        c, d = q[l], q[-1]
        cur += (d-c) - (b-a)
        ans = min(ans, cur)
    print('Case #{}: {}'.format(case, ans))

按照理论来说是件复杂度是一样的，不知道为什么就过不了。

正确的写法，滑动窗口就能过，按理说，双端队列首位的原子操作应该和这个时间复杂度一样，不知道为什么一直超时。

from collections import deque
T = int(input())

def solve(ary):
    i, n = 0, len(ary)
    return sum(ary[~i]-ary[i] for i in range(n//2))
        
for case in range(1, T+1):
    W, N = map(int, input().split())
    wheels = sorted(map(int, input().split()))
    wheels = wheels + [num+N for num in wheels]
    cur = ans = solve(wheels[:W])
    for i in range(W):
        l, r = W//2, (W+1)//2
        cur += wheels[i] + wheels[i+W] - wheels[i+r] - wheels[i+l]
        ans = min(ans, cur)
    print('Case #{}: {}'.format(case, ans))

双端队列中间取值的时间复杂度是O(n)，而不是O(1)。这是我一直忽略的一个问题。所以在W此循环中取了两个中间的值。还有使用solve求中位数时还用了双端队列。这个solve方法在最大数据集下执行时间就是1s！！这是我用Pycharm中profile run两个方法比较后找到的问题所在。终于将这个疑惑解决了，以后可以避免踩坑了。