我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数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),但它的效果比迄今为止任何其他建议都要好得多。
其他回答
我想我会先不看别人的答案就试试这个:
#include <stdio.h> #include <limits.h> #include <stdlib.h> int f(int n) { if(n > 0) { if(n % 2) return -(++n); else { return (--n); } } else { if(n % 2) return -(--n); else { return (++n); } } } int main(int argc, char* argv[]) { int n; for(n = INT_MIN; n < INT_MAX; n++) { int N = f(f(n)); if(N != -n) { fprintf(stderr, "FAIL! %i != %i\n", N, -n); } } n = INT_MAX; int N = f(f(n)); if(N != -n) { fprintf(stderr, "FAIL! n = %i\n", n); } return 0; }
输出:[无]
const unsigned long Magic = 0x8000000;
unsigned long f(unsigned long n)
{
if(n > Magic )
{
return Magic - n;
}
return n + Magic;
}
0~2^31
另一种方法是将状态保持在一位,并在负数的情况下翻转它,注意二进制表示。。。限制为2^29
整数ffn(整数n){
n = n ^ (1 << 30); //flip the bit
if (n>0)// if negative then there's a two's complement
{
if (n & (1<<30))
{
return n;
}
else
{
return -n;
}
}
else
{
if (n & (1<<30))
{
return -n;
}
else
{
return n;
}
}
}
根据您的平台,某些语言允许您在函数中保持状态。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),但它的效果比迄今为止任何其他建议都要好得多。
也许我错过了什么?
这不是简单的事情吗
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;}
丑陋但有效。