运维开发网

掌握前缀表达式真的可以为所欲为!

运维开发网 https://www.qedev.com 2021-01-12 08:26 出处:51CTO 作者:mb5ff981d806017
题目地址(1310.子数组异或查询)https://leetcode-cn.com/problems/xor-queries-of-a-subarray题目描述有一个正整数数组arr,现给你一个对应的查询数组queries,其中queries[i]=[Li,Ri]。对于每个查询i,请你计算从Li到Ri的XOR值(即arr[Li]xorarr[Li+1]xor...xorarr[Ri])作为本次查询

题目地址(1310. 子数组异或查询)

https://leetcode-cn.com/problems/xor-queries-of-a-subarray

题目描述

有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。

对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri])作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1:

输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]

输出:[2,7,14,8]

解释:

数组中元素的二进制表示形式是:

1 = 0001

3 = 0011

4 = 0100

8 = 1000

查询的 XOR 值为:

[0,1] = 1 xor 3 = 2

[1,2] = 3 xor 4 = 7

[0,3] = 1 xor 3 xor 4 xor 8 = 14

[3,3] = 8

示例 2:

输入:arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]

输出:[8,0,4,4]

提示:

1 <= arr.length <= 3 * 10^4

1 <= arr[i] <= 10^9

1 <= queries.length <= 3 * 10^4

queries[i].length == 2

0 <= queries[i][0] <= queries[i][1] < arr.length

暴力法

思路

最直观的思路是双层循环即可,果不其然超时了。

代码

class Solution:

   def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:

 res = []

       for (L, R) in queries:

           i = L

           xor = 0

           while i <= R:

               xor ^= arr[i]

               i += 1

           res.append(xor)

       return res

前缀表达式

思路

比较常见的是前缀和,这个概念其实很容易理解,即一个数组中,第 n 位存储的是数组前 n 个数字的和。

对 [1,2,3,4,5,6] 来说,其前缀和可以是 pre=[1,3,6,10,15,21]。我们可以使用公式 pre[

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号