php经典算法面试题

吴宇 2020-01-03 59℃ 0条

面试中经常被问到会什么算法,下面收集了一些常见的经典算法,并为你详解它们的实现原理。希望能够帮助到广大php学习者及面试者。

       1、一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。

function king($m, $n) {
    if (1 >= $n) {
        return $n;
    }
    $monkeys = range(1, $n);
    $count = $n;
    while ($count > 1) {
        $remainder = $m % $count;
        unset($monkeys[$remainder - 1]);
        $monkeys = array_values($monkeys);
        $count--;
    }
 
    return array_shift($monkeys);
}

       2、有一母牛,到4岁可生育,每年一头,所生均是一样的母牛,到15岁绝育,不再能生,20岁死亡,问n年后有多少头牛。

function cows ($n) {
    $cows = [1];
    for ($i = 1; $i <= $n; $i++) {
        // 新出生的牛
        $new_number = 0;
        foreach ($cows as $age => $num) {
            // 4岁到14岁的牛生育新的母牛
            if ($age >= 3 && $age <= 13) {
                $new_number += $num;
            }
        }
        // 将新出生的牛加到数组开头
        array_unshift($cows, $new_number);
        // 取出数组的前20个单元
        $cows = array_slice($cows, 0, 20);
    }
 
    return array_sum($cows);
}

       3、冒泡排序

function bubble_sort ($array) {
    $array = array_values($array);
    for ($i = 0; $i < count($array); $i++) {
        for ($j = 0;$j < count($array) - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j + 1];
                $array[$j + 1] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
 
    return $array;
}

       4、快速排序

function quick_sort ($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $left_array = [];
    $right_array = [];
    $key = array_shift($array);
    foreach ($array as $value) {
        if ($key > $value) {
            $left_array[] = $value;
        }else {
            $right_array[] = $value;
        }
    }
 
    return array_merge(quick_sort($left_array), [$key], quick_sort($right_array));
}

       5、选择排序

function select_sort ($array) {
    $sort_array = [];
    while (count($array)) {
        $min = null;
        $min_key = null;
        foreach ($array as $key => $value) {
            if (is_null($min)) {
                $min = $value;
                $min_key = $key;
            }elseif ($min > $value) {
                $min = $value;
                $min_key = $key;
            }
        }
        $sort_array[] = $min;
        unset($array[$min_key]);
    }
 
    return $sort_array;
}

       6、字符集合:输入一个字符串,求出该字符串包含的字符集合,并按顺序排序

function unique_char ($str) {
    $arr = array_unique(str_split($str));
    sort($arr);
 
    return implode('', $arr);
}

       7、遍历一个文件下的所有文件和子文件夹下的文件

function all_file ($dir) {
    if (is_dir($dir)) {
        $resource = opendir($dir);
        while ($file = readdir($resource)) {
            if (in_array($file, ['.', '..'])) {
                continue;
            }elseif (is_dir($dir . '/' . $file)) {
                all_file($dir . '/' . $file);
            }else {
                echo $dir . '/' . $file, "\n";
            }
        }
    }else {
        echo $dir, "\n";
    }
}

       8、有个人想上一个n级的台阶,每次只能迈1级或者迈2级台阶,问:这个人有多少种方法可以把台阶走完?例如:总共3级台阶,可以先迈1级再迈2级,或者先迈2级再迈1级,或者迈3次1级总共3中方式.(实际上是斐波那契数列)

function ladder($steps) {
    return $steps < 2 ? 1 : ladder($steps - 1) + ladder($steps - 2);
}

       9、遍历二叉树

class Node
{
    public $value;
    public $left;
    public $right;
}
 
/**
 * 先序遍历 根节点 ---> 左子树 ---> 右子树
 *
 * @param $root
 */
function preorder ($root) {
    echo $root->value;
    if (!empty($root->left)) {
        preorder($root->left);
    }
    if (!empty($root->right)) {
        preorder($root->right);
    }
}
 
/**
 * 中序遍历,左子树---> 根节点 ---> 右子树
 *
 * @param $root
 */
function inorder ($root) {
    if (!empty($root->left)) {
        inorder($root->left);
    }
    echo $root->value;
    if (!empty($root->right)) {
        inorder($root->right);
    }
}
 
/**
 * 后序遍历,左子树 ---> 右子树 ---> 根节点
 *
 * @param $root
 */
function tailorder ($root) {
    if (!empty($root->left)) {
        tailorder($root->left);
    }
    if (!empty($root->right)) {
        tailorder($root->right);
    }
    echo $root->value;
}
 
$d = new Node;
$d->value = 'D';
$b = new Node;
$b->value = 'B';
$b->left = $d;
$e = new Node;
$e->value = 'E';
$f = new Node;
$f->value = 'F';
$c = new Node;
$c->value = 'C';
$c->left = $e;
$c->right = $f;
$a = new Node;
$a->value = 'A';
$a->left = $b;
$a->right = $c;
 
preorder($a);echo "\n";
inorder($a);echo "\n";
tailorder($a);echo "\n";
标签: php

非特殊说明,本博所有文章均为博主原创。