PHP-Datenstrukturen und Algorithmen

Dieser Artikel teilt Ihnen hauptsächlich die Datenstruktur und den Algorithmus von PHP mit, hauptsächlich in Form von Code, in der Hoffnung, allen zu helfen.

Datenstrukturen und Algorithmen

1 Damit Objekte foreach-Schleifen wie Arrays ausführen können, müssen die Eigenschaften privat sein. (PHP5-Implementierung des Iterator-Modus, schreiben Sie eine Klasse zur Implementierung der Iterator-Schnittstelle) (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/>';
    }?>

2. Verwenden Sie PHP, um eine bidirektionale Warteschlange zu implementieren (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);
    }
}?>

3. Bitte verwenden Sie die Blasensortiermethode, um den folgenden Datensatz zu sortieren: 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);?>

4. Schreiben Sie einen Sortieralgorithmus (Schreibcode) und erklären Sie, wie Sie ihn optimieren können. (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);
    }
}?>

Dieser Algorithmus wird durch Divide-and-Conquer-Rekursion implementiert. Seine Effizienz hängt weitgehend von der Auswahl der Referenzelemente ab. Sie können auch drei Elemente auswählen Elemente zufällig auswählen und dann das mittlere Element auswählen (Drei-Zahlen-Median-Methode).
Ein weiterer Punkt ist, dass bei der Division die Effizienz der rekursiven Sortierung normalerweise nicht so schnell ist wie die Einfügungssortierung oder die Hill-Sortierung, wenn die Länge der geteilten Teilsequenz sehr klein ist (weniger als 5 bis 20). Daher können Sie die Länge des Arrays beurteilen, indem Sie die Einfügungssortierung direkt verwenden, anstatt diese schnelle Sortierung rekursiv aufzurufen.

5. Eine Gruppe Affen stellt sich im Kreis auf und wird nach 1, 2,..., n nummeriert. Beginnen Sie dann mit dem Zählen vom ersten, zählen Sie bis zum m-ten, werfen Sie es aus dem Kreis, beginnen Sie von hinten zu zählen, zählen Sie bis zum m-ten, werfen Sie es raus ... und fahren Sie auf diese Weise fort, bis es nur noch gibt Ein Affe ist noch übrig, dieser Affe wird der König genannt. Um diesen Prozess zu simulieren, ist eine Programmierung erforderlich. Geben Sie m und n ein und geben Sie die Nummer des letzten Königs aus. (Sina) (Xiaomi)

Dies ist das berühmte Joseph-Ring-Problem

<?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));?>

6. Schreiben Sie eine zweidimensionale Array-Sortieralgorithmus-Funktion, die vielseitig ist und in PHP integrierte Funktionen aufrufen kann .

<?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);?>

7. Verwenden Sie die Binärmethode, um eine sortierte lineare Tabelle der Länge 10 zu finden. Wenn die Suche nicht erfolgreich ist, beträgt die maximale Anzahl erforderlicher Vergleiche (Xiaomi)

4

8. Wählen Sie zufällig drei verschiedene Zahlen aus diesen zehn Zahlen aus: 0,1,2,3,4,5,6,7,8,9, „die drei Zahlen enthalten nicht 0 und 5“ Die Wahrscheinlichkeit ist ( Xiaomi)

7/15

9. An den drei Ecken eines Dreiecks befinden sich drei Mäuse. Wenn ein Schuss zu hören ist, beginnen sich die drei Mäuse mit konstanter Geschwindigkeit an den Seiten entlang zu bewegen des Dreiecks. Bitte fragen Sie sie. Die Wahrscheinlichkeit der Begegnung beträgt (Xiaomi) 75 %. Jede Maus hat zwei Bewegungsrichtungen: im Uhrzeigersinn und gegen den Uhrzeigersinn. Nur wenn alle 3 Mäuse vorhanden sind Im Uhrzeigersinn oder gegen den Uhrzeigersinn. Gegen den Uhrzeigersinn treffen sie sich nicht und die verbleibenden 6 Situationen treffen sich, sodass die Wahrscheinlichkeit eines Treffens 6/8 = 75 % beträgt.

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?>

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));?>

12.写出你所知道的排序方法（亿邮）

冒泡排序，快速排序，插入排序，选择排序。

Das obige ist der detaillierte Inhalt vonPHP-Datenstrukturen und Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!