0914小米笔试-算法卷

选择题考的比较杂，花了30几分钟写完，过程很曲折，很多都是蒙的。

小米编程题处理输入输出比较麻烦，所以选择用python写。

编程题第一题：给一个数组Array，一个整数x。每次用x减去数组头或者数组尾，求使得x为0的最小操作次数。否则返回-1。

感觉是考察前缀子串和，用两个数组分别记录 A的正序前n个元素和、A的逆序前n个元素和。然后暴力即可。

A = input().split(",")
A[0] = A[0][1:]
A[-1] = A[-1][:1]
A = [int(x) for x in A]
# print(A)

n = int(input())
x = int(input())

B, C = [], []
summary = 0
for i in range(len(A)):
    if i == 0:
        B.append(A[i])
    else:
        B.append(A[i] + B[-1])

summary = 0
for i in reversed(range(len(A))):
    if i == len(A) - 1:
        C.append(A[i])
    else:
        C.append(A[i] + C[-1])

# print(B)
# print(C)
res = 1e9
for i in range(len(B)):
    for j in range(len(C)):
        if B[i] + C[j] == x:
            res = min(res, i + j + 2)
        elif B[i] + C[j] > x:
            break
if res == 1e9:
    print("-1")
else:
    print(res)

编程题第二题：坑爹的模拟题。求两个数组的线性卷积、相关性。题目很简略，就两个公式。然后样例没有解释。

其中线性卷积倒是比较容易理解，相关性搞了我十多分钟才搞明白，看题目看了20分钟。。

花了20分钟在本地写完，过了测试样例。但考试还剩最后一分钟的时，没来得及调试输出格式，所以0分，坑爹啊。

在此强烈吐槽题目的输入和输出。。

# 线性卷积 A[m] = {X[i] * Y[j]} , i + j = m , m >=2
# 互相关 B[m] = {X[i] * Y[j]}, i + j = m, m >=2, j从后往前

X = input().split(",")[1]
X = X.split(" ")
X = [int(x) for x in X]

H = input().split(",")[1]
H = H.split(" ")
H = [int(x) for x in H]

# print(X)
# print(H)

A, B = [], []
# 线性卷积
for m in range(len(X) + len(H) - 1):
    summary = 0
    for i in range(min(m+1, len(X))):
        # print("{}, {}".format(i, m-i))
        if m-i < len(H):
            summary = summary + X[i]*H[m-i]
    A.append(summary)

# 相关卷积
if len(X) > len(H):
    for i in range(len(X) - len(H)):
        H.append(0)
else:
    for i in range(len(H) - len(X)):
        X.append(0)
# print(H)
for m in range(len(X) + len(H) - 1):
    summary = 0
    # print(m)
    for i in range(min(m+1, len(X))):
        j = len(H) - 1 - (m-i)
        # print("{}, {}".format(i, j))
        if j >=0 and j < len(H):
            summary = summary + X[i]*H[j]
    B.append(summary)
    # break

print(len(A), end=",")
for i in A:
    print(i, end=" ")
print("")
print(len(B),end=",")
for i in B:
    print(i, end=" ")

#秋招笔试##小米23秋招笔试认真的吗#