java - 第n个具有有效时间复杂度的二元回文

给定一个整数N，我试图找到第n个二进制回文式。我编写了以下代码，但是效率不高。在时间复杂度方面是否有更有效的方法？
我正在尝试将其作为在线问题进行处理，我应该在1秒或更短的时间内输出，但每次输入都需要2秒。

public static Boolean Palind(String n){
    String reverse = "";
    int length = n.length();
    for(int i = length - 1; i >=0;i--){
        reverse = reverse + n.charAt(i);
    }
    if(n.equals(reverse)){
        return true;
    }
    else{
        return false;
    }
}

public static int Magical(int n){
    ArrayList<Integer> res = new ArrayList<Integer>();
    for(int i = 1; i < Math.pow(2, n);i++){
        if(Palind(Integer.toBinaryString(i))){
            res.add(i);
        }
    }
    return res.get(n-1);
}

最佳答案

如果您通读The relevant OEIS entry (A006995)有很多不错的技巧。例如，使用a(2^n-1)=2^(2n-2)-1，您可以非常快速地跳到第（2n-1）个回文。

它还提供了几种实现。例如，Smalltalk实现的工作方式如下（请注意，第一个回文n的输入值1以0开头）：

public static final int nthBooleanPalindrome(int n) {
    if (n == 1) return 0;
    if (n == 2) return 1;
    int m = 31 - Integer.numberOfLeadingZeros(n);
    int c = 1 << (m - 1);
    int b;
    if (n >= 3*c) {
        int a = n - 3*c;
        int d = 2*c*c;
        b = d + 1;
        int k2 = 1;
        for (int i = 1; i < m; i++) {
            k2 <<= 1;
            b += a*k2/c%2*(k2 + d/k2);
        }
    }
    else {
        int a = n - 2*c;
        int d = c*c;
        b = d + 1 + (n%2*c);
        int k2 = 1;
        for (int i = 1; i < m - 1; i++) {
            k2 <<= 1;
            b += a*k2/c%2*(k2 + d/k2);
        }
    }
    return b;
}

关于java - 第n个具有有效时间复杂度的二元回文，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41312110/