PHP 算法 查找篇

<?php
/**
 * 顺序查找（数组里查找某个值的键）
 * @param $array 给定数组
 * @param $high 最大键，结束位置
 * @param $value 要查找的值
 * @return int
 */
function sequence_search($array, $high, $value)
{
     for( $i=0; $i <= $high; $i++) {
          if ($array[$i] == $value) {
               break;
          }
     }
     if ($i <= $high) {
          return $i;
     } else {
          return -1;
     }
} 

$array = array(2, 4, 6, 8, 10);
$key = sequence_search($array, 3, 6);
echo $key;   // 输出 2 

/**
 * 二分查找（数组里查找某个值的键），也叫半分法
 * @param $array 给定数组
 * @param $low 最小键，开始位置
 * @param $high 最大键，结束位置
 * @param $value 要查找的值
 * @return int
 */
function binary_search($array, $low, $high, $value)
{
     if ( $low <= $high ) {
          $mid = intval( ($low+$high)/2 );
          if ( $array[$mid] == $value ) {
               return $mid;
          } elseif ( $value < $array[$mid] ) {
               return binary_search ( $array, $low, $mid-1, $value );
          } else {
               return binary_search ( $array, $mid+1, $high, $value );
          }
     }
     
     return -1;
}

$array = array(2, 4, 6, 8, 10, 12, 14);
$key = binary_search($array, 2, 7 , 8);
echo $key;     // 输出 3 

/**
 * 递归版 二分查找
 *
 * @param array  $container
 * @param        $search
 * @param int    $low
 * @param string $top
 * @return int|string
 */
function BinaryQueryRecursive(array $container, $search, $low = 0, $top = 'default')
{
    $top === 'default' && $top = count($container);
    if ($low <= $top) {
        $mid = intval(floor($low + $top) / 2);
        if (!isset($container[$mid])) {
            return '没找着哦';
        }
        if ($container[$mid] == $search) {
            return $mid;
        }
        if ($container[$mid] < $search) {
            return BinaryQueryRecursive($container, $search, $mid + 1, $top);
        } else {
            return BinaryQueryRecursive($container, $search, $low, $mid - 1);
        }
    }
}

function QuickQuery($array, $value, $low = 0, $high = 0)
{
    //判断是否为第一次调用
    if (count($array) != 0 and $high == 0) {
        $high = count($array);
    }
    //如果还存在剩余的数组元素
    if ($low <= $high) {
        //取$low和$high的中间值
        $mid = intval(($low + $high) / 2);
        //如果找到则返回
        if ($array[$mid] == $value) {
            return $mid;
        } else if ($value < $array[$mid]) {//如果没有找到，则继续查找
            return QuickQuery($array, $value, $low, $mid - 1);
        } else {
            return QuickQuery($array, $value, $mid + 1, $high);
        }
    }
    return -1;
}

echo QuickQuery([4, 5, 7, 8, 9, 10, 8], 8);

/**
 * 非递归版 二分查找
 *
 * @param array $container
 * @param       $search
 * @return int|string
 */
function BinaryQuery(array $container, $search)
{
    $top = count($container);
    $low = 0;
    while ($low <= $top) {
        $mid = intval(floor(($low + $top) / 2));
        if (!isset($container[$mid])) {
            return '没找着哦';
        }
        if ($container[$mid] == $search) {
            return $mid;
        }
        $container[$mid] < $search && $low = $mid + 1;
        $container[$mid] > $search && $top = $mid - 1;
    }
}

<?php
function quickSelect($arr, $target, $left, $right) {  
   
}  
  
$unsortedArray = [3, 5, 2, 1, 4];  
$target = 3;  
$index = quickSelect($unsortedArray, $target, 0, count($unsortedArray) - 1);  

echo "找到目标元素，索引为：{$index}"; // 输出：2

/**
 * insertQuery
 *
 * @param array $container
 * @param       $num
 * @return bool|float|int
 */
function insertQuery(array $container, $num)
{
    $count = count($container);
    $lower = 0;
    $high  = $count - 1;

    while ($lower <= $high) {
        if ($container[ $lower ] == $num) {
            return $lower;
        }
        if ($container[ $high ] == $num) {
            return $high;
        }

//        $left  = intval($lower + $num - $container[ $lower ]);
//        $right = ($container[ $high ] - $container[ $lower ]) * ($high - $lower);
//        $middle = $left /$right;
        
        // ($middle - $lower) / ($num - $container[ $lower ]) = ($high - $lower) / ($container[ $high ] - $container[ $lower ])
        $middle = intval(($high - $lower) * ($num - $container[ $lower ]) / ($container[ $high ] - $container[ $lower ])) + $lower;

        if ($num < $container[ $middle ]) {
            $high  = $middle - 1;
        } else if ($num > $container[ $middle ]) {
            $lower = $middle + 1;
        } else {
            return $middle;
        }
    }
    return false;
}

