PHP算法实战

后端开发涉及Java、PHP等语言 #生活知识# #生活经验# #编程#

二分查找

基本思想：

      假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。（数据量大的时候使用）

<?php

function bin_search($arr,$low,$high,$k)

{

if($low <= $high)

{

$mid = intval(($low + $high)/2);

if($arr[$mid] == $k)

{

return $mid;

}

else if($k < $arr[$mid])

{

return bin_search($arr,$low,$mid-1,$k);

}

else

{

return bin_search($arr,$mid+1,$high,$k);

}

}

return -1;

}

$arr = array(1,2,3,4,5,6,7,8,9,10);

print(bin_search($arr,0,9,3));

?>

顺序查找

基本思想：

  从数组的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。

<?php

function seq_search($arr,$n,$k)

{

$array[$n] = $k;

for($i = 0;$i < $n; $i++)

{

if($arr[$i] == $k)

{

break;

}

}

if($i < $n)

{

return $i;

}

else

{

return -1;

}

}

?>

简化增强版本

function seq_sch($array, $k){

$y = $m = 'no';

foreach($array as $i => $v){

if($v == $k){

if($i == 'no'){$m = 'yes'}

$y = $i;

break;

}

}

if ($y != 'no' || $m == 'yes'){

return $y;

}else{

return -1;

}

}

此方法适用于所有一维数组

PHP奇异算法

<?php

function test(){

$a=1;

$b=&$a;

echo (++$a)+(++$a);

}

test();

PHP7以下的版本返回的是 6，PHP7版本返回5 ，还真的算奇异，个人底层算法差，认为是PHP7以下版本的BUG

线性表的删除（数组中实现）

function delete_array_element($array , $i){

$len = count($array);

for ($j=$i; $j<$len; $j++){

$array[$j] = $array [$j+1];

}

array_pop ($array);

return $array ;

}

字符串长度

function strlen ($str){

if ($str == '' ) return 0;

$count = 0;

while (1){

if ($str[$count] != NULL){

$count++;

continue;

}else{

break;

}

}

return $count;

}

while (1) 其中1代表一个常量表达式，他永远不会等于0。所以，循环会一直执行下去。除非你设置break等类似的跳出循环语句循环才会中止

$str[count] php是弱类型语言 使用下标可以读取到相应位置对应参数

