c – 查找查找给定索引值的步骤

发布时间：2020-12-16 06:50:42 所属栏目：百科来源：网络整理

导读：我是新来的 – 我有一个问题,我在采访中被问到,对于我的生活,我无法绕过我的脑袋.我可以用while / for循环解决它,但是面试官明确要求不使用它我甚至与我的几个朋友讨论过但无法解决它.如果有人可以提供指针. 问题是：对于给定的数组 s[] = {5,1,4,2,3} 没有

我是新来的 – 我有一个问题,我在采访中被问到,对于我的生活,我无法绕过我的脑袋.我可以用while / for循环解决它,但是面试官明确要求不使用它我甚至与我的几个朋友讨论过但无法解决它.如果有人可以提供指针.

问题是：
对于给定的数组

s[] = {5,1,4,2,3}

>没有给出数组的长度.
>如果数组长度为5个内容
保证在0到5之间.
>没有重复
数字.

示例长度(s,3)
– a [3] = 4,a [4] = 2,a [2] = 0,a [0] = 5,a [5] = 3返回长度4.

对于给定条件写入子程序int length(s,3) – 找到找到给定值所需的步骤数 –

附加条件

>你不能使用任何循环语句,如for,while等等 –
>您不能使用任何全局或静态变量.
>您无法在此例程中调用其他例程
>您无法修改给定的函数参数 – 它仅保留长度(s,n)
>您也无法更改原始数组

解决方法

替代解决方案根本不修改数组,但在x的前16位内隐藏了一个额外的参数：

int length(int *s,int x){
    int start = (x >> 16) - 1;
    if (start < 0)
        start = x;
    if (s[x] == start)
       return 0;
    return 1 + length(s,((start + 1) << 16) + s[x]);   
}

如果数组中有太多元素,这将失败,但我怀疑任何其他递归解决方案在任何情况下都可能在该点上达到堆栈溢出.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!