java - Codility二进制周期

Question

这是一个Codility考试的问题，我认为一定有更有效的方法来做这件事。 (而且我知道有一种方法可以直接转换二进制数，而无需通过 BinaryString，但我不知道如何)。

问题是:

给定一个由 Q 个字符组成的非空零索引字符串 S。该字符串的周期是满足以下条件的最小正整数 P:

P ≤ Q/2 和对于 0 ≤ K < Q − P，S[K] = S[K+P]。

例如，8 是“codilitycodilityco”的句号。一个正整数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..1,000,000,000] 范围内的整数。

复杂度:

• 预期的最坏情况时间复杂度为 O(log(N)^2);

• 预期的最坏情况空间复杂度为 O(log(N))。

  公共(public)类SecondTask{公共(public) int 解决方案(int N){String binario = Integer.toBinaryString(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))。

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