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

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

有什么想法吗?


当前回答

有些类似,但我只是想写下我的第一个想法(用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))实际调用两个不同的函数

其他回答

从来没有人说过f(x)必须是同一类型。

def f(x):
    if type(x) == list:
        return -x[0]
    return [x]


f(2) => [2]
f(f(2)) => -2

它通过保存状态来作弊,但它有效,将操作分成两部分:-n=(~n+1)对于整数

int f(int n) {
    static int a = 1;
    a = !a;
    if (a) {
        return (~n);
    } else {
        return (n+1);
    }
}

使用问题中给出的信息,您可以

从2-完成转换为符号位表示如果设置了最后一位,则翻转符号位和最后一位;否则,只翻转最后一位转换回2-完成。

所以你基本上是奇数->偶数->奇数或偶数->奇数->偶数,只对偶数更改符号。唯一不适用的数字是-2^31

代码:

function f(x) {
  var neg = x < 0;
  x = Math.abs(x) ^ 1;
  if (x & 1) {
    neg = !neg;
  }
  return neg ? -x : x;
}

也许我错过了什么?

这不是简单的事情吗

    function f(n)
    {
        if(n ==0 || n < 0){return n;}
        return n * -1;
    }

编辑:

所以我错过了阅读问题,嗯哼,所以:

    function f(n)
    {
        if(!c(n,"z")&&!c(n,"n")){if(n==0){return "z"+n;}return "n"+n;}
        if( c(n,"z")){return 0;}return parseInt(n.replace("n",""))*-1;
    }
    function c(x,y){return x.indexOf(y) !==-1;}

丑陋但有效。

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