<?php
/**
 * $num == $container[$mid],直接返回
 * $num <  $container[$mid],新范围是第 $low   个到 $mid-1 个，此时范围个数为 produced($key-1)-1 个
 * $num >  $container[$mid],新范围是第 $mid+1 个到 $high  个，此时范围个数为 produced($key-2)-1 个
 */
class FibonacciQuery
{
    /**
     * FibonacciQuery constructor.
     *
     * @param array $container
     * @param       $num
     */
    public function __construct(array $container, $num)
    {
        $count = count($container);
        $lower = $key = $result = 0;
        $high  = $count - 1;
        //计算$count位于斐波那契数列的位置，$this->produced($key) - 1 是因为数组键名从0开始
        while ($count > ($this->produced($key) - 1)) {
            $key++;
        }
        //将不满的数值补全，补的数值为数组的最后一位
        for ($j = $count; $j <= ($this->produced($key) - 1); $j++) {
            $container[$j] = $container[$count - 1];
        }
        //查找开始
        while ($lower <= $high) {
            //计算当前分隔的下标
            $mid = $lower + $this->produced($key - 1) - 1;
            if ($num < $container[$mid]) {
                $high = $mid - 1;
                $key  -= 1;    //斐波那契数列数列下标减一位
            } else if ($num > $container[$mid]) {
                $lower = $mid + 1;
                $key   -= 2;    //斐波那契数列数列下标减两位
            } else {
                if ($mid <= $count - 1) {
                    $result = $mid;
                    break;
                } else { //这里$mid大于$count-1说明是补全数值，返回$count-1
                    $result = $count - 1;
                    break;
                }
            }
            
        }
        var_dump($result);
    }

    /**
     * 创建一个生产斐波那契数列
     *
     * @param $length
     * @return int
     */
    public function produced($length)
    {
        if ($length < 2) {
            return ($length == 0 ? 0 : 1);
        }
        return $this->produced($length - 1) + $this->produced($length - 2);
    }
}

function ViolentMatch($haystack, $needle) {
    $haystackLen = mb_strlen($haystack, 'utf-8');
    $needleLen = mb_strlen($needle, 'utf-8');
    
    $i = $j = 0;
    while ($i < $haystackLen && $j < $needleLen) {  
        if ($haystack[$i] == $needle[$j]) {  
            //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++      
            $i++;  
            $j++;  
        } else {  
            //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
            $i = $i - $j + 1;  
            $j = 0;  
        }  
    }  
    
    // 匹配成功，返回模式串p在文本串s中的位置，否则返回-1  
    if ($j == $needleLen) {
        return $i - $j;  
    } else {
        return -1;  
    } 
}

echo ViolentMatch("BBC ABCDAB ABCDABCDABDE", "ABCDABD");

class KMP
{
    public  $haystack;
    public  $needle;
    private $_haystackLen;
    private $_needleLen;
    private $_matchTable;
    private $_isMatch;

    //构造函数
    function __construct($haystack, $needle)
    {
        $this->haystack = $haystack;
        $this->needle   = $needle;
        //初始化一些参数
        $this->_haystackLen = $this->getLen($this->haystack);
        $this->_needleLen   = $this->getLen($this->needle);
        $this->_matchTable  = $this->getMatchTable();
        $this->_isMatch     = false;
    }


    //类似strpos函数功能
    public function strpos()
    {
        //haystack
        $haystackIdx = $matchNum = 0;
        while ($haystackIdx <= $this->_haystackLen - $this->_needleLen) {
            //needle
            $needIdx = 0;
            for (; $needIdx < $this->_needleLen; $needIdx++) {
                if (strcmp($this->haystack[$haystackIdx], $this->needle[$needIdx]) <> 0) {
                    if ($matchNum > 0) {
                        $lastMatchValue = $this->getLastMatchValue($needIdx - 1);
                        $haystackIdx    += $this->getStep($matchNum, $lastMatchValue);
                        $matchNum       = 0;
                    } else {
                        $haystackIdx++;
                    }
                    break;
                } else {
                    $haystackIdx++;
                    $matchNum++;
                    if ($matchNum == $this->_needleLen) {
                        $this->_isMatch = true;
                        break;
                    }
                }
            }
            if ($this->_isMatch == true) {
                break;
            }
        }
        return $this->_isMatch ? $haystackIdx - $this->_needleLen : false;
    }

    //获取字符长度
    private function getLen($str)
    {
        return mb_strlen($str, 'utf-8');
    }

