9.14 小米算法方向笔试（数组去除+卷积和互相关）
求点赞！我第二题没AC，也没找到哪里出了bug，欢迎讨论！
#小米##小米笔试##小米23秋招笔试认真的吗#
第一题：数组去数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
输入：包含3行
第一行，数组nums（输入的格式和 python 的列表相同，例如 [1, 2, 3, 4]。用 python 的 eval() 函数可以直接读入为列表）
第二行，数组nums的大小
第三行，给定的正整数x
输出：
输出最小操作数
解法：阅读题意，发现并不需要实际去操作数组（不要被题干里这句话误导到：“需要修改数组以供接下来的操作使用”）。只需要在左端和右端分别找一些数，使它们的和等于 x ，找到数字的数量最少的一个方案即可。因此这题类似于固定sum的滑动窗口问题。
先从右边开始遍历。每遍历到一个数，把它的后缀和，以及后缀长度存在字典 right_sum 里，直到后缀和大于 x 为止。
然后从左边遍历数组。同样是记录前缀和 s，然后在 right_sum 里寻找 x - s。每找到一次，说明前 i + 1 个数和后面 right_sum[x-s] 个数之和为 x，可以更新一次最终答案。注意：数字的总个数必须小于 n，否则不是可行方案。
如果没有找到任何和为 x 的方案，输出-1。
nums = eval(input())
n = int(input())
x = int(input())
right_sum = {}
s = 0
for i in range(n):
s += nums[- i - 1]
right_sum[s] = i + 1
if s > x:
break
ans = float('inf')
s = 0
for i in range(n):
s += nums[i]
if right_sum.get(x - s) != None:
t = right_sum.get(x - s) + i + 1
if t <= n:
ans = min(t, ans)
print(ans if ans < float('inf') else -1) 第二题：实现卷积和互相关计算（通过83%）
给定两个信号 x(n) 和 h(n)，卷积和互相关定义如下：
卷积：
h(n-i))
互相关：
h(n%2Bi))
互相关：
给定两个信号 x 和 n，分别输出它们的卷积和互相关函数。输出取在 -2147483648~ 2147483647之间。在计算互相关时，需要将短的信号后面补0后在计算。
输入：
x长度，x 中的数字。比如：7,10 13 16 19 22 25 28
h长度，h 中的数字。比如：3,20 22 24
输出：
卷积。比如：9,200 480 846 1044 1242 1440 1638 1216 672
互相关。比如：13,0 0 0 0 240 532 870 1068 1266 1464 1662 1116 560
解法：卷积函数直接根据公式，模拟即可。注意把输出取在 -2147483648~ 2147483647之间。
计算互相关，先按照要求补全0。然后把 h 颠倒过来，计算 x 和它的卷积即可。
我只过了83%的测试点，大佬们可以帮忙找找代码问题，或是没考虑全的地方 QwQ
n1, x = input().strip().split(',')
n2, h = input().strip().split(',')
x = [int(n) for n in x.split()]
h = [int(n) for n in h.split()]
n1, n2 = int(n1), int(n2)
def conv(xx, hh):
c = []
for i in range(len(xx) + len(hh) - 1):
s = 0
for j in range(i, -1, -1):
if i - j in range(len(xx)) and j in range(len(hh)):
s += xx[i - j] * hh[j]
if s < -2147483648:
s = -2147483648
if s > 2147483647:
s = 2147483647
c.append(s)
return c
a = conv(x, h)
if n1 < n2:
x.extend([0] * (n2 - n1))
else:
h.extend([0] * (n1 - n2))
h.reverse()
b = conv(x, h)
print(f"{len(a)},{str(a)[1:-1].replace(',','')}")
print(f"{len(b)},{str(b)[1:-1].replace(',','')}") #小米##小米笔试##小米23秋招笔试认真的吗#
查看16道真题和解析
