网易互娱笔试题的Python代码

第一题是字符串缩写的题目，这道题只过了50%，剩下50%超时了。结束后跟同学讨论了下，她说用join函数会快一些，我也不知道是不是那儿的问题。我提交的是注释部分。

import sys
T = int(sys.stdin.readline().strip())

examples = []
for i in range(T):
    s = sys.stdin.readline().strip()
    examples.append(s)
for i in range(T):
    s = examples[i]
    ret, n = '', len(s)
    idx1, idx2 =  0, 1
    while idx1 < n and idx2 < n:
        # print(idx1, idx2)
        current = ord(s[idx1])
        while idx2 < n and ord(s[idx2]) - ord(s[idx2-1]) == 1:
            idx2 += 1
        if (idx2 - idx1) >= 4:
            # ret += s[idx1]
            # ret += '-'
            # ret += s[idx2-1]
            ret = ''.join([ret, s[idx1], '-', s[idx2]])
        else:
            # ret += s[idx1:idx2]
            ret = ''.join([ret, s[idx1:idx2]])
        idx1, idx2 = idx2, idx2 + 1
    if idx1 < n:
        ret += s[idx1:]
    print(ret)

第二题是服务器日志查询的题目，这道题过了90%。后来加了先对log按时间排序的操作，还是90%，看来日志本身就是按时间有序的。思路很直接。

import sys
N = int(sys.stdin.readline().strip())
logs = []
for i in range(N):
    line = sys.stdin.readline().split()
    line = [line[0], int(line[1]), line[2]]
    logs.append(line)

T =  int(sys.stdin.readline().strip())
examples = []
for i in range(T):
    dic = {}
    k =  int(sys.stdin.readline().strip())
    for j in range(k):
        param, con = sys.stdin.readline().split()
        if param != '--search':
            con = int(con)
        dic[param[2:]] = con
    examples.append(dic)

for i in range(T):
    dic = examples[i]
    for idx in range(N):
            if dic['search'] in logs[idx][2]:
                if 'hostid' in dic:
                    if logs[idx][1] == dic['hostid']:
                        break
                else:
                    break

    if idx == N-1:
        if  dic['search'] not in logs[-1][2]:
            print('ERROR')
        elif 'hostid' in dic:
            if dic['hostid'] != logs[-1][1]:
                print('ERROR')
    else:
        if 'before' in dic:
            if idx > dic['before']:
                start = idx - dic['before']
            else:
                start = 0
            for p in range(start, idx):
                print(logs[p][2])
        print(logs[idx][2])
        if 'after' in dic:
            if idx + dic['after'] > N:
                end = N
            else:
                end = idx + dic['after'] + 1
            for p in range(idx+1, end):
                print(logs[p][2])

第三题是X进制和Y进制的题目。这道题AC。

解题思路：针对单个测试用例[x, y, z]，我们用两个指针idx1和idx2分别指向字符串z的头和尾，则z[:idx1]和z[idx2:]分别是X进制数字和Y进制数字。两个指针都向中间移动：如果z[:idx1]>z[idx2:]，则idx2--；如果z[:idx1]<z[idx2]，则idx1++；如果二者相等且idx1+1<idx2，则idx1++,idx2--。移动的停止条件是idx1+1=idx2且z[:idx1]==z[idx2:]。

import sys
T = int(sys.stdin.readline().strip())
examples = []
for i in range(T):
    x, y, z = sys.stdin.readline().split()
    x, y = int(x), int(y)
    examples.append([x, y, z])

for i in range(T):
    x, y, z = examples[i]
    n = len(z)
    idx1, idx2 = 0, n-1
    ret1, ret2 = 0, 0
    if ord(z[idx1]) > 64:
        tmp = ord(z[idx1]) - 64 + 9
        ret1 = ret1 * x + tmp
    else:
        ret1 = ret1 * x + int(z[idx1])
    if ord(z[idx2]) > 64:
        tmp = ord(z[idx2]) - 64 + 9
        ret2 += tmp * (y ** (n - 1 - idx2))
    else:
        ret2 += int(z[idx2]) * (y ** (n - 1 - idx2))
    while idx1 < idx2:
        # print(idx1, idx2, ret1, ret2)
        if ret1 > ret2:
            idx2 -= 1
            if ord(z[idx2]) > 64:
                tmp = ord(z[idx2]) - 64 + 9
                ret2 += tmp * (y ** (n - 1 - idx2))
            else:
                ret2 += int(z[idx2]) * (y ** (n - 1 - idx2))
        elif ret1 < ret2:
            idx1 += 1
            if ord(z[idx1]) > 64:
                tmp = ord(z[idx1]) - 64 + 9
                ret1 = ret1 * x + tmp
            else:
                ret1 = ret1 * x + int(z[idx1])
        else:
            if idx1 + 1 == idx2:
                break
            else:
                idx1 += 1
                if ord(z[idx1]) > 64:
                    tmp = ord(z[idx1]) - 64 + 9
                    ret1 = ret1 * x + tmp
                else:
                    ret1 = ret1 * x + int(z[idx1])
                idx2 -= 1
                if ord(z[idx2]) > 64:
                    tmp = ord(z[idx2]) - 64 + 9
                    ret2 += tmp * (y ** (n - 1 - idx2))
                else:
                    ret2 += int(z[idx2]) * (y ** (n - 1 - idx2))
    print(ret1)