-1

サブ配列でビットごとの AND 演算が実行されるときに、隣接するサブ配列の完全な二乗の数を数えるソリューションを最適化する方法。Time Complexity は 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;
        }
    }
}

4

2 に答える 2

2

数値のビットの Trie データ構造を作成し、pre_and を挿入し続けることができます。また、特定の範囲に対してクエリを実行できるように、ノード構造に数値のインデックスを格納することを忘れないでください。あとは、AND の結果が完全平方かどうかを計算するだけです。自分で試してみてください。ヒントは十分です。あなたはこれを参照することができます

于 2018-09-13T18:25:44.570 に答える