    //获取部分匹配表
    private function getMatchTable()
    {
        $matchTable = [];
        for ($i = 0; $i < $this->_needleLen; $i++) {
            $intersectLen = 0;
            $nowStr       = mb_substr($this->needle, 0, $i + 1, 'utf-8');
            $preFixArr    = $this->getPreFix($nowStr);
            $sufFixArr    = $this->getSufFix($nowStr);
            if ($preFixArr && $sufFixArr) {
                $intersectArr = array_intersect($preFixArr, $sufFixArr);  
                if (!empty($intersectArr)) {
                    $intersect    = array_pop($intersectArr);  // 从栈中获取最上面一条，也就是最长的匹配
                    $intersectLen = mb_strlen($intersect, 'utf-8');
                }
            }
            $matchTable[$i] = $intersectLen;
        }
        return $matchTable;
    }

    //获取前缀数组，从短到长
    private function getPreFix($str)
    {
        $outArr = [];
        $strLen = $this->getLen($str);
        if ($strLen > 1) {
            for ($i = 1; $i < $strLen; $i++) {
                $outArr[] = mb_substr($str, 0, $i, 'utf-8');
            }
        }
        return $outArr;
    }

    //获取后缀数组
    private function getSufFix($str)
    {
        $outArr = [];
        $strLen = $this->getLen($str);
        if ($strLen > 1) {
            for ($i = 1; $i < $strLen; $i++) {
                $outArr[] = mb_substr($str, $i, null, 'utf-8');
            }
        }
        return $outArr;
    }

    //计算步长
    private function getStep($matchNum, $lastMatchValue)
    {
        return $matchNum - $lastMatchValue;
    }

    //获取最后匹配值
    private function getLastMatchValue($index)
    {
        return isset($this->_matchTable[$index]) ? $this->_matchTable[$index] : 0;
    }

}

$str    = 'a b a c a a b a c a b a c a b a a b b';
$subStr = 'a b a c a b';
$kmp    = new KMP($str, $subStr);
var_dump($kmp->strpos());
$kmp->haystack = 'pull requests';
$kmp->needle   = 'sts';
var_dump($kmp->strpos());
$kmp->haystack = 'i love you';
$kmp->needle   = 'hate';
var_dump($kmp->strpos());

<?php
class BFSQuery
{
    /**
     * @var array 关系网络
     */
    protected $relationship;
    /**
     * @var \SplQueue 处理队列
     */
    protected $queue;

    /**
     * @var string 搜索结果
     */
    protected $target;

    /**
     * BFSQuery constructor.
     *
     * @param array  $relationship
     * @param string $target
     */
    public function __construct(array $relationship, $target)
    {

        $this->relationship = $relationship;
        $this->queue        = new SplQueue();
        $this->target       = $target;
        $this->generator($this->relationship);
    }

    /**
     * 开始入列
     *
     * @param array $relation
     * @return \Generator
     */
    public function generator($relation)
    {
        foreach ($relation as $value) {
            $this->schedule($value);
        }
    }


    /**
     * 队列入队
     *
     * @param  $item
     * @return int
     */
    public function schedule($item)
    {
        $this->queue->enqueue($item);
    }

    /**
     * 队列中查找符合条件
     *
     * @return string
     */
    public function run()
    {
        $result = $this->target . '没有人有~!';
        while (!$this->queue->isEmpty()) {
            // 出队列
            $item = $this->queue->dequeue();
            if (!isset($item['friend'])) {
                continue;
            }
            if (!isset($item['fruit'])) {
                continue;
            }
            $totalFruit = count($item['fruit']);
            $mark       = 0;
            while ($totalFruit > $mark) {
                if ($item['fruit'][$mark] === $this->target) {
                    $result = '找到了～！';
                    break 2;
                }
                $mark++;
            }
            $this->generator($item['friend']);
        }
        return $result;
    }
}

<?php
class DijkstraQuery
{
    /**
     * @var array
     */
    protected $graph;
    
    /**
     * @var array
     */
    protected $processed;
    
    /**
     * @var int
     */
    protected $infinity;
    
    /**
     * @var string
     */
    protected $start;
    
    /**
     * @var string
     */
    protected $end;

    /**
     * DijkstraQuery constructor.
     *
     * @param array $graph
     * @param       $start
     * @param       $end
     */
    public function __construct(array $graph, $start, $end)
    {
        $this->graph      = $graph;  // 图
        $this->start      = $start;
        $this->end        = $end;
        $this->processed = array ();
        $this->infinity  = mt_getrandmax();  // 无穷大数
    }

