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

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

有什么想法吗?


当前回答

根据您的平台,某些语言允许您在函数中保持状态。VB.Net,例如:

Function f(ByVal n As Integer) As Integer
    Static flag As Integer = -1
    flag *= -1

    Return n * flag
End Function

IIRC、C++也允许这样做。我怀疑他们正在寻找不同的解决方案。

另一个想法是,由于它们没有定义函数第一次调用的结果,因此可以使用奇数/均匀度来控制是否反转符号:

int f(int n)
{
   int sign = n>=0?1:-1;
   if (abs(n)%2 == 0)
      return ((abs(n)+1)*sign * -1;
   else
      return (abs(n)-1)*sign;
}

所有偶数的幅度加一,所有奇数的幅度减一。两次调用的结果大小相同,但在一次调用中,我们甚至交换了符号。在某些情况下,这不会起作用(-1,max或min int),但它的效果比迄今为止任何其他建议都要好得多。

其他回答

Lua:

function f(n)
    if type(n) == "number" then
        return (-number) .. ""
    else
        return number + 0
    end
end

在awk中,由于几乎没有任何信息被传递,因此必须求助于允许将状态信息作为函数返回的一部分传递的方法,而不会危及传递内容的可用性:

jot - -5 5 | mawk 'function _(__,___) { 

     return (__~(___=" ")) \
      \
      ? substr("",sub("^[ ]?[+- ]*",\
        substr(" -",__~__,index("_"___,___)-\
              (__~"[-]")),__))\
            (__~"[-]"?"":___)__\
      : (+__<-__?___:(___)___)__ 

  } BEGIN { CONVFMT=OFMT="%.17g" 
  } { 
      print "orig",           +(__=$(__<__))<-__?__:" "__,
            "f(n)....",        _(__),_(_(__)),_(_(_(__))),
                         _(_(_(_(__)))), _(_(_(_(_(__))))) 

  }' |gcat -n | lgp3 5 

 1  orig -5 f(n)....  -5   5  -5   5  -5
 2  orig -4 f(n)....  -4   4  -4   4  -4
 3  orig -3 f(n)....  -3   3  -3   3  -3
 4  orig -2 f(n)....  -2   2  -2   2  -2
 5  orig -1 f(n)....  -1   1  -1   1  -1

 6  orig  0 f(n)....   0  -0   0  -0   0
 7  orig  1 f(n)....   1  -1   1  -1   1
 8  orig  2 f(n)....   2  -2   2  -2   2
 9  orig  3 f(n)....   3  -3   3  -3   3
10  orig  4 f(n)....   4  -4   4  -4   4

11  orig  5 f(n)....   5  -5   5  -5   5

因此,这样做的限制是,只有整数或浮点值已经是字符串格式,可以在没有风险的情况下使用,因为额外的ASCII空间\040作为状态信息

这种方法的优点是

它愿意为您提供“负零”,对于绝对值小于2^53的整数,简单地添加加号,即+f(f(_))函数调用本身将具有隐式代表您完成类型铸造,结果值将再次为数字对于大整数,只需减去()任何前导空格轻松处理大整数,而不会丢失精度从类型转换为双精度浮点

`

    1   orig -99999999999999999999999999999999 
        f(n).... 
             -99999999999999999999999999999999   
              99999999999999999999999999999999
             -99999999999999999999999999999999   
              99999999999999999999999999999999  
             -99999999999999999999999999999999

 2  orig      -1239999999999999999999999999999 
    f(n)....  -1239999999999999999999999999999                   
               1239999999999999999999999999999
              -1239999999999999999999999999999
               1239999999999999999999999999999
              -1239999999999999999999999999999`

f(x)=在二维笛卡尔坐标系中围绕原点逆时针旋转90度的点(x)。仅一个数字x的输入被假定为(x,0),并且具有y=0的输出被提供为单个数字x。

object f: (object) x {
    if (x.length == 1)
        x = (x, 0)
    swap = x[0]
    x[1] = x[0]
    x[0] = -swap
    if (x[1] == 0)
        x = x[0]
    return x

这个怎么样:

do
    local function makeFunc()
        local var
        return function(x)
            if x == true then
                return -var
            else
                var = x
                return true
            end
        end

    end
    f = makeFunc()
end
print(f(f(20000)))

我相信这符合所有要求。没有什么规定参数必须是32位有符号整数,只有你传入的值“n”是。

long long f(long long n)
{
    int high_int = n >> 32;
    int low_int  = n & 0xFFFFFFFF;

    if (high_int == 0) {
        return 0x100000000LL + low_int;
    } else {
        return -low_int;
    }
}