我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
这将在非常广泛的数字范围内发挥作用:
static int f(int n)
{
int lastBit = int.MaxValue;
lastBit++;
int secondLastBit = lastBit >> 1;
int tuple = lastBit | secondLastBit;
if ((n & tuple) == tuple)
return n + lastBit;
if ((n & tuple) == 0)
return n + lastBit;
return -(n + lastBit);
}
我最初的方法是使用最后一位作为检查位,以了解我们在第一次或第二次调用中的位置。基本上,我会在第一次调用后将此位设置为1,以向第二次调用发出第一次调用已经通过的信号。但是,这种方法被负数所击败,负数的最后一位在第一次调用期间已经到达1。
同样的理论适用于大多数负数的倒数第二位。但是,通常发生的情况是,大多数情况下,最后一位和第二位是相同的。它们要么都是负数的1,要么都是正数的0。
所以我的最后一个方法是检查它们是否都是1或都是0,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。
其他回答
这个想法已经在其他答案中使用过,但我把它融入了Python的一行:
def f(n):
return str(n) if type(n) == int else -int(n)
对于所有32位值(注意,-0是-2147483648)
int rotate(int x)
{
static const int split = INT_MAX / 2 + 1;
static const int negativeSplit = INT_MIN / 2 + 1;
if (x == INT_MAX)
return INT_MIN;
if (x == INT_MIN)
return x + 1;
if (x >= split)
return x + 1 - INT_MIN;
if (x >= 0)
return INT_MAX - x;
if (x >= negativeSplit)
return INT_MIN - x + 1;
return split -(negativeSplit - x);
}
基本上需要将每个-x=>x=>-x循环与y=>-y=>y循环配对。所以我把裂口的两边配对。
例如,对于4位整数:
0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
Lua:
function f(n)
if type(n) == "number" then
return (-number) .. ""
else
return number + 0
end
end
我有另一个解决方案,它可以在一半时间内工作:
def f(x):
if random.randrange(0, 2):
return -x
return x
我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成4个数的小集合:
1 → 2 3 → 4 5 → 6
↑ ↓ ↑ ↓ ↑ ↓ ...
-2 ← -1 -4 ← -3 -6 ← -5
这很容易翻译成代码。注意,偶数改变符号,奇数增加或减少1。在C#中,它看起来像这样:
public static int f(int x)
{
if(x == 0)
return 0;
if(x > 0)
return (x % 2 == 0) ? -x+1 : x+1;
// we know x is negative at this point
return (x % 2 == 0) ? -x-1 : x-1;
}
当然,您可以通过使用巧妙的技巧来缩短此方法,但我认为这段代码最好地解释了它本身。
然后是范围。32位整数的范围从-2^31到2^31-1。数字2^31-1、-2^31-1和-2^31超出了f(x)的范围,因为缺少数字2^31。