网易互联网算法编程题分享

1. 橡皮泥斑马

• 思路：滑动窗口法，无论反转几次形成的字符串都是s+s的子串或逆序子串，只需在s+s中查找最长连续反转子串长度(不超过n)即可；时间复杂度O(n)
• 代码：

s = raw_input()
n = len(s)
l = r = res = 0
while l < n and r < l + n - 1:
    if s[(r+1)%n] != s[r%n]:
        r += 1
    else:
        l, r, res = r + 1, r + 1, max(res, r-l+1)

print max(res, r-l+1)

2. 翻转翻转

• 思路：讨论每个节点的邻接点个数为偶数的个数即可，时间复杂度O(1)
• 代码：

t = input()
for _ in xrange(t):
    n,m = map(int,raw_input().split())
    print [n-2,1][n==1] * [m-2,1][m==1]

3. 香槟塔

• 思路：逐层下流直至层数超出总层数或者下流量为0；单次调整时间复杂度O(n)
• 代码：

n,m = map(int,raw_input().split())
a = map(int,raw_input().split())
vs = [0] * n 
for _ in xrange(m):
    tmp = map(int,raw_input().split())
    if tmp[0] == 1:
        print vs[tmp[1]-1]
    else:
        x,v = tmp[1] - 1, tmp[2]
        while v and x < n:
            vs[x], v = min(a[x],vs[x]+v), max(0, vs[x]+v-a[x])
            x += 1