我有一个数组-
$hubnode[1]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[2]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[3]=array(2,10,11,15);
$hubnode[4]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[5]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);
$hubnode[6]=array(2,10,11,13,15);
$hubnode[7]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);
$hubnode[8]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);
我需要通过从每行取1个数字来得到每一个唯一的8个成员的组。
在一组中，所有的8位数字都是唯一的。
计数时没有组不能重复。例如，有效的组有:-
美元集团[1]= 1,2,3,4,11日,5日,8;
美元集团[2]= 1,3,10日,2,4,11日,9日,8;
........................ 等
我们来试试动态规划吧!
1)如果你只有一个组呢?那就简单了，对吧?简单来说就是N种可能，其中N是组的大小。例如:
$hubnode[1]=array(1,2,3);
group[1] = 1
group[2] = 2
group[3] = 3
2)如果我们再加一组呢?假设:
hubnode美元[2]=数组(3、4);
你:
group[1] = 1,3
group[2] = 1,4
group[3] = 2,3
group[4] = 2,4
group[5] = 3,4
这告诉我们什么?基本上，当计算N个集线器的组时，我们可以取N-1个集线器的组，如果不在该组中，则将集线器N中的元素添加到每个组中。
我的意思是:
- 对于N = 1，你有一个组"group[1] = 1"，现在你从hub2中一个接一个地取出所有元素，并尝试将它们应用到这个组，每次创建一个新组。在本例中，这将创建组{1,3}和{1,4}。对于组[3]，它只创建组{3,4}，因为{3,3}不满足唯一元素的条件。
3)如果我们不能在点N处将任何集线器上的数应用到群上怎么办?我们抛弃这组。例如，当你有{1,3}和{1}时，你首先得到2组1和3，但你不能对第一个组做任何事情，所以丢弃它。
现在的问题是如何有效地检查X是否在组[Y]中。这是一个很好的问题，因为我们不能保持组排序(因为顺序很重要)，除非我们还为它来自哪个组的每个值添加一个标签。然后使用二分搜索，我们可以检查给定的数字是否在组中。
4)作为一种性能提升(如果你需要的话)，你可以处理从最小到最大的数组，因为最小的数组将给你最大的可能解决方案约束。
最坏的情况下，我们可以简单地线性检查每一组…
复杂性将是巨大的，但在最坏的情况下，你会有很多可能性，所以不要认为你能做那么多。最坏的情况是，你将有8组n不同的数字，这意味着n^8，哇!
注。就像Ondrej在评论区说的，你应该试着自己想一些东西——我回复只是因为我正在为面试练习;)