当前位置: 首页 > 知识库问答 >
问题:

求一个数组中的三元组i,j,k的个数,使得索引为i到j-1的元素的异或等于索引为j到k的元素的异或

闻人修明
2023-03-14
for (int i = 0; i < arr.length; i++) {
            int xor = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                xor ^= arr[j];
                if (xor == 0) {
                    ans += (j - i);
                }
            }
        }
        finAns.append(ans + "\n");

共有1个答案

松雅健
2023-03-14

以下是基于Ciapan在问题描述下的评论的O(n)解决方案:

如果在指数I到J-1处的项的异或等于从J到K的异或,那么从I到K的异或等于零。对于任何这样的子数组[I.K],I+1和K-1之间的每一个J构成满足要求的三元组。从I到K的xor等于(从0到K的xor)xor(从0到I-1的xor)。所以我想你可能会找到序列所有可能的初始部分的异或-s,并寻找它们的相等对。

函数f是主要方法。brute_force用于验证。

import random

def brute_force(A):
  res = 0

  for i in xrange(len(A) - 1):
    left = A[i]
    for j in xrange(i + 1, len(A)):
      if j > i + 1:
        left ^= A[j - 1]
      right = A[j]
      for k in xrange(j, len(A)):
        if k > j:
          right ^= A[k]
        if left == right:
          res += 1

  return res

def f(A):
  ps = [A[0]] + [0] * (len(A) - 1)
  for i in xrange(1, len(A)):
    ps[i] = ps[i- 1] ^ A[i]

  res = 0
  seen = {0: (-1, 1, 0)}

  for  i in xrange(len(A)):
    if ps[i] in seen:
      prev_i, i_count, count = seen[ps[i]]
      new_count = count + i_count * (i - prev_i) - 1
      res += new_count
      seen[ps[i]] = (i, i_count + 1, new_count)
    else:
      seen[ps[i]] = (i, 1, 0)

  return res

for i in xrange(100):
  A = [random.randint(1, 10) for x in xrange(200)]
  f_A, brute_force_A = f(A), brute_force(A)
  assert f_A == brute_force_A
print "Done"
 类似资料:
  • 问题内容: 我在一个开始从事的项目中遇到了这段代码。原始开发人员不再可用,我对此一无所知: 产生值为。这是如何运作的? 什么是运算符? 什么是运算符? 什么是运算符? 什么是运算符? 问题答案: 什么是运算符? 那是两个运算符,一个是赋值运算符,一个是一元加号,它什么都不做。 您是否输入错了并表示compund赋值运算符? 什么是运算符? 还有两个运算符,一个为后递增,一个为加法(根据最大划分规则

  • 给我一个大小为n的正整数数组。对于数组中的每个索引I,我想找到最大的索引j,使得从索引I到j的数组元素之和小于或等于某个整数K。我只能用蛮力O(n^2)的方式来思考。我想知道是否有更有效的方法?

  • 问题内容: 在Python中,我们可以使用来获取数组中值的索引。 但是,当我尝试执行NumPy数组时: 我得到: AttributeError:“ numpy.ndarray”对象没有属性“ index” 我如何在NumPy数组上执行此操作? 问题答案: 使用来获得,其中一个给定的条件是指数。 例子: 对于称为的2D : 对于一维数组: 请注意,这也适用于像条件,,等等… 您也可以使用方法创建的子

  • 问题内容: 整数数组包含一些元素,以使每个元素比其前一个元素多1个或小于1个。现在给了一个数字,我们需要确定该数字在数组中首次出现的索引。需要优化线性搜索。它不是功课。 问题答案: 我的算法是这样的: p = 0 如果(A [p] == x)则idx = p并且算法完成,否则转到下一步 设置p + = | xA [p] | 转到2。 说A [p]> x。然后,由于A项增加或减少1,因此idx至少可

  • } 嗨,我已经在这方面工作了很长时间,我知道这似乎很容易,但我就是不能理解它....我只能更改getOverM()方法中的代码,我不能编辑其他方法。我想使用if语句,但我只是不知道如何编写一个代码来显示与m相比下一个最大的索引数。 插入GetOverm方法主体的代码。

  • 问题内容: 给定一个数组。我们如何在恒定时间内找到索引间隔中的元素总数。允许您使用额外的空间。 示例: A:3 2 4 7 1 -2 8 0 -4 2 1 5 6 -1 长度= 14 固定时间之和应为10。 问题答案: 如果您可以花费O(n)的时间来“准备”辅助信息,那么您就可以基于该信息来计算O(1)中的总和。 准备(O(n)): 查询(O(1))从编号为: 我认为这是意图,因为否则,这是不可能