我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成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。

其他回答

类似于python中的函数重载解决方案:

def f(number):
 if type(number) != type([]):
  return [].append(number)
 else:
  return -1*number[0]

备选方案:静态数据成员

容易的:

function f($n) {
   if ($n%2 == 0) return ($n+1)*-1;
   else return ($n-1);
}

使用全局。。。但事实如此?

bool done = false
f(int n)
{
  int out = n;
  if(!done)
  {  
      out = n * -1;
      done = true;
   }
   return out;
}

这个问题并没有说明函数f的输入类型和返回值必须是什么(至少不是你给出的方式)。。。

…只是当n是32位整数时,f(f(n))=-n

那么,怎么样

Int64 f(Int64 n)
{
    return(n > Int32.MaxValue ? 
        -(n - 4L * Int32.MaxValue):
        n + 4L * Int32.MaxValue);
}

如果n是32位整数,则语句f(f(n))==-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