1

最新のCodilityテストを試しましたか？

K-スパース数の定義に誤りがあり、混乱を招き、正しい進め方がわからなかったように感じました。したがって、Kスパース数を定義することから始めます。

2進数「100100010000」では、2つの連続する1の間に少なくとも2つの0があります。2進数「100010000100010」では、2つの連続する1の間に少なくとも3つの0があります。正の整数Nは、バイナリ表現の任意の2つの連続する1の間に少なくともK 0が存在する場合、Kスパースと呼ばれます。（私の強調）

したがって、最初に表示される数値100100010000は2スパースで、2番目の数値100010000100010は3スパースです。非常に単純ですが、アルゴリズムに組み込まれます。

関数を書く：

class Solution { public int sparse_binary_count(String S,String T,int K); }

それ、与えられた：

    string S containing a binary representation of some positive integer A,
    string T containing a binary representation of some positive integer B,
    a positive integer K.

[A..B]の範囲内のKスパース整数の数を返します（両端を含む）

次に、このテストケースを示します。

たとえば、S = "101"（A = 5）、T = "1111"（B = 15）、K = 2の場合、[5]の範囲に2つのスパース整数が2つしかないため、関数は2を返す必要があります。 ..15]、つまり「1000」（つまり8）と「1001」（つまり9）。

基本的に、8、つまり基数2の1000は、2進表現に2つの連続した数がない場合でも、2スパース数であると言っています。何が得られますか？ここで何かが足りませんか？

4

3 に答える 3

1

それを解決しようとしました。問題が「2の累乗」の数値の2進表現がデフォルトでKスパースであるという仮定は、やや混乱し、反対です。

私が理解したのは、8-> 1000は2の累乗3であるため、8は3のスパースです。16-> 10000 2乗4、したがって4スパース。

私たちもそれが真実であると仮定しています、そしてあなたが以下に興味があるなら、この問題のための私の解決策コード（C）です。2つの入力数値の間に2つの数値の累乗が含まれている場合、それを修正できるかどうかを確認しようとして、正しく処理されない場合があります。

int sparse_binary_count (const string &S,const string &T,int K) 
{
    char buf[50];
    char *str1,*tptr,*Sstr,*Tstr;
    int i,len1,len2,cnt=0;
    long int num1,num2;
    char *pend,*ch;

    Sstr = (char *)S.c_str();
    Tstr = (char *)T.c_str();
    str1 = (char *)malloc(300001);
    tptr = str1;

    num1 = strtol(Sstr,&pend,2);
    num2 = strtol(Tstr,&pend,2);

    for(i=0;i<K;i++)
    {
        buf[i] = '0';
    }
    buf[i] = '\0';

    for(i=num1;i<=num2;i++)
    {
        str1 = tptr;

        if( (i & (i-1))==0)
        {
            if(i >= (pow((float)2,(float)K)))
            {
                cnt++;
                continue;
            }
        }
        str1 = myitoa(i,str1,2);

        ch = strstr(str1,buf);
        if(ch == NULL)
            continue;
        else
        {
            if((i % 2) != 0)
                cnt++;
        }

    }
    return cnt;
}

    char*  myitoa(int val, char *buf, int base){


    int i = 299999;
    int cnt=0;

    for(; val && i ; --i, val /= base)  
    {
        buf[i] = "0123456789abcdef"[val % base];
        cnt++;
    }
    buf[i+cnt+1] = '\0';
    return &buf[i+1];

}
于 2012-02-01T21:52:07.350 に答える
1

テストの詳細には、この特定のケースを示す情報が含まれていました。この情報によると、の任意の累乗は、任意の2に対してKスパースと見なされますK。

これは、整数の二項演算によって簡単に解決できます。特定の整数より大きく、Tで表される整数よりも小さい（または等しい）Kスパース整数は見つからないこともわかります。

私が見る限り、チェックする整数が数億個あることもあるので、パフォーマンスにも多くの注意を払う必要があります。

Pythonで記述された私自身のソリューションは、広範囲の整数でも非常に効率的に機能し、多くの入力に対して正常にテストされましたが、失敗しました。結果はあまり説明的ではなく、質問内で必要に応じて機能しないと述べています（私の意見ではすべての要件を満たしていますが）。

于 2012-02-02T01:09:53.657 に答える
0 
/////////////////////////////////////
solutions with bitwise operators:
no of bits per int = 32 on 32 bit system,check for pattern (for K=2, 
like 1001, 1000) in each shift and increment the count, repeat this 
for all numbers in range.




///////////////////////////////////////////////////////

int KsparseNumbers(int a, int b, int s) {
    int nbits = sizeof(int)*8;
    int slen = 0;
    int lslen = pow(2, s); 

    int scount = 0;
    int i = 0;
    for (; i < s; ++i) {
      slen += pow(2, i);
    }
    printf("\n slen = %d\n", slen);

    for(; a <= b; ++a) {
    int num = a;
      for(i = 0 ; i < nbits-2; ++i) {
         if ( (num & slen) == 0 && (num & lslen) ) {
          scount++;
          printf("\n Scount = %d\n", scount);
          break;
         }
       num >>=1;
      }
    }
return scount;

}

int main() {

   printf("\n No of 2-sparse numbers between 5 and 15 = %d\n", KsparseNumbers(5, 15, 2));

 }
于 2013-03-14T00:43:55.463 に答える