面試題不同公司不一樣像百度公司要求算法高這個(gè)也能理解了,下面整理了一道據(jù)說是百度的面試題,我們來看看它的算法與答案吧.
據(jù)說是一個(gè)百度php的面試題,已給定一個(gè)數(shù)組:
$arr = array(‘b’=>’a’, ‘c’=>’a’, ‘e’=>’b’, ‘d’=>’b’, ‘f’=>’c’, ‘g’=>’e’, ‘h’=>’f’);
寫一個(gè)算法,完成到以下格式的轉(zhuǎn)換:
array (
'a' => array (
'b' => array (
'e' => array (
[0] => 'g',
),
[0] => 'd',
),
'c' => array (
'f' => array (
[0] => 'h',
),
),
),
)
這個(gè)結(jié)構(gòu)應(yīng)該屬于一種Trie樹,當(dāng)時(shí)在寫的時(shí)候由于沒發(fā)現(xiàn)array_keys()函數(shù)第二個(gè)參數(shù)(汗一個(gè)先),于是寫了以下這個(gè)方法來實(shí)現(xiàn).
function getsomething(&$arr, &$re, $c='') {
$c or $c=array_shift(array_keys($arr));//當(dāng)未指定開始位置時(shí) 從數(shù)組第一個(gè)元素開始
$flag= false; //標(biāo)記 當(dāng)有和$c對應(yīng)的key(鍵)時(shí) 設(shè)為true
while($k = array_search($c, $arr)) { //循環(huán)獲取值為$c的key。
getsomething($arr, $re[$c], $k); //一直遞歸到最后沒有key對應(yīng)時(shí)
unset($arr[$k]); //移除 這個(gè)元素已經(jīng)不會(huì)再使用了
$flag = true;
}
//當(dāng)flag為真時(shí) 說明之前獲得過正常存在的key，不會(huì)繼續(xù)生成[0]下標(biāo)的元素
if(! $flag) return $re[] = $c;
}
//調(diào)用
getsomething($arr, $re, 'a');
雖然有點(diǎn)兒奇葩，至少還是實(shí)現(xiàn)了。以下是某網(wǎng)友使用array_keys()的另一解法：
function _array_keys($k, $arr) {
$return = array();
if($ret = array_keys($arr, $k)) {
foreach($ret as $v) {
if($t = _array_keys($v, $arr)) {
$return[$v] = $t;
} else {
$return[] = $v;
}
}
}
return $return;
}
