1

您是否尝试过最新的 Codility 测试？

我觉得在定义什么是 K-Sparse 数时有一个错误，这让我感到困惑，我不确定正确的方法是什么。所以它从定义一个 K-Sparse 数开始：

在二进制数“100100010000”中，任何两个连续的 1 之间至少有两个 0。在二进制数“100010000100010”中，任何两个连续的 1 之间至少有三个 0。如果一个正整数 N在其二进制表示中任意两个连续的 1 之间至少有 K 个 0，则称为 K-sparse 。（我的重点）

所以你看到的第一个数字 100100010000 是 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，函数应该返回 2，因为在范围 [5 ..15]，即“1000”（即8）和“1001”（即9）。

基本上它是说 8 或以 2 为底的 1000 是一个 2 稀疏数，即使它的二进制表示中没有两个连续的数字。是什么赋予了？我在这里错过了什么吗？

4

3 回答 3

1

试图解决那个。默认情况下，问题关于“二的幂”数的二进制表示是 K 稀疏的假设有点令人困惑和相反。

我的理解是 8-->1000 是 2 次方 3 所以 8 是 3 稀疏的。16-->10000 2 power 4 ，因此 4 稀疏。

即使我们认为它是 true ，如果您对以下内容感兴趣，下面是我针对此问题的解决方案代码（C）。不能正确处理某些情况，其中两个输入数字之间涉及两个数字的幂，试图看看我是否可以解决这个问题：

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。

您可以简单地通过对整数进行二元运算来解决这个问题。您甚至可以说，您不会发现任何 K 稀疏整数大于某个特定整数且小于（或等于）由 T 表示的整数。

据我所知，您还必须非常注意性能，因为有时要检查数亿个整数。

我自己的解决方案，用 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 回答