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

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

有什么想法吗?


当前回答

创建许多解的一种方法是注意,如果我们将整数划分为两个集合S和R

那么我们可以如下创建f:

如果x在R中,则f(x)=g(x)

如果x在S中,则f(x)=-invg(x)

其中invg(g(x))=x,所以invg是g的逆函数。

上面提到的第一个解决方案是分区R=偶数,R=奇数,g(x)=x+1。

我们可以取任意两个无限集合T,P s.T T+U=整数集合,取s=T+(-T),R=U+(-U)。

然后-S=S和-R=R通过它们的定义,我们可以将g取为从S到R的任何1-1对应关系,这必须存在,因为这两个集合都是无限的和可数的。

因此,这将为我们提供许多解决方案,但并非所有解决方案都可以编程,因为它们不会被有限地定义。

例如:

R=可被3整除的数字,S=不可被3除的数字。

然后我们取g(6r)=3r+1,g(6r+3)=3r+2。

其他回答

在PHP中

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}

我相信你能理解其他语言的这种方法的精神。为了让不使用弱类型语言的人更清楚,我明确地将其转换回int。对于某些语言,您必须重载该函数。

这个解决方案的妙处在于,无论您是从字符串还是整数开始,它都是有效的,并且在返回f(n)时不会明显改变任何内容。

在我看来,面试官在问,“这位应聘者是否知道如何标记数据以供以后操作”,以及“这位应聘人员是否知道如何在最少更改数据的情况下标记数据?”你可以使用双精度、字符串或任何其他你想使用的数据类型来实现这一点。

const unsigned long Magic = 0x8000000;

unsigned long f(unsigned long n)
{    
    if(n > Magic )
    {
        return Magic - n;
    }

    return n + Magic;
} 

0~2^31

int f( int n ){
    return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}
int f(int n)
{
  static long counter=0;
  counter++;
  if(counter%2==0)
    return -n;
  else
    return n;
}

少于50个字符(C#)

int f(int n) { return (n <= 0) ? n : f(-n); }

或更容易阅读:

static int f(int n) { 
  if (n <= 0)
    return n;
  else 
    return f(-n);
}

要测试

static void Main(string[] args) {
    for (int n = int.MinValue; n < int.MaxValue; n+=1) {
        Console.Out.WriteLine("Value: " + n + " Result: " + f(f(n)));
    }
}

它有效(假设我正确理解问题)