我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
在PHP中
function f($n) {
if(is_int($n)) {
return (string)$n;
}
else {
return (int)$n * (-1);
}
}
我相信你能理解其他语言的这种方法的精神。为了让不使用弱类型语言的人更清楚,我明确地将其转换回int。对于某些语言,您必须重载该函数。
这个解决方案的妙处在于,无论您是从字符串还是整数开始,它都是有效的,并且在返回f(n)时不会明显改变任何内容。
在我看来,面试官在问,“这位应聘者是否知道如何标记数据以供以后操作”,以及“这位应聘人员是否知道如何在最少更改数据的情况下标记数据?”你可以使用双精度、字符串或任何其他你想使用的数据类型来实现这一点。
其他回答
使用复数,您可以有效地将否定数字的任务分为两个步骤:
将n乘以i,得到n*i,n逆时针旋转90°再乘以i,得到-n
最棒的是,您不需要任何特殊的处理代码。只要乘以i就可以了。
但不允许使用复数。因此,您必须使用部分数据范围创建自己的虚拟轴。由于需要的虚(中间)值与初始值一样多,因此只剩下一半的数据范围。
我试图在下图中显示这一点,假设有符号的8位数据。您必须将其缩放为32位整数。初始n的允许范围为-64到+63。下面是函数对正n的作用:
如果n在0..63(初始范围)内,函数调用将添加64,将n映射到范围64..127(中间范围)如果n在64..127(中间范围)内,则函数从64中减去n,将n映射到范围0..-63
对于负n,函数使用中间范围-65..-128。
我认为这些问题的答案最好用图表直观地解释。当我们忽略零时,我们可以将整数分成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。
我相信这符合所有要求。没有什么规定参数必须是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;
}
}
int func(int a)
{
static int p = 0;
int ret = a;
if ( p ) ret *= -1;
p ^= 1;
return ret;
}
我的答案是正确的。。。50%的时间,所有的时间。
int f (int num) {
if (rand () / (double) RAND_MAX > 0.5)
return ~num + 1;
return num;
}