    /**
     * 最短路径
     *
     * @return string
     */
    public function calculate()
    {
        // 开始人结构
        $costs             = $this->graph[$this->start];
        // 终点也放进来，不过距离为最大
        $costs[$this->end] = $this->infinity;
        // 在开始人结构中找到最小的邻居点
        $node              = $this->findLowestCostNode($costs);

        while ($node !== null) {
            // 距离
            $cost      = $costs[$node];
            // 邻居结构
            $neighbors = $this->graph[$node]  ?? array ();
            
            foreach ($neighbors as $neighbor => $distance) {
                // 新距离
                $newCost = $cost + $distance;
                
                // 如果这个邻居还没有包含进来，那么包含进来，变相补充开始人的邻居及距离
                if (!isset($costs[$neighbor])) {
                    $costs[$neighbor] = $newCost;
                }
                
                // 开始人到邻居的距离比新距离大，则开始人到邻居的距离取新距离，变相修改开始人到邻居的最短距离
                if ($costs[$neighbor] > $newCost) {
                    $costs[$neighbor] = $newCost;
                }
            }
            
            // 把算过的邻居计入过程
            array_push($this->processed, $node);
            
            // 继续选择里面最近的邻居，直到所有邻居都计算完
            $node = $this->findLowestCostNode($costs);
        }

        return 'The shortest distance for：' . $costs[$this->end];
    }

    /**
     * findLowestCostNode
     * 寻找最小邻居节点   
     *
     * @param $costs
     * @return null
     */
    protected function findLowestCostNode($costs)
    {
        // 当前最小距离
        $lowestCost     = $this->infinity;
        
        // 最小邻居
        $lowestCostNode = null;
        
        foreach ($costs as $node => $cost) {
            if ($cost < $lowestCost && !in_array($node, $this->processed)) {
                $lowestCost     = $cost;
                $lowestCostNode = $node;
            }
        }
        
        return $lowestCostNode;
    }
}

// +--------------------------------------------------------------------------
// | 验证 me --> claire
// +--------------------------------------------------------------------------
//  ∞
$graph = array (
    'me'     => array (
        'alice' => 6,
        'bob'   => 2,
    ),
    'alice'  => array (
        'claire' => 1,
    ),
    'bob'    => array (
        'alice'  => 3,
        'claire' => 5,
    ),
    'claire' => array (// 没有任何邻居

    ),
);
echo (new DijkstraQuery($graph, 'me', 'claire'))->calculate();

<?php
/**
 * 二叉搜索树
 * 
 * 二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
 * 1.每个结点都有一个作为搜索依据的关键码(value)，所有结点的关键码互不相同。
 * 2.左子树（如果非空）上所有结点的关键码都小于根结点的关键码。
 * 3.右子树（如果非空）上所有结点的关键码都大于根结点的关键码。
 * 4.左子树和右子树也是二叉搜索树。
 * 
 * class Node {
 *  public $value;
 *  public $left = null;
 *  public $right = null;
 * }
 */
class BinarySearchTree
{
    /**
     * @var $root 根节点
     */
    public $root = null;

    /**
     * 创建新节点
     * @param $data  关键码
     */
    protected function createNode($data)
    {
        $node = new stdClass();
        $node->value = $data;
        $node->left = null;
        $node->right = null;
        return $node;
    }


    /**
     * 插入节点
     * @param $node  根节点
     * @param $value 关键值
     */
    public function insert(&$node, $value)
    {
        // $value为 null、 '' 的情况
        if (empty($value) && $value !== 0) {
            return ;
        }

        if ($node == null) {
            // 创建结点
            $node = $this->createNode($value);
        } else if ($value < $node->value) {
            $this->insert($node->left, $value);
        } else {
            $this->insert($node->right, $value);
        }
    }

    /**
     * 先序遍历
     * @param $node 根节点
     */
    public function preOrder(&$node)
    {
       if ($node != null) {
            echo $node->value . PHP_EOL ;
            $this->preOrder($node->left);
            $this->preOrder($node->right);
        }
    }
    
    /**
     * 中序遍历
     * @param $node 根节点
     */
    public function middleOrder(&$node)
    {
       if ($node != null) {
           $this->middleOrder($node->left);
            echo $node->value . PHP_EOL ;
            $this->middleOrder($node->right);
        }
    }

    /**
     * 后序遍历
     * @param $node 根节点
     */
    public function afterOrder(&$node)
    {
       if ($node != null) {
            $this->afterOrder($node->left);
            $this->afterOrder($node->right);
            echo $node->value . PHP_EOL;
        }
    }

    /**
     * 获取最大值
     * @param $node 根节点
     */
    public function findMax(&$node) 
    {
        while ($node->right != null) {
            $node = $node->right;
        }
        return $node->value;
    }
}

$tree = new BinarySearchTree();
$tree->insert($tree->root, 3);
$tree->insert($tree->root, 9);
$tree->insert($tree->root, 2);
$tree->insert($tree->root, 20);

echo "先序遍历".PHP_EOL;
$tree->preOrder($tree->root); 

echo "中序遍历" . PHP_EOL;
$tree->middleOrder($tree->root); 

echo "后序遍历" . PHP_EOL;
$tree->afterOrder($tree->root); 

$max = $tree->findMax($tree->root); 

var_dump($max);