用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 09:32:52 浏览: 115
这道题的题意是:给定一个二进制字符串 s 和一个整数数组 queries,其中 queries[i] = [firsti, secondi]。对于每个查询,要求找到 s 的最短子字符串,使得该子字符串对应的十进制值与 firsti 按位异或得到 secondi。如果存在多个答案,选择左端点最小的那个。
解决方案:
- 首先,我们可以遍历整个字符串 s,对于每个查询,将其对应的十进制值存储在一个字典中,key 为 firsti,value 为该十进制值对应的二进制字符串的左端点和右端点。
- 接着,我们可以从左到右遍历字符串 s,不断地更新每个查询对应的子字符串的最小长度。对于当前遍历到的字符,我们将它对应的十进制值与所有的 firsti 做异或运算,并在字典中查询对应的长度。如果查询到了对应的长度,我们更新该查询的最小长度,并将该查询对应的左端点和右端点更新为当前遍历到的字符的下标。
代码实现如下:
```
def shortestSeq(s, queries):
d = {}
for i, c in enumerate(s):
val = int(c)
for q in queries:
if (val ^ q[0]) in d:
left, right = d[val ^ q[0]]
if q[
阅读全文