旷视算法3 笔试交流 python 0.9 0.6 0.3

第一题0.9未通过所有用例：判断 ‘-1 0 1’，其中0可以表示任意数，能够构成等差为1的等差数列

import sys

while sys.stdin.readline().strip():
    line = sys.stdin.readline().strip()
    values = list(map(int,line.split()))
    values.sort()

    l,r = len(values),-1
    for i in range(len(values)):
        if values[i] == 0:
            l = min(l,i)
            r = max(r,i)
    if r > -1:
        res = r - l + 1
        values = values[:l] + values[r+1:]

    flag_print = 0
    for i,v in enumerate(values):
        if i == 0:
            continue
        if i > 0 and values[i-1] == values[i]:
            flag_print = 1
            print('Invalid')
            break
        if values[i] - values[i-1] == 1:
            continue
        res -= (values[i]-values[i-1] - 1)
        if res < 0:
            flag_print = 1
            print ('Invalid')
            break
    if flag_print == 0:
        print('Valid')

第二题0.6超时：给一个矩阵M*N，怎么样通过第一行到最后一行代价最小

import sys

line = sys.stdin.readline().strip()
values = list(map(int,line.split()))

M,N = values

a = []

for _ in range(M):
    line = sys.stdin.readline().strip()
    values = list(map(int, line.split()))
    a.append(values)

# print(M)
# print(N)
# print(a)

dp = [[float('inf')] * N for _ in range(M)]
dp[-1] = a[-1]

for i in range(M-2,-1,-1):
    for j in range(N):
        dp[i][j] = min(dp[i][j],dp[i+1][j] + a[i][j])
        tmp = a[i][j]
        for k in range(j-1,-1,-1):
            tmp += a[i][k]
            dp[i][j] = min(dp[i][j],dp[i+1][k]+tmp)
        tmp = a[i][j]
        for k in range(j+1,N):
            tmp += a[i][k]
            dp[i][j] = min(dp[i][j],dp[i+1][k]+tmp)
print(min(dp[0]))

第三题0.3超时，且忘了取余：s='FRF'表示不等关系，N=len(s)，把{0,1,2,...,N}填入，有多少种情况

import sys


def helper(pre, tmp, line):
    if not tmp:
        global res
        res += 1
        return

    for i, t in enumerate(tmp):
        if line[0] == 'R':
            if pre < t:
                helper(t, tmp[:i] + tmp[i + 1:], line[1:])
            else:
                continue
        if line[0] == 'F':
            if pre > t:
                helper(t, tmp[:i] + tmp[i + 1:], line[1:])
            else:
                continue


while True:
    line = sys.stdin.readline().strip()
    if not line:
        break

    l = len(line)

    tmp = list(range(0, l + 1))

    res = 0

    for i in range(len(tmp)):
        helper(tmp[i], tmp[:i] + tmp[i + 1:], line)

    print(res)

#笔试题目##旷视#