编码二进制周期

Question

这是一个考题，我想一定有更有效的方法。（我也知道有一种方法可以直接转换二进制数，而不需要经过二进制字符串，但我不知道如何转换）。

这就是问题所在：

给出了一个由Q字符组成的非空零索引字符串S。该字符串的周期是最小的正整数P，使得：

P≤ Q/2和S[K]=S[kp]表示0≤ K

例如，8是“Codilityco”的时期。如果M是N的二进制表示的周期，则正整数M是正整数N的二进制周期。

例如，4是955的二进制周期，因为955的二进制表示是“1110111011”，它的周期是4；另一方面，102没有二进制周期，因为它的二进制表示是“1100110”，它没有周期。

编写一个函数：

int solution(int N);

给定一个正整数N，返回N的二进制周期。函数应该返回−如果N没有二进制周期，则为1。

例如，给定N=955，函数应该返回4，给定N=102，函数应该返回−1，如上例所述。

假设：

N是[1..100000000]范围内的整数。

复杂性：

>

预计最坏情况下的空间复杂度为O（log（N））。

公共类第二个任务{public int solution（int N）{String binario=Integer.tobinarysting（N）；

      int minimo = Integer.MAX_VALUE;
      int Q = binario.length();

      for(int P=1;P<Q;P++)
      {
          float der =Q/2;
          if(P<=der)
          {
              int delta = Q-P;
              int fail=0;
              for(int K=0;K<delta;K++)
              {
                  if(binario.charAt(K)!=binario.charAt(K+P))
                  {
                      K=delta;
                      fail=1;
                  }
              }
              if(fail!=1)
              {
                  if(P<minimo)
                  {
                      minimo=P;
                  }
              }
          }
      }
      if(minimo==Integer.MAX_VALUE)
      {
          return -1;
      }
      return minimo;
  }    

}

可能代码效率极低，但当我们进行时，我会修复它。应该是简单的：-（。

编辑：在@Eran的帮助下，这是新代码。运行时间几乎相同，但现在很干净。

public class SecondTask {
    public int solution(int N) 
    {
        String binario = Integer.toBinaryString(N);
        
        int minimo = Integer.MAX_VALUE;
        int Q = binario.length();
        System.out.println("binario: "+binario);
        for(int P=1;P<Q/2;P++)
        {
            System.out.print("P: "+P);
            int delta = Q-P;
            int fail=0;
            for(int K=0;K<delta;K++)
            {
                System.out.print(" "+binario.charAt(K));                
                if(binario.charAt(K)!=binario.charAt(K+P))
                {

                    K=delta;
                    fail=1;
                }
            }
            System.out.println("");
            if(fail!=1)
            {
                return P;
            }
        }
        
        if(minimo==Integer.MAX_VALUE)
        {
            return -1;
        }
        return minimo;
    }    
}

Answer 1

您的实现并不理想。

例如

for(int P=1;P<Q;P++)
{
    float der =Q/2;
    if(P<=der)

你可以写

for(int P=1;P<=Q/2;P++)
{

这可以为您节省一些什么都不做的迭代。

我要做的另一个改变是替换：

        if(fail!=1)
        {
            if(P<minimo)
            {
                minimo=P;
            }
        }

与：

        if(fail!=1)
        {
           return P;
        }

因为一旦你找到了一个有效周期的P，你就可以停止搜索。

然而，这些改进不会改变时间复杂性，而且您的实现已经满足了复杂性要求。

数字N由O（log（N））位表示，因此Q=O（log（N））。

您的实现在一个循环中有一个循环，每个循环的大小都小于Q。因此，最坏情况下的时间复杂度受Q^2的限制，即O（log（N）^2），这是所需的复杂度。

还满足了O（log（N））的空间复杂度，因为您使用的唯一非恒定长度存储是N的二进制字符串表示（binario变量），其长度为O（log（N））。

我不确定是否有更好的时间复杂度的实现。