PHP 데이터 구조와 알고리즘

이 기사에서는 모든 사람에게 도움이 되기를 바라며 주로 코드 형식으로 PHP 데이터 구조와 알고리즘을 여러분과 공유합니다.

데이터 구조 및 알고리즘

1. 객체가 배열처럼 반복되도록 하려면 속성이 비공개여야 합니다. (Iterator 모드의 PHP5 구현, 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/>';
    }?>

2. PHP를 사용하여 양방향 대기열 구현 (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 다음을 정렬하려면 버블 정렬 방법을 사용하세요. 데이터 세트 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. 정렬 알고리즘을 작성하고(코드 작성) 최적화 방법을 알려주세요. (시나)

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

알고리즘은 분할 정복 재귀를 통해 구현됩니다. 효율성은 주로 참조 요소 선택에 따라 달라집니다. 배열의 중간 요소를 선택하거나 무작위로 세 요소를 가져온 다음 선택할 수 있습니다. 중간 요소(3개 숫자의 평균 방법).
또 다른 점은 분할할 때 분할된 하위 수열의 길이가 매우 작으면(5~20 미만) 일반적으로 재귀 정렬의 효율성이 삽입 정렬이나 Hill 정렬만큼 빠르지 않다는 것입니다. 따라서 배열의 길이가 10보다 작다면 이 퀵 정렬을 재귀적으로 호출하는 대신 직접 삽입 정렬을 사용하면 됩니다.

5. 한 무리의 원숭이들이 원을 그리며 줄을 서고 1, 2,..., n에 따라 번호가 매겨져 있습니다. 그런 다음 첫 번째부터 세기 시작하고, m 번째까지 세고, 원 밖으로 쫓아내고, 뒤에서 세기 시작하고, m 번째까지 세고, 쫓아내고... 그리고 이 방법으로 계속합니다. 원숭이 한 마리만 남았는데, 그 원숭이를 왕이라 부른다. 이 과정을 시뮬레이션하여 m, n을 입력하고 마지막 왕의 수를 출력하는 프로그래밍이 필요합니다. (시나) (샤오미)

이것은 유명한 조셉 링 문제입니다

<?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. PHP 내장 함수를 호출할 수 있고 다재다능한 2차원 배열 정렬 알고리즘 함수를 작성합니다.

<?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 이진 방법을 사용하여 길이가 10인 정렬된 선형 테이블을 찾습니다. 검색에 실패하면 필요한 최대 비교 수는 (Xiaomi)

4

8부터입니다. ,4,5,6,7,8,9, 이 10개의 숫자 중에서 서로 다른 숫자 3개를 무작위로 선택하면 "세 숫자에 0과 5가 포함되어 있지 않다"는 확률은 (Xiaomi)

7/15

9 입니다. 삼각형의 세 꼭지점에 3마리의 쥐가 있습니다. 총이 발사되면 3마리의 쥐가 삼각형의 변을 따라 균일하게 움직이기 시작합니다. (샤오미)

75%. 시계 방향 또는 시계 반대 방향으로 3마리의 마우스가 움직이는 8가지 상황이 있으며, 3마리의 마우스가 모두 시계 방향 또는 시계 반대 방향으로 움직일 경우에만 나머지 6가지 상황이 충족되지 않으므로 만날 확률은 다음과 같습니다. 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?>

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.写出你所知道的排序方法（亿邮）

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

위 내용은 PHP 데이터 구조와 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!