用目标按位与值查找子数组

本文介绍了用目标按位与值查找子数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 给出大小为 N 的数组 A 和整数 P ，找到子数组 B = A [i ... j] ，使 i< = j ，计算子数组元素的按位值，例如 K = B [i]& B [i + 1]& ...& B [j] 。 输出 | KP | 的最小值> K 。解决方案这里还有另一种准线性算法，混合了 因此您可以计算 A [i]& A [i + 1]& ...& A [I + N-1] 仅执行 log N 个操作。 这里是管理计数器的方式：如果 计数器是 C0，C1，... Cp 和 Ck 是 Ck0，Ck1，... Ckm ， 然后 Cpq ... C1q，C0q 是 {A [i]，A [i + 1]，...，A [j-1]} 。 位级实现（在python中）；所有位都是并行管理的。 def add（counter，x）：k = 0 而x：x，计数器[k] = x& counter [k]，x ^ counter [k] k + = 1 def sub（counter，x）：k = 0 而x：x，counter [k] = x& 〜counter [k]，x ^ counter [k] k + = 1 def val（counter，count）：＃return A [i]& ....&如果count = j-i，则为A [j-1]。 k = 0 res = -1 而计数：如果计数％2> 0：res& =计数器[k] 其他：res& =〜counter [k] 计数// = 2 k + = 1 返回res 和算法： defsolve（A，P）：计数器= np.zeros（32，np.int64）＃最多4Go n = A.size i = j = 0 K = P＃触发填充缓冲区 mini = np.int64（2 ** 63-1） 而i 如果K sub（counter，A [i]）i + = 1 else：＃填充缓冲区 add（counter，A [j ]）j + = 1 如果j> i： K = val（计数器，计数） X = np.abs（K-P）$ b如果mini>为$ b X：mini = X else：K = P＃重置K return mini val ， sub 和 add 是 O（ln N），因此整个过程是 O（N ln N） 测试： n = 10 ** 5 A = np.random。 randint（0，10 ** 8，n，dtype = np.int64） P = np.random.randint（0，10 ** 8，dtype = np.int64） ％timesolve（A，P）墙壁时间：0.8 s 出：452613036735 numba编译版本（用 @ numba.jit 装饰4个函数）快了200倍（5毫秒）。 Given an array A of size N and an integer P, find the subarray B = A[i...j] such that i <= j, compute the bitwise value of subarray elements say K = B[i] & B[i + 1] & ... & B[j].Output the minimum value of |K-P| among all possible values of K. 解决方案 Here an other quasi-linear algorithm, mixing the yonlif Find subarray with given sum problem solution with Harold idea to compute K[i,j]; therefore I don't use pre-processing which if memory-hungry. I use a counter to keep trace of bits and compute at most 2N values of K, each costing at most O(log N). since log N is generally smaller than the word size (B), it's faster than a linear O(NB) algorithm. Counts of bits of N numbers can be done with only ~log N words :So you can compute A[i]&A[i+1]& ... &A[I+N-1] with only log N operations. Here the way to manage the counter: if counter is C0,C1, ...Cp, and Ck is Ck0,Ck1, ...Ckm,Then Cpq ... C1q,C0q is the binary representation of the number of bits equal to 1 among the q-th bit of {A[i],A[i+1], ... ,A[j-1]}. The bit-level implementation (in python); all bits are managed in parallel. def add(counter,x): k = 0 while x : x, counter[k] = x & counter[k], x ^ counter[k] k += 1def sub(counter,x): k = 0 while x : x, counter[k] = x & ~counter[k], x ^ counter[k] k += 1def val(counter,count): # return A[i] & .... & A[j-1] if count = j-i. k = 0 res = -1 while count: if count %2 > 0 : res &= counter[k] else: res &= ~counter[k] count //= 2 k += 1 return resAnd the algorithm :def solve(A,P): counter = np.zeros(32, np.int64) # up to 4Go n = A.size i = j = 0 K=P # trig fill buffer mini = np.int64(2**63-1) while i<n : if K<P or j == n : # dump buffer sub(counter,A[i]) i += 1 else: # fill buffer add(counter,A[j]) j += 1 if j>i: K = val(counter, count) X = np.abs(K - P) if mini > X: mini = X else : K = P # reset K return minival,sub and add are O(ln N) so the whole process is O(N ln N)Test :n = 10**5A = np.random.randint(0, 10**8, n, dtype=np.int64)P = np.random.randint(0, 10**8, dtype=np.int64)%time solve(A,P)Wall time: 0.8 sOut: 452613036735A numba compiled version (decorate the 4 functions by @numba.jit) is 200x faster (5 ms). 这篇关于用目标按位与值查找子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！