腾讯笔试题

第一题

题解：和 LeetCode64. 最小路径和 类似的递归。用两个数组，一个储存正的最大值，另一个储存负的最大值即可。

grid = [
    [-1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
INF=10**9
MOD=10**9+7
m = len(grid)
n = len(grid[0])
P = [[-INF]*n for _ in range(m)]
N = [[INF]*n for _ in range(m)]
P[0][0] = grid[0][0]
N[0][0] = grid[0][0]
for i in range(m):
    for j in range(n):
        if i:
            if grid[i][j] >= 0:
                P[i][j] = grid[i][j]*P[i-1][j]
                N[i][j] = grid[i][j]*N[i-1][j]
            else:
                P[i][j] = grid[i][j]*N[i-1][j]
                N[i][j] = grid[i][j]*P[i-1][j]
        if j:
            if grid[i][j] >= 0:
                P[i][j] = max(grid[i][j]*P[i][j-1], P[i][j])
                N[i][j] = min(grid[i][j]*N[i][j-1], N[i][j])
            else:
                P[i][j] = max(grid[i][j]*N[i][j-1], P[i][j])
                N[i][j] = min(grid[i][j]*P[i][j-1], N[i][j])
print(P[m][n])

第二题

题解：
%20%5Cleft(%20a%5E2%2Bb%5E2%2Bab%20%5Cright)%C2%A0%0A#card=math&code=a%5E3-b%5E3%3D%5Cleft%28%20a-b%20%5Cright%29%20%5Cleft%28%20a%5E2%2Bb%5E2%2Bab%20%5Cright%29%C2%A0%0A)

如果直接计算的话，由于两个数之间的误差很小，会导致累积误差非常大，因此可以转化之后将 提取出来。

l = 1
r = 100
k = 15
ret = 0
for i in range(l, r+1):
    ret += pow(i+pow(10, -k), 1/3)-pow(i, 1/3)
print(ret)
ret = 0
pk = pow(10, -k)
for i in range(l, r+1):
    s = pow(i+pk, 2/3)+pow(i, 2/3)+pow((i+pk)*i, 1/3)
    ret += 1/s
ret *= pk
print(ret)
ret = 0
for i in range(l, r+1):
    ret += 1/(3*pow(i, 2/3))
ret *= pow(10, -k)
print(ret)

三种方法的输出分别为：

2.886579864025407e-15
3.833455974119704e-15
3.833455974119704e-15

第三题

题解：

用 F[n] 来记录从第1个小球一直摆到第 n 个小球一共有多少种方法。

容易列出状态转移方程：

%20%2BF%5Cleft%5B%20n-2%20%5Cright%5D%20*%5Cleft(%20k-1%20%5Cright)%C2%A0%0A#card=math&code=F%5Cleft%5B%20n%20%5Cright%5D%20%3DF%5Cleft%5B%20n-1%20%5Cright%5D%20%2A%5Cleft%28%20k-1%20%5Cright%29%20%2BF%5Cleft%5B%20n-2%20%5Cright%5D%20%2A%5Cleft%28%20k-1%20%5Cright%29%C2%A0%0A)

该方程分为两个部分考虑：对于最后三个小球 [n-2] [n-1] [n]

1. 最后两个小球[n-1] [n] 的颜色不同，此时只需 [n] 的颜色与 [n-1] 不同即可，方案数有 F[n-1]*(k-1) 种。
2. 最后两个小球[n-1] [n] 的颜色相同，此时只需 [n-1] [n] 的颜色与 [n-2] 不同即可，方案数有 F[n-2]*(k-1) 种。

此时方程可以继续化简：
%20%5E%7Bn-2%7D#card=math&code=f%5Cleft%5B%201%20%5Cright%5D%20%3Dk%0A%5C%5C%0Af%5Cleft%5B%202%20%5Cright%5D%20%3Dk%5E2%0A%5C%5C%0Af%5Cleft%5B%20n%20%5Cright%5D%20%3Df%5Cleft%5B%20n-1%20%5Cright%5D%20%2Bf%5Cleft%5B%20n-2%20%5Cright%5D%20%0A%5C%5C%0AF%5Cleft%5B%20n%20%5Cright%5D%20%3Df%5Cleft%5B%20n%20%5Cright%5D%20%2A%5Cleft%28%20k-1%20%5Cright%29%20%5E%7Bn-2%7D)

n = 10
k = 2
MOD = 10**9+7
# code 1
F = [0]*(n+3)
F[1] = k
F[2] = k**2
for i in range(3, n+1):
    F[i] = ((F[i-1]*(k-1)) % MOD+(F[i-2]*(k-1)) % MOD) % MOD
print(F[n])
# code 2
b = k
a = k**2
for i in range(3, n+1):
    a, b = a+b, a
print(a*pow(k-1, n-2, MOD))

第四题

题解：直接递归即可

def f(L):
    if len(L) == 0:
        return 0
    elif len(L) == 1:
        return L[0]
    val = (min(L)+max(L))//2
    Left = [i for i in L if i <= val]
    Right = [i for i in L if i > val]
    print(Left,Right)
    return sum(L)+f(Left)+f(Right)
L1 = [1, 2, 3,4]
print(f(L1-sum(L1)))

第五题

题解：目测直接模拟即可