时间戳

首页 > 解决方案 > BIT WISE AND 的完美广场

c++ - BIT WISE AND 的完美广场

问题描述

对子数组进行按位与运算时，如何优化计算连续子数组的完全平方数的解决方案。时间复杂度应该是 O(n) 或 O(n*logn)。

这是天真的方法

int a[]={1,2,3,4,5,6};
int l=2,r=5;
int c=0;  // for counting the subsets 
for(int i=l;i<=r;i++){
    int val=a[i];
    for(int j=i;j<=r;j++){
        val=val&a[j];
        if(isPerfectSquare(val)){
            c+=1;
        }
    }
}

标签： c++bitwise-andcontiguous

解决方案

您可以制作数字位的 Trie 数据结构并继续插入 pre_and。此外，请记住让 Node 结构存储数字的索引，以便您可以针对给定范围运行查询。现在剩下的就是计算 AND 结果是否是一个完美的正方形。自己试试吧。提示就足够了。你可以参考这个

推荐阅读