看到的有道的某题。

Problem Statement

      

一个二进制序列由下面的伪代码生成：

string A = "0"

While (A的长度小于等于n)

    创建一个和A一样长度的字符串B

    For i=0,1,...length(A)-1

        If (i 是完全平方数)

            B[i] = 1-A[i]

        Else

            B[i] = A[i]

    令A = A + B (即将B拼接在A后面)

End While

Return A

请注意，在上面的伪代码中，A[i]和B[i]分别表示字符串A和B中下标为i的字符（下标编号从0开始）。对"完全平方数"的定义是，对于整数i，存在整数j，使得i= j *j，则称i为完全平方数。

下面具体说明序列生成的过程：如果n=7，则在每一轮迭代中，A的取值依次为：0, 01, 0110, 01101010，所以最终产生的二进制序列就是0,1,1,0,1,0,1,0

请返回上述序列中下标为n的数字（该序列的下标从0开始）

Definition

      

Class:

BinarySequence

Method:

getValue

Parameters:

int

Returns:

int

Method signature:

int getValue(int n)

(be sure your method is public)

      

 

Constraints

-

n 的取值大于等于0，小于等于2,000,000,000

Examples

0)

 

      

7

Returns: 0

原因参见题目描述。

1)

2

Returns: 1

2)      

8

Returns: 1

这一次，生成的序列为0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0.

3)      

11

Returns: 0

4)       

10

Returns: 1  

5)      

15

Returns: 0

 

 

耗费三五小时，作出一解法：

unsigned int getValue(const unsigned int & n)
{
 unsigned int truen=n+1;
 unsigned int pow2=1;
 //unsigned int pow2p=0;
 unsigned int changetimes=0;
 unsigned int currentPerfectsquare=0;
 unsigned int currentPerfectsquarebase=0;
 unsigned int lastcn=0xffffffff;
 while (pow2<=n)
 {
  unsigned int cn=n%pow2;
  if (lastcn!=cn)
  {
   while (currentPerfectsquare<cn)
   {
    currentPerfectsquare=++currentPerfectsquarebase*currentPerfectsquarebase;
   }
   if (currentPerfectsquare==cn)
   {
    changetimes++;
   }
  }
  lastcn=cn;
  pow2*=2;
  //pow2p++;
 }
 return changetimes%2;
}

为c/c++代码。算法复杂度O(log(n))，而且算法复杂度中的隐含系数也尽可能的减少了。

昨晚解决，今早发日志。

经测试比目前为止所见的算法都快……