structures de données et algorithmes php-tutoriel php-php.cn

Cet article partage principalement avec vous la structure des données et l'algorithme PHP, principalement sous forme de code, dans l'espoir d'aider tout le monde.

Structures de données et algorithmes

1. Pour permettre aux objets d'effectuer des boucles foreach comme des tableaux, les propriétés doivent être privées. (Implémentation PHP5 du mode Iterator, écrivez une classe pour implémenter l'interface Iterator) (Tencent)

<?php
    class Test implements Iterator{    private $item = array(&#39;id&#39;=>1,'name'=>'php');    public function rewind(){
        reset($this->item);
    }    public function current(){        return current($this->item);
    }    public function key(){        return key($this->item);
    }    public function next(){        return next($this->item);
    }    public function valid(){        return($this->current()!==false);
    }
}    //测试
    $t=new Test;    foreach($t as $k=>$v){        echo$k,'--->',$v,'<br/>';
    }?>

Copier après la connexion

2 Utilisez PHP pour implémenter une file d'attente bidirectionnelle (Tencent)

<?php
    class Deque{    private $queue=array();    public function addFirst($item){        return array_unshift($this->queue,$item);
    }    public function addLast($item){        return array_push($this->queue,$item);
    }    public function removeFirst(){        return array_shift($this->queue);
    }    public function removeLast(){        return array_pop($this->queue);
    }
}?>

Copier après la connexion

3. Veuillez utiliser La méthode de tri à bulles trie l'ensemble de données suivant 10 2 36 14 10 25 23 85 99 45.

<?php
    // 冒泡排序
    function bubble_sort(&$arr){        for ($i=0,$len=count($arr); $i < $len; $i++) {            for ($j=1; $j < $len-$i; $j++) {                if ($arr[$j-1] > $arr[$j]) {
                    $temp = $arr[$j-1];
                    $arr[$j-1] = $arr[$j];
                    $arr[$j] = $temp;
                }
            }
        }
    }    // 测试
    $arr = array(10,2,36,14,10,25,23,85,99,45);
    bubble_sort($arr);
    print_r($arr);?>

Copier après la connexion

4. Écrivez un algorithme de tri (écrivez du code) et indiquez comment l'optimiser. (Sina)

<?php
    //快速排序
    function partition(&$arr,$low,$high){
        $pivotkey = $arr[$low];        while($low<$high){            while($low < $high && $arr[$high] >= $pivotkey){
                $high--;
            }
            $temp = $arr[$low];
            $arr[$low] = $arr[$high];
            $arr[$high] = $temp;            while($low < $high && $arr[$low] <= $pivotkey){
                $low++;
            }
            $temp=$arr[$low];
            $arr[$low]=$arr[$high];
            $arr[$high]=$temp;
        }        return$low;
    }function quick_sort(&$arr,$low,$high){    if($low < $high){
        $pivot = partition($arr,$low,$high);
        quick_sort($arr,$low,$pivot-1);
        quick_sort($arr,$pivot+1,$high);
    }
}?>

Copier après la connexion

Cet algorithme est implémenté par récursion diviser pour régner. Son efficacité dépend en grande partie de la sélection des éléments de référence. Vous pouvez choisir l'élément central du tableau, ou vous pouvez en obtenir trois. éléments au hasard, puis sélectionnez l'élément du milieu (méthode médiane à trois nombres).

Un autre point est que lorsque nous divisons, si la longueur de la sous-séquence divisée est très petite (moins de 5 à 20), l'efficacité du tri récursif n'est généralement pas aussi rapide que le tri par insertion ou le tri Hill. Par conséquent, vous pouvez juger de la longueur du tableau si elle est inférieure à 10, utilisez le tri par insertion directement au lieu d'appeler ce tri rapide de manière récursive.

5. Un groupe de singes s'alignent en cercle et sont numérotés selon 1, 2,..., n. Puis commencez à compter à partir du 1er, comptez jusqu'au mème, expulsez-le du cercle, commencez à compter par derrière, comptez jusqu'au mème, expulsez-le..., et continuez ainsi, jusqu'à ce qu'il n'y ait plus que il reste un singe, ce singe s'appelle le roi. Une programmation est nécessaire pour simuler ce processus, saisir m, n et afficher le numéro du dernier roi. (Sina) (Xiaomi)

C'est le célèbre problème de l'anneau de Joseph

<?php
    // 方案一，使用php来模拟这个过程
    function king($n,$m){
        $mokey = range(1, $n);
        $i = 0;        while (count($mokey) >1) {
            $i += 1;
            $head = array_shift($mokey);//一个个出列最前面的猴子
            if ($i % $m !=0) {                #如果不是m的倍数，则把猴子返回尾部，否则就抛掉，也就是出列
                array_push($mokey,$head);
            }            // 剩下的最后一个就是大王了
            return $mokey[0];
        }
    }    // 测试
    echo king(10,7);    // 方案二，使用数学方法解决
    function josephus($n,$m){
        $r = 0;        for ($i=2; $i <= $m ; $i++) {
            $r = ($r + $m) % $i;
        }        return $r+1;
    }    // 测试
    print_r(josephus(10,7));?>

