按键式便签
小黄人们将一些布尔教授的秘密安全地锁在了某处。或者他们这么认为。实际上,他们非常自信,甚至在锁的按键上贴了一个密码提示便利贴。
这个锁需要你在按键上输入一对非负整数 (a, b)。由于这些整数可能高达 20 亿,因此你需要查看提示便利贴以获得帮助。
提示便利贴上写有两个数字,但即使是小黄人也知道不要把密码放在那里。他们实际上写下了密码整数对 (a, b) 的和(称其为 s)和按位异或(xor,标记为 x)。这样,他们只需要记住一个数字。如果他们对减法感到困难,他们可以使用按位异或。
即,我们有 s = a+b 和 x = a^b(其中 ^ 是按位异或运算)。
使用你的自动化黑客设备,每次猜测尝试需要几毫秒。由于你很快就会被发现,所以你想知道在尝试所有组合之前可能需要多长时间。由于提示便利贴,你现在可以在不必要输入它们到按键上的情况下消除某些组合,并且可以在最坏情况下找出破解锁所需的确切时间。
编写一个名为 answer(s, x) 的函数,该函数查找具有目标和和异或的数字对 (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 要提供 Java 解决方案,请编辑 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变得很大时,程序运行时间太长了。我该如何让这个程序运行更快?
[0; s]
中取出a
,计算b = s - a
,检查异或,并在必要时添加到列表中。返回list.size() * 2
。 - user2418306