如何让编程更快[Keypad_Sticky_Note]

Question

键盘粘滞便笺

跟班们把布林教授的一些秘密安全地锁起来了。至少他们是这么认为的。事实上，他们非常自信，他们甚至在锁的键盘上贴上了密码提示粘贴纸。

该锁要求您在键盘中输入一对非负整数(a，b)。由于整数可能高达20亿，您可以从便签中寻求帮助。

便签纸上写着两个数字，但即使是小跟班也知道不会把密码放在上面。他们实际上写下了和(他们将其标记为s)和密码整数对(a，b)的逐位异或(xor，标记为x)。这样，他们只需要记住一个。如果他们在减法上有困难，他们可以使用逐位异或。

也就是说，我们有s= a+b和x= a^b (其中^是逐位异或运算)。

使用你的自动黑客设备，每次尝试输入一个猜测都需要几毫秒。由于您在被发现之前只有很短的时间，因此您想知道在尝试所有组合之前可能需要多长时间。多亏了便签，你现在可以消除某些组合，甚至不需要在键盘上输入它们，而且你可以准确地找出解锁可能需要多长时间-在最坏的情况下。

编写一个名为answer(s，x)的函数，用于查找具有目标sum和xor的对(a，b)的数量。

例如，如果s=10和x=4，则(a，b)的可能值是(3，7)和(7，3)，因此answer将返回2。

如果为s=5和x=3，则没有可能的值，因此answer将返回0。

S和x至少为0，最多为20亿。

语言

要提供Python解决方案，请编辑要提供solution.py解决方案的solution.java

测试用例

输入：(int) s= 10 (int) x=4输出：(int) 2

输入：(int) s=0 (int) x=0输出：(int) 1

public static int answer(int s, int x) {
    List<Integer> num = new ArrayList<>();
    int a;
    int b;
    int sum;
    int finalans;

    for(int i = 0; i <=s; i++){
        for(int e = 0; e <= s; e++){
            sum = i + e;
            if(sum == s){
                if((i^e) == x){
                    if(!num.contains(i)){
                        num.add(i);
                    }
                    if(!num.contains(e)){
                        num.add(e);
                    }
                }
            }
        }
    }

    finalans = num.size();
    if((finalans%2) == 0){
        return finalans*2;
    } else if(!((finalans%2) == 0)){
        return finalans;
    }
    return 0;

}

我的代码可以工作，但是当s和x变得太大时，它需要花费太长的时间。我怎样才能让这个程序运行得更快？

Answer 1

您可以通过认识到对于传入状态(xor数字、和数字、传入进位)存在有限数量的传出状态(传出进位)来解决此问题。您可以使用if条件处理每个状态，并使用递归来计算组合的总数。您可以使用memoization来提高递归的效率。我下面的解决方案在O(m)时间内解决了这个问题，其中m是您的number数据类型中的二进制位数。由于问题指定了m = 32 (整数)，因此从技术上讲，这是一个O(1)解决方案。

如果你有任何问题，请告诉我。我尝试在代码中添加有用的注释来解释各种情况。

public class SumAndXor {
    public static void main(String[] args) {
        int a = 3;
        int b = 7;

        int sum = a + b;
        int xor = a ^ b;

        System.out.println(answer(sum, xor));
    }

    private static final int NOT_SET = -1;

    // Driver
    public static int answer(int sum, int xor) {
        int numBitsPerInt = Integer.toBinaryString(Integer.MAX_VALUE).length() + 1;
        int[][] cache = new int[numBitsPerInt][2];

        for (int i = 0; i < numBitsPerInt; ++i) {
            cache[i][0] = NOT_SET;
            cache[i][1] = NOT_SET;
        }

        return answer(sum, xor, 0, 0, cache);
    }

