用python写一下这道题,给你一个 二进制字符串 s 和一个整数数组 queries ,其中 queries[i] = [firsti, secondi] 。 对于第 i 个查询,找到 s 的 最短子字符串 ,它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ,换言之,val ^ firsti == secondi 。 第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点(下标从 0 开始),如果不存在这样的子字符串,则答案为 [-1, -1] 。如果有多个答案,请你选择 lefti 最小的一个。 请你返回一个数组 ans ,其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。 子字符串 是一个字符串中一段连续非空的字符序列。
时间: 2023-02-26 12:32:53 浏览: 49
这是一道字符串题目。题目给出了一个二进制字符串s和一个整数数组queries,每一项queries[i] = [firsti, secondi]表示第i个查询。查询要求在s中找到最短的一个子字符串,使得它对应的十进制值val满足val ^ firsti == secondi(即按位异或)。最终要求返回一个数组ans,其中ans[i] = [lefti, righti]表示第i个查询的答案,如果不存在这样的子字符串,答案为[-1, -1],如果有多个答案,选择lefti最小的一个。
下面是一种python实现方法:
```
def find(s, queries):
n = len(s)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] ^ (1 << (n - i)) if s[i - 1] == '1' else prefix[i - 1]
res = []
for q in queries:
firsti, secondi = q
tmp = {}
for i in range(n + 1):
val = prefix[i] ^ firsti
if val in tmp:
res.append([tmp[val], i - 1])
break
tmp[prefix[i]] = i
else:
res.append([-1, -1])
return res
```
在这段代码中,首先求出字符串s的前缀和,然后对于每个查询,使用一个字典tmp记录出现的前缀和,如果当前的val在字典中出现过,说明已经找到答案,直接返回结果,否则更新字典。最后如果找不到答案,返回[-1, -1