一道面试题,我已经想了2天了

RocChan 发布于 2017/09/03 13:32
阅读 2K+
收藏 5
PHP

题目我忘记了,大概的意思是这样的:

PHP实现一个数组中值的交叉组合

有一个数组,如果有3个值:array(3,2,6)。交叉组合后返回:3-2,3-6,2-6,3-2-6

有一个数组,如果有4个值:array(3,2,6,9)。交叉组合后返回:3-2,3-6,3-9,2-6,2-9,6-9,3-2-6,3-2-9,2-6-9,3-2-6-9

5个值,6个值以此类推

求各位大神有没有好的解法

加载中
2
开源中国首席装逼王

求 集合的 幂集(集合的所有子集)

 

2
波波侠
波波侠

我有一个思路哈,其实直观看起来就是多重循环嵌套,BUT套数不定,就是数组个数了, 可以将多重循环,改成递归。不知道明白我的意思没。

2
小马哥啊
小马哥啊
$array = array(1, 2, 3, 4, 5, 6);
$len = count($array);
$data = array();
for($prefixLength = 1; $prefixLength < $len; $prefixLength++){
	for($i = 0; $i < $len - 1; $i++){
		$prefixArray = array_slice($array, $i, $prefixLength);
		$prefix = implode('-', $prefixArray);
		for($j = $i + $prefixLength; $j < $len; $j++){
			$data[] = $prefix .'-'. $array[$j];
		}
	}
}
print_r($data);
/*
Array
(
	[0] => 1-2
	[1] => 1-3
	[2] => 1-4
	[3] => 1-5
	[4] => 1-6
	[5] => 2-3
	[6] => 2-4
	[7] => 2-5
	[8] => 2-6
	[9] => 3-4
	[10] => 3-5
	[11] => 3-6
	[12] => 4-5
	[13] => 4-6
	[14] => 5-6
	[15] => 1-2-3
	[16] => 1-2-4
	[17] => 1-2-5
	[18] => 1-2-6
	[19] => 2-3-4
	[20] => 2-3-5
	[21] => 2-3-6
	[22] => 3-4-5
	[23] => 3-4-6
	[24] => 4-5-6
	[25] => 1-2-3-4
	[26] => 1-2-3-5
	[27] => 1-2-3-6
	[28] => 2-3-4-5
	[29] => 2-3-4-6
	[30] => 3-4-5-6
	[31] => 1-2-3-4-5
	[32] => 1-2-3-4-6
	[33] => 2-3-4-5-6
	[34] => 1-2-3-4-5-6
)		
*/

 

栓独爱青春
栓独爱青春
厉害
蒋域丶极
蒋域丶极
谢谢分享
1
冷冷gg
冷冷gg

动态规划的味道

1
阿债
阿债
<?php
function get_pow_set(array $nums)
{
    //处理两个及以下元素的情况
    $count = count($nums);
    if ($count < 2) {
        return array();
    } elseif ($count === 2) {
        return array(implode('-', $nums), );
    }
    
    //递归,拿掉最后一个元素,得出上一步的结果
    $last = array_pop($nums);
    $result = get_pow_set($nums);
    $count_res = count($result);
    //上一步数组中每个元素和最后一个元素的组合
    foreach ($nums as $item) {
        $result[] = sprintf('%d-%d', $item, $last);
    }
    //上一步结果中每个元素和最后一个元素的组合
    for ($i = 0; $i < $count_res; $i ++) {
        $result[] = sprintf('%s-%d', $result[$i], $last);
    }
    return $result;
}

 

0
公孙二狗
公孙二狗

应该是求 n 个元素集合的组合: 求有 2 个,3 个,...,n 个元素的组合

组合算法百度就能搜索到

0
Shabby-滔
Shabby-滔

组合而已....

0
OSC_Pdhdcl
OSC_Pdhdcl
1 2 3 4 fn if <= for fn
0
昵称非法已被屏蔽

递归,js 版的

array = [1,2,3,4,5,6]

result =array.slice(0,1)

function foo(num){
  if(array.length === num) return;
  var length = result.length;
  for(var i = 0;i < length; i++)
    result.push(result[i]+"-"+array[num]);
  foo(num+1);
}

foo(1);

console.log(result.slice(1))

 

0
David257
David257

貌似在做彩票类应用哟

返回顶部
顶部