    // Recursive helper
    public static int answer(int sum, int xor, int carry, int index, int[][] cache) {
        // Return memoized value if available
        if (cache[index][carry] != NOT_SET) {
            return cache[index][carry];
        }

        // Base case: nothing else to process
        if ((sum >> index) == 0 && (xor >> index) == 0 && carry == 0) {
            return 1;
        }

        // Get least significant bits
        int sumLSB = (sum >> index) & 1;
        int xorLSB = (xor >> index) & 1;

        // Recursion
        int result = 0;

        if (carry == 0) {
            if (xorLSB == 0 && sumLSB == 0) {
                // Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
                // sum is 0 and the incoming carry is 0, both [0, 0] and [1, 1] are valid. We
                // recurse with a carry of 0 to represent [0, 0], and we recurse with a carry of
                // 1 to represent [1, 1].
                result = answer(sum, xor, 0, index + 1, cache) + answer(sum, xor, 1, index + 1, cache);
            } else if (xorLSB == 0 && sumLSB == 1) {
                // Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
                // sum is 1 and the incoming carry is 0, neither [0, 0] nor [1, 1] is valid.
                result = 0;
            } else if (xorLSB == 1 && sumLSB == 0) {
                // Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
                // sum is 0 and the incoming carry is 0, neither [0, 1] nor [1, 0] is valid.
                result = 0;
            } else if (xorLSB == 1 && sumLSB == 1) {
                // Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
                // sum is 1 and the incoming carry is 0, both [0, 1] and [1, 0] is valid. We
                // recurse with a carry of 0 to represent [0, 1], and we recurse with a carry
                // of 0 to represent [1, 0].
                result = 2 * answer(sum, xor, 0, index + 1, cache);
            }
        } else {
            if (xorLSB == 0 && sumLSB == 0) {
                // Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
                // sum is 0 and the incoming carry is 1, neither [0, 0] nor [1, 1] is valid.
                result = 0;
            } else if (xorLSB == 0 && sumLSB == 1) {
                // Since the XOR is 0, the binary digits are either [0, 0] or [1, 1]. Since the
                // sum is 1 and the incoming carry is 1, both [0, 0] and [1, 1] are valid. We
                // recurse with a carry of 0 to represent [0, 0], and we recurse with a carry of
                // 1 to represent [1, 1].
                result = answer(sum, xor, 0, index + 1, cache) + answer(sum, xor, 1, index + 1, cache);
            } else if (xorLSB == 1 && sumLSB == 0) {
                // Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
                // sum is 0 and the incoming carry is 1, both [0, 1] and [1, 0] are valid. We
                // recurse with a carry of 0 to represent [0, 1], and we recurse with a carry
                // of 0 to represent [1, 0].
                result = 2 * answer(sum, xor, 1, index + 1, cache);
            } else if (xorLSB == 1 && sumLSB == 1) {
                // Since the XOR is 1, the binary digits are either [0, 1] or [1, 0]. Since the
                // sum is 1 and the incoming carry is 1, neither [0, 1] nor [1, 0] is valid.
                result = 0;
            }
        }

        cache[index][carry] = result;

        return result;
    }
}

Answer 2

谷歌说，这太耗时了，因为你的算法运行在O(n^2)，而谷歌希望它运行在O(lg )。如果你问我，这对于一个3级的挑战来说太难了。我有过更简单的4级考试，这个问题的解决方案完全不是你所期望的。实际上，在正确答案中，您甚至不会将值设置为(a，b)，也不会将(a，b)与(S，x)进行比较。在你看到并理解解决方案之前，这与逻辑背道而驰。

无论如何，它有助于在2D图形或Excel电子表格中绘制正确的答案，使用S表示行，x表示列(将零留空)。然后，寻找模式。这些数据点实际上形成了一个Sierpinski三角形(参见http://en.wikipedia.org/wiki/Sierpinski_triangle)。

您还会注意到，一列中的每个数据点(大于零)对于该列中的所有实例都是相同的，因此给定x值，只要对应于S值的行与三角形中的一个数据点相交，您就会自动知道最终答案应该是什么。您只需要确定S值(行)是否与列x处的三角形相交。

甚至列中的值也形成从0到x的模式: 1，2，2，4，2，4，4，8，2，4，4，8，2，4，4，8，8，8，16...我相信你能想出办法的。

这里是“给定x的最终值”方法以及大部分剩余的代码(在Python中……Java的过于冗长和复杂)。您只需要编写三角形遍历算法(我不会泄露这一点，但这是在正确方向上的坚实推动)：

def final(x, t):
    if x > 0:
        if x % 2: # x is odd
            return final(x / 2, t * 2)
        else: # x is even
            return final(x / 2, t)
    else:
        return t

def mid(l, r):
    return (l + r) / 2

def sierpinski_traverse(s_mod_xms, x. lo, hi, e, l, r):
    # you can do this in 16 lines of code to end with...
    if intersect:
        # always start with a t-value of 1 when first calling final in case x=0
        return final(x, 1)
    else:
        return 0

def answer(s, x):
    print final(x, 1)

    if s < 0 or x < 0 or s > 2000000000 or x > 2000000000 or s < x or s % 2 != x % 2:
        return 0
    if x == 0:
        return 1

    x_modulus_size = 2 ** int(math.log(x, 2) + 2)
    s_mod_xms = s % x_modulus_size
    lo_root = x_modulus_size / 4
    hi_root = x_modulus_size / 2
    exp = x_modulus_size / 4    # exponent of 2 (e.g. 2 ** exp)

    return sierpinski_traverse(s_mod_xms, x, lo_root, hi_root, exp, exp, 2 * exp)


if __name__ == '__main__':
    answer(10, 4)

Answer 3

尝试将num更改为HashSet。你也可以在最后清理if/else。

例如：

public static int answer(int s, int x) {
    HashSet<Integer> num = new HashSet<>();
    int a;
    int b;
    int sum;
    int finalans;

    for(int i = 0; i <=s; i++){
        for(int e = 0; e <= s; e++){
            sum = i + e;
            if(sum == s){
                if((i^e) == x){
                    num.add(i);
                    num.add(e);
                }
            }
        }
    }

    finalans = num.size();
    if((finalans%2) == 0){
        return finalans*2;
    } else {
        return finalans;
    }        
}