gpt4 book ai didi

arrays - 在没有 for 循环的情况下查找数组的排列

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:00:00 24 4
gpt4 key购买 nike

我在 LinkedIn 群组上看到这个面试问题 here

总结一下,如果我有一个数组

[1,2,3,4,5]

并输入

3

我需要输出

[1,2,3], [3,2,1], [2,3,1], [2,1,3], [1,3,2], [3,1,2], [2,3,4], [4,3,2],...

排名不分先后。

我一直在想这个问题。我想出了各种不同的解决方法,但所有方法都使用 for 循环。

我认为很明显,为了消除循环,它必须是递归的。

我以为我已经接近于递归地对数组进行分区并连接元素,但非常沮丧,我最终需要另一个 for 循环。

我开始认为这是不可能的(这是不可能的,否则为什么面试问题?)。

有任何想法或链接吗?可能的输出量应该是 5PN,其中 N 是输入。

最佳答案

以下递归算法将尝试打印 {1,.., n} 的每个子集。这些子集通过以下双射与 0 和 2^n-1 之间的数字一对一:对于 0 和 2^n-1 之间的整数 x,如果 x 的第一位设置为,则关联包含 1 的集合one, 2 如果 x 的第二位设置为 1, ..

void print_all_subsets (int n, int m, int x) {
if (x==pow(2,n)) {
return;
}
else if (x has m bits set to one) {
print the set corresponding to x;
}
print_all_subsets(n,m,x+1);
}

您需要使用 n = 5(在您的情况下)、m=3(在您的情况下)和 x = 0 来调用它。

然后您需要实现两个函数“打印对应于 x 的集合”和“x 将 m 位设置为 1”而不使用 for 循环...但这很容易再次使用递归完成。

但是,我认为这更具挑战性——完全消除 for 循环没有意义,有意义的是以巧妙的方式使用它们。

关于arrays - 在没有 for 循环的情况下查找数组的排列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30509702/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com