Copier après la connexion

6. Écrivez une fonction d'algorithme de tri de tableau bidimensionnel qui est polyvalente et peut appeler des fonctions intégrées PHP .

<?php//二维数组排序，$arr是数据，$keys是排序的健值，$order是排序规则，1是降序，0是升序function array_sort($arr,$keys,$order=0){    if(!is_array($arr)){        return false;
    }
    $keysvalue=array();    foreach($arr as $key => $val){
        $keysvalue[$key] = $val[$keys];
    }    if($order == 0){
        asort($keysvalue);
    }else{
        arsort($keysvalue);
    }
    reset($keysvalue);    foreach($keysvalue as $key => $vals){
        $keysort[$key] = $key;
    }
    $new_array=array();    foreach($keysort as $key=> $val){
        $new_array[$key]=$arr[$val];
    }    return$new_array;
}    //测试
    $person=array(        array('id'=>2,'name'=>'zhangsan','age'=>23),        array('id'=>5,'name'=>'lisi','age'=>28),        array('id'=>3,'name'=>'apple','age'=>17)
    );
    $result = array_sort($person,'name',1);
    print_r($result);?>

Copier après la connexion

7. Utilisez la méthode binaire pour trouver un tableau linéaire trié de longueur 10. Lorsque la recherche échoue, le nombre maximum de comparaisons requises est (Xiaomi)

8. Sélectionnez au hasard trois nombres différents parmi ces dix nombres 0,1,2,3,4,5,6,7,8,9, "les trois nombres n'incluent pas 0 et 5" La probabilité est ( Xiaomi)

15/7

9. Il y a 3 souris aux trois sommets d'un triangle Lorsqu'un coup de feu se fait entendre, les 3 souris commencent à se déplacer à une vitesse constante le long des côtés du triangle. le triangle. Veuillez leur demander. La probabilité de rencontre est (Xiaomi)

75%. Chaque souris a deux sens de mouvement : dans le sens des aiguilles d'une montre et dans le sens inverse. Il y a 8 situations de mouvement pour 3 souris. Uniquement lorsque les 3 souris sont dans le sens des aiguilles d'une montre. ou dans le sens inverse des aiguilles d'une montre, ils ne se rencontreront pas et les 6 situations restantes se rencontreront, donc la probabilité de se rencontrer est de 6/8 = 75 %.

10.描述顺序查找和二分查找（也叫做折半查找）算法，顺序查找必须考虑效率，对象可以是一个有序数组（小米）

<?php
    /**
     * 顺序查找
     * @param  array $arr 数组
     * @param   $k   要查找的元素
     * @return   mixed  成功返回数组下标，失败返回-1
     */
    function seq_sch($arr,$k){        for ($i=0,$n = count($arr); $i < $n; $i++) {            if ($arr[$i] == $k) {                break;
            }
        }        if($i < $n){            return $i;
        }else{            return -1;
        }
    }    /**
     * 二分查找，要求数组已经排好顺序
     * @param  array $array 数组
     * @param  int $low   数组起始元素下标
     * @param  int $high  数组末尾元素下标
     * @param   $k     要查找的元素
     * @return mixed        成功时返回数组下标，失败返回-1
     */
    function bin_sch($array,$low,$high,$k){        if ($low <= $high) {
            $mid = intval(($low + $high) / 2);            if ($array[$mid] == $k) {                return $mid;
            } elseif ($k < $array[$mid]) {                return bin_sch($array,$low,$mid - 1,$k);
            } else{                return bin_sch($array,$mid + 1,$high,$k);
            }
        }        return -1;
    }    // 测试：顺序查找
    $arr1 = array(9,15,34,76,25,5,47,55);    echo seq_sch($arr1,47);//结果为6

    echo "<br />";    // 测试：二分查找
    $arr2 = array(5,9,15,25,34,47,55,76);    echo bin_sch($arr2,0,7,47);//结果为5?>

Copier après la connexion

11.我们希望开发一款扑克游戏，请给出一套洗牌算法，公平的洗牌并将洗好的牌存储在一个整形数组里。（鑫众人云）

<?php
    $card_num = 54;//牌数
    function wash_card($card_num){
        $cards = $tmp = array();        for($i = 0;$i < $card_num;$i++){
            $tmp[$i] = $i;
        }        for($i = 0;$i < $card_num;$i++){
            $index = rand(0,$card_num-$i-1);
            $cards[$i] = $tmp[$index];            unset($tmp[$index]);
            $tmp = array_values($tmp);
        }        return $cards;
    }    // 测试：
    print_r(wash_card($card_num));?>

Copier après la connexion