9.14 小米算法方向笔试（数组去除+卷积和互相关）

求点赞！我第二题没AC，也没找到哪里出了bug，欢迎讨论！

第一题：数组去数

给你一个整数数组 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)，卷积和互相关定义如下：

卷积：
$\sum_{i=0}^{\infty}x(i)h(n-i)$
互相关：
$\sum_{i=0}^{\infty}x(i)h(n+i)$

给定两个信号 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(',','')}")