function substr($str, $start, $length=NULL){

if ($str== '' || $start>strlen($str)) return;

if (($length!=NULL) && ($start>0) && ($length>strlen($str)-$start)) return;

if (($length!=NULL) && ($start<0) && ($length>strlen($str )+$start)) return;

if ($length == NULL) $length = (strlen($str) - $start);

if ($start < 0){

for ($i=(strlen($str)+$start); $i<(strlen ($str)+$start+$length ); $i++) {

$substr .= $str[$i];

}

}

if ($length > 0){

for ($i= $start; $i<($start+$length); $i++) {

$substr .= $str[$i];

}

}

if ($length < 0){

for ($i =$start; $i<(strlen($str)+$length); $i++) {

$substr .= $str[$i ];

}

}

return $substr;

字符串翻转

function strrev($str){

if ($str == '') return 0 ;

for ($i=(strlen($str)- 1); $i>=0; $i --){

$rev_str .= $str[$i ];

}

return $rev_str;

}

字符串比较

function strcmp($s1, $s2){

if (strlen($s1) < strlen($s2)) return -1 ;

if (strlen($s1) > strlen( $s2)) return 1;

for ($i=0; $i<strlen($s1); $i++){

if ($s1[$i] == $s2[$i]){

continue;

}else{

return false;

}

}

return 0;

}

查找字符串

function strstr($str, $substr){

$m = strlen($str);

$n = strlen($substr);

if ($m < $n) return false ;

for($i=0; $i<=($m-$n+1); $i++){

$sub = substr($str, $i, $n);

if (strcmp($sub, $substr) == 0) return $i;

}

return false ;

}

strcmp(sub,sub,substr)字符串比较方法 如果想不用比较方法请增加for循环 字符串替换

function str_replace($substr, $newsubstr, $str){

$m = strlen($str);

$n = strlen($substr);

$x = strlen($newsubstr);

if (strchr($str, $substr) == false) return false;

$str_new = $str

for ($i=0; $i<=($m-$n+1); $i++){

$i = strchr($str, $substr);

$str = str_delete($str_new, $i, $n);

$str = str_insert($str_new, $i, $newstr);

}

return $str_new;

}

strchr() 函数搜索字符串在另一字符串中的第一次出现。 
该函数是 strstr() 函数的别名。 插入一段字符串

function str_insert($str, $i , $substr) {

for($j=0 ; $j<$i; $j++){

$startstr .= $str[$j];

}

for ($j=$i; $j <strlen($str); $j++){

$laststr .= $str[$j ];

}

$str = $startstr.$substr.$laststr;

return $str ;

}

删除一段字符串

function str_delete($str, $i, $j){

for ( $c=0; $c<$i; $c++){

$startstr .= $str [$c];

}

for ($c=( $i+$j); $c<strlen ($str); $c++){

$laststr .= $str[$c];

}

$str = $startstr.$laststr;

return $str;

}

复制字符串

function strcpy($s1, $s2){

if (strlen($s1)==NULL || !isset($s2)) return;

for ($i=0; $i<strlen($s1); $i++){

$s2[] = $s1[$i];

}

return $s2;

}

连接字符串

function strcat($s1 ,$s2){

if (!isset($s1) || !isset( $s2)) return;

$newstr = $s1 ;

for($i=0; $i<strlen($s2); $i++){

$newstr .= $s2[$i];

}

return $newstr;

}

---------------------------------------------------------------------------------------------------------------------------------------------------------

字符集合：输入一个字符串，求出该字符串包含的字符集合，并按顺序排序（英文）

function set($str){

$arr = str_split($str);

$arr = array_flip(array_flip($arr));

sort($arr);

return implode('', $arr);

}

遍历文件夹

<?php

function my_scandir($dir)

{

$files = array();

if($handle = opendir($dir))

{

while (($file = readdir($handle))!== false)

{

if($file != '..' && $file != '.')

{

if(is_dir($dir."/".$file))

{

$files[$file]=my_scandir($dir."/".$file);

}

else

{

$files[] = $file;

}

}

}

closedir($handle);

return $files;

}

}

var_dump(my_scandir('../'));

?>

写一个函数，尽可能高效的从一个标准url中取出文件的扩展名

<?php

function getExt($url)

{

$arr = parse_url($url);

$file = basename($arr['path']);

$ext = explode('.', $file);

return $ext[count($ext)-1];

}

print(getExt('http://www.sina.com.cn/abc/de/fg.html.php?id=1'));

?>

实现中文字符串截取无乱码的方法

可使用mb_substr,但是需要确保在php.ini中加载了php_mbstring.dll，即确保“extension=php_mbstring.dll”这一行存在并且没有被注释掉，否则会出现未定义函 数的问题。

 

数据结构和算法

使对象可以像数组一样进行foreach循环，要求属性必须是私有。(Iterator模式的PHP5实现，写一类实现Iterator接口)（腾讯）
 

<?php

class Test implements Iterator{

private $item = array('id'=>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/>';

}

?>

用PHP实现一个双向队列（腾讯）

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

}

}

?>

请使用冒泡排序法对以下一组数据进行排序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);

?>

写出一种排序算法（要写出代码），并说出优化它的方法。（新浪）

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

}

}

?>

关于猴子的面试题

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

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

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

function king($n, $m){

$monkeys = range(1, $n);

$i=0;

while (count($monkeys)>1) {

if(($i+1)%$m==0) {

unset($monkeys[$i]);

} else {

array_push($monkeys,$monkeys[$i]);

unset($monkeys[$i]);

}

$i++;

}

return current($monkeys);

}

echo king(6,3);

?>

二维数组排序算法函数，能够具有通用性，可以调用php内置函数。

<?php

function array_sort($arr,$keys,$order=0){

if(!is_array($arr)){

return false;

    }

$keysvalue=array();

foreach($arr as $key => $val){

$keysvalue[$key] = $val[$keys];

    }

print_r($keysvalue);

if($order == 0){

asort($keysvalue);

    }else{

arsort($keysvalue);

    }

print_r($keysvalue);

$new_array=array();

foreach($keysvalue as $key => $val){

$new_array[$key] = $arr[$key];

    }

return $new_array;

}

$person=array(

array('id'=>2,'name'=>'lhangsan','age'=>23),

array('id'=>5,'name'=>'zisi','age'=>28),

array('id'=>3,'name'=>'apple','age'=>17)

    );

