我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
对于所有32位值(注意,-0是-2147483648)
int rotate(int x)
{
static const int split = INT_MAX / 2 + 1;
static const int negativeSplit = INT_MIN / 2 + 1;
if (x == INT_MAX)
return INT_MIN;
if (x == INT_MIN)
return x + 1;
if (x >= split)
return x + 1 - INT_MIN;
if (x >= 0)
return INT_MAX - x;
if (x >= negativeSplit)
return INT_MIN - x + 1;
return split -(negativeSplit - x);
}
基本上需要将每个-x=>x=>-x循环与y=>-y=>y循环配对。所以我把裂口的两边配对。
例如,对于4位整数:
0 => 7 => -8 => -7 => 0
1 => 6 => -1 => -6 => 1
2 => 5 => -2 => -5 => 2
3 => 4 => -3 => -4 => 3
其他回答
这个是Python中的。适用于n的所有负值:
f = abs
MIN_INT不会失败:
int f(n) { return n < 0 ? -abs(n + 1) : -(abs(n) + 1); }
创建许多解的一种方法是注意,如果我们将整数划分为两个集合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。
我承认我会作弊,但还是符合要求。这是编程魔术,而不是数学。它适用于整个范围,-2^31除外。
int f(int n)
{
static bool eFlag = false; // Only executed once
eFlag = !eFlag;
return eFlag?-n:n;
}
在PHP中
function f($n) {
if(is_int($n)) {
return (string)$n;
}
else {
return (int)$n * (-1);
}
}
我相信你能理解其他语言的这种方法的精神。为了让不使用弱类型语言的人更清楚,我明确地将其转换回int。对于某些语言,您必须重载该函数。
这个解决方案的妙处在于,无论您是从字符串还是整数开始,它都是有效的,并且在返回f(n)时不会明显改变任何内容。
在我看来,面试官在问,“这位应聘者是否知道如何标记数据以供以后操作”,以及“这位应聘人员是否知道如何在最少更改数据的情况下标记数据?”你可以使用双精度、字符串或任何其他你想使用的数据类型来实现这一点。