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

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

有什么想法吗?


当前回答

这里有一个我从未见过的变体。因为这是ruby,所以32位整数的东西就不见了(当然可以添加检查)。

def f(n)
    case n
    when Integer
        proc { n * -1 }
    when Proc
        n.call
    else
        raise "Invalid input #{n.class} #{n.inspect}"
    end
end

(-10..10).each { |num|
    puts "#{num}: #{f(f(num))}"
}

其他回答

return x ^ ((x%2) ? 1 : -INT_MAX);

有些类似,但我只是想写下我的第一个想法(用C++)

#include <vector>

vector<int>* f(int n)
{
  returnVector = new vector<int>();
  returnVector->push_back(n);
  return returnVector;
}

int f(vector<int>* n) { return -(n->at(0)); }

仅使用重载使f(f(n))实际调用两个不同的函数

:D

boolean inner = true;

int f(int input) {
   if(inner) {
      inner = false;
      return input;
   } else {
      inner = true;
      return -input;
   }
}

这将在非常广泛的数字范围内发挥作用:

    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,这意味着在大多数情况下这是第一次调用。如果最后一位与第二个最后一位不同,那么我假设我们在第二次调用,然后简单地重新反转最后一位。显然,对于使用最后两位的非常大的数字来说,这不起作用。但是,它再次适用于非常广泛的数字。

创建许多解的一种方法是注意,如果我们将整数划分为两个集合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。