php程序員面試之百度面試題

面試題不同公司不一樣像百度公司要求算法高這個也能理解了，下面整理了一道據說是百度的面試題，我們來看看它的算法與答案吧。

據說是一個百度php的面試題，已給定一個數組：

$arr = array(‘b’=>’a’, ‘c’=>’a’, ‘e’=>’b’, ‘d’=>’b’, ‘f’=>’c’, ‘g’=>’e’, ‘h’=>’f’);

寫一個算法，完成到以下格式的轉換：

array (

    'a' => array (

        'b' => array (

            'e' => array (

                [0] => 'g',

            ),

            [0] => 'd',

        ),

        'c' => array (

            'f' => array (

                [0] => 'h',

            ),

        ),

    ),

)

這個結構應該屬於一種Trie樹。當時在寫的時候由於沒發現array_keys()函數第二個參數(汗一個先)，於是寫了以下這個方法來實現。

function getsomething(&$arr, &$re, $c='') {

    $c or $c=array_shift(array_keys($arr));//當未指定開始位置時 從數組第一個元素開始

    $flag= false;   //標記 當有和$c對應的key(鍵)時 設為true

    while($k = array_search($c, $arr)) {    //循環獲取值為$c的key。

        getsomething($arr, $re[$c], $k);    //一直遞歸到最後沒有key對應時

        unset($arr[$k]);        //移除  這個元素已經不會再使用了

        $flag = true;

    }

    //當flag為真時 說明之前獲得過正常存在的key，不會繼續生成[0]下標的元素

    if(! $flag) return $re[] = $c; 

}

//調用

getsomething($arr, $re, 'a');

雖然有點兒奇葩，至少還是實現了。以下是某網友使用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;

}