$result = array_sort($person,'name',0);

print_r($result);

?>

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

<?php

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;

}

}

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

echo "<br />";

$arr2 = array(5,9,15,25,34,47,55,76);

echo bin_sch($arr2,0,7,47);

?>

洗牌算法

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

?>

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

function niu($y){

static $num= 1;

for ($i=1; $i <=$y ; $i++) {

if($i>=4 && $i<15){

$num++;

niu($y-$i);

}else if($i==20){

$num--;

}

return $num;

}

 PHP实现斐波那契数列

function fbnq($n){

$arr[1] = 1;

$arr[2] = 1;

for($i=3; $i<=$n; $i++){

$arr[$i] = $arr[$i-1] + $arr[$i-2];

    }

return $arr;

}

var_dump(array_values(fbnq(10)));die;

比较两个文件路径的相对

$b = '/a/b/c/d/e.php';

$a = '/a/b/f/g/j/h.php';

function diff($a, $b){

$aArr = explode('/',$a);

$bArr = explode('/',$b);

$bCount = count($bArr);

$k = 0;

for($i=0;$i<$bCount;$i++){

if($aArr[$i] != $bArr[$i]){

$k = $i;

break;

        }

    }

$result = array_merge(array_fill(1, $bCount-$k-1, '..'), array_slice($aArr,$k));

return implode('/', $result);

}

var_dump(diff($a, $b));die;

杨辉三角

<?php

class T{

private $num;

public function __construct($var=10) {

if ($var<3) die("值太小啦！");

$this->num=$var;

}

public function display(){

$n=$this->num;

$arr=array();

$arr[1]=array_fill(0,3,0);

$arr[1][1]=1;

echo str_pad(" ",$n*12," ");

printf("%3d",$arr[1][1]);

echo "<br/>";

for($i=2;$i<=$n;$i++){

$arr[$i]=array_fill(0,($i+2),0);

for($j=1;$j<=$i;$j++){

if($j==1)

echo str_pad(" ",($n+1-$i)*12," ");

printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);

echo "  ";

}

echo"<br/>";

}

}

}

$yh=new T('3');

$yh->display();

?>

有个人想上一个n级的台阶，每次只能迈1级或者迈2级台阶，问：这个人有多少种方法可以把台阶走完？例如：总共3级台阶，可以先迈1级再迈2级，或者先迈2级再迈1级，或者迈3次1级总共3中方式

function jieti($num){

return $num<2?1:jieti($num-1)+jieti($num-2);

}

请写一段PHP代码，确保多个进程同时写入同一个文件成功

<?php

$fp = fopen("lock.txt","w+");

if (flock($fp,LOCK_EX)) {

fwrite($fp, "write something");

flock($fp, LOCK_UN);

} else {

echo "file is locking...";

}

fclose($fp);

?>

无限级分类

function tree($arr,$pid=0,$level=0){

static $list = array();

foreach ($arr as $v) {

if ($v['pid'] == $pid) {

$v['level'] = $level;

$list[] = $v;

tree($arr,$v['id'],$level+1);

}

}

return $list;

}

获取上个月第一天 和 最后一天

date('Y-m-01',strtotime('-1 month'));

date('Y-m-t',strtotime('-1 month'));

随机输入一个数字能查询到对应的数据区间

function binsearch($x,$a){

$c=count($a);

$lower=0;

$high=$c-1;

while($lower<=$high){

$middle=intval(($lower+$high)/2);

if($a[$middle]>=$x){

$high=$middle-1;

}elseif($a[$middle]<=$x ){

$lower=$middle+1;

}

}

return '在区间'.$a[$high].'到'.$a[$lower];

}

$array = ['1','50','100','150','200','250','300'];

$a = '120';

echo binsearch($a,$array);

网址：PHP算法实战 https://www.yuejiaxmz.com/news/view/415595

相关内容

使用PHP构建个性化健身指导平台的实践与挑战
用PHP中的 == 运算符进行字符串比较
PHP中=>和
什么是php？php是什么？
【php毕业设计】基于php+mysql+apache的二手物品交易网站设计与实现（毕业论文+程序源码）——二手物品交易网站
php四种基础排序(基础算法)
PHP日期与时间应用与实践
通过php://filter/read=convert.base64
PHP和机器学习：如何进行推荐系统的个性化定制
yum安装php Requires: libzip5(x86

随便看看