• 技术文章 >后端开发 >php教程

    整理常见的PHP算法面试题

    藏色散人藏色散人2021-06-01 09:07:31转载1006
    本篇文章向大家介绍整理常见的PHP算法面试题,有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。

    1、插入排序(一维数组) 基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。

    示例:

    [初始关键字] [49] 38 65 97 76 13 27 49

    J=2(38) [38 49] 65 97 76 13 27 49

    J=3(65) [38 49 65] 97 76 13 27 49

    J=4(97) [38 49 65 97] 76 13 27 49

    J=5(76) [38 49 65 76 97] 13 27 49

    J=6(13) [13 38 49 65 76 97] 27 49

    J=7(27) [13 27 38 49 65 76 97] 49

    J=8(49) [13 27 38 49 49 65 76 97]

    function insert_sort($arr){
        $count = count($arr);   
        for($i=1; $i<$count; $i++){      
            $tmp = $arr[$i];        
            $j = $i - 1;        
            while($arr[$j] > $tmp){          
                $arr[$j+1] = $arr[$j];          
                $arr[$j] = $tmp;            
                $j--;           
            }    
        }    
        return $arr; 
    }

    2、选择排序(一维数组) 基本思想:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 示例:

    [初始关键字] [49 38 65 97 76 13 27 49]

    第一趟排序后 13 [38 65 97 76 49 27 49]

    第二趟排序后 13 27 [65 97 76 49 38 49]

    第三趟排序后 13 27 38 [97 76 49 65 49]

    第四趟排序后 13 27 38 49 [49 97 65 76]

    第五趟排序后 13 27 38 49 49 [97 97 76]

    第六趟排序后 13 27 38 49 49 76 [76 97]

    第七趟排序后 13 27 38 49 49 76 76 [97]

    最后排序结果 13 27 38 49 49 76 76 97

    function select_sort($arr){     
        $count = count($arr);   
        for($i=0; $i<$count; $i++){      
            $k = $i;        
            for($j=$i+1; $j<$count; $j++){           
                if ($arr[$k] > $arr[$j]) $k = $j;        
            }       
            if($k != $i){           
                $tmp = $arr[$i];            
                $arr[$i] = $arr[$k];            
                $arr[$k] = $tmp;        
            }   
        }   
        return $arr; 
    }

    3、冒泡排序(一维数组) 基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。 排序过程:设想被排序的数组 R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则, 从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就使其向上” 漂浮”,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

    示例:

    49 13 13 13 13 13 13 13

    38 49 27 27 27 27 27 27

    65 38 49 38 38 38 38 38

    97 65 38 49 49 49 49 49

    76 97 65 49 49 49 49 49

    13 76 97 65 65 65 65 65

    27 27 76 97 76 76 76 76

    49 49 49 76 97 97 97 97

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

    4、快速排序(一维数组) 基本思想:在当前无序区 R [1..H] 中任取一个数据元素作为比较的” 基准”(不妨记为 X), 用此基准将当前无序区划分为左右两个较小的无序区:R [1..I-1] 和 R [I 1..H],且左边的无序子区中数据元素均小于等于基准元素, 右边的无序子区中数据元素均大于等于基准元素,而基准 X 则位于最终排序的位置上,即 R [1..I-1]≤X.Key≤RI 1..H, 当 R [1..I-1] 和 R [I 1..H] 均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。 示例:

    初始关键字 [49 38 65 97 76 13 27 49]

    第一次交换后 [27 38 65 97 76 13 49 49]

    第二次交换后 [27 38 49 97 76 13 65 49]

    J 向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49]

    I 向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49]

    J 向左扫描 [27 38 13 49 76 97 65 49]

    (一次划分过程)

    初始关键字 [49 38 65 97 76 13 27 49]

    一趟排序之后 [27 38 13] 49 [76 97 65 49]

    二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]

    三趟排序之后 13 27 38 49 49 [65]76 97

    最后的排序结果 13 27 38 49 49 65 76 97

    各趟排序之后的状态

    function quickSort(&$arr){    
        if(count($arr)>1){
            $k=$arr[0];
            $x=array();
            $y=array();
            $_size=count($arr);        
            for($i=1;$i<$_size;$i++){            
                if($arr[$i]<=$k){
                    $x[]=$arr[$i];
                }elseif($arr[$i]>$k){
                    $y[]=$arr[$i];
                }
            }
            $x=quickSort($x);
            $y=quickSort($y);        
            return array_merge($x,array($k),$y);
        }else{ 
            return$arr;
        }
    }

    5、希尔排序(shell sort)— O (n log n)

    functionshell_sort(&$arr){    
        if(!is_array($arr))return;
        $n=count($arr);    
        for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){
            for($i=$gap;$i<$n;++$i){
                for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){                
                    $temp=$arr[$j];                
                    $arr[$j]=$arr[$j+$gap];                
                    $arr[$j+$gap]=$temp;
                }
            }
        }
    }

    6、二分查找

    /** 
    * 二分算法查找 
    * @param array $array 要查找的数组 
    * @param int $min_key 数组的最小下标 
    * @param int $max_key 数组的最大下标 
    * @param mixed $value 要查找的值 
    * @return boolean 
    */ 
    function bin_search($array,$min_key,$max_key,$value){             
        if($min_key <= $max_key){ 
            $key = intval(($min_key+$max_key)/2); 
            if($array[$key] == $value){ 
                return true; 
            }elseif($value < $array[$key]){ 
                return bin_search($array,$min_key,$key-1,$value);
            }else{ 
                return bin_search($array,$key+1,$max_key,$value);
            }   
        }else{      
            return false;   
        } 
    }

    7、线性表的删除(数组中实现)

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

    8、字符串长度

    function strlen($str)   { 
        if ($str == '') return 0; 
        $count = 0; 
        while (1){ 
            if ($str[$count] != NULL){ 
                $count++; 
                continue; 
            }else{ 
                break; 
            } 
        } 
        return $count; 
    }

    9、字符串翻转

    function strrev($str)   {   
        if ($str == '') return 0;   
        for ($i=(strlen($str)-1); $i>=0; $i--){   
            $rev_str .= $str[$i];   
        }   
        return $rev_str; 
    }

    10、字符串比较

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

    11、查找字符串

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

    12、字符串替换

    function str_replace($substr, $newsubstr, $str) { 
        $m = strlen($str); 
        $n = strlen($substr); 
        $x = strlen($newsubstr); 
        if (strchr($str, $substr) == false) return false; 
        for ($i=0; $i<=($m-$n+1); $i++){ 
            $i = strchr($str, $substr); 
            $str = str_delete($str, $i, $n); 
            $str = str_insert($str, $i, $newstr); 
        } 
        return $str; 
    }

    13、插入一段字符串

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

    14、删除一段字符串

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

    15、复制字符串

    function strcpy($s1, $s2){ 
        if (strlen($s1)==NULL || !isset($s2)) return; 
        for ($i=0; $i<strlen($s1); $i++){ 
            $s2[] = $s1[$i]; 
        } 
        return $s2; 
    }
    16、连接字符串
    function strcat($s1, $s2){ 
        if (!isset($s1) || !isset($s2)) return; 
        $newstr = $s1; 
        for($i=0; $i<count($s); $i++){ 
            $newstr .= $st[$i]; 
        } 
        return $newsstr; 
    }

    17、简单编码函数(与 php_decode 函数对应)

    function php_encode($str)    { 
        if ($str=='' && strlen($str)>128) 
            return false;
        for($i=0; $i<strlen($str); $i++){ 
            $c = ord($str[$i]); 
            if ($c>31 && $c<107) 
                $c += 20; 
                if ($c>106 && $c<127) 
                    $c -= 75; 
                    $word = chr($c); 
                    $s .= $word; 
                } 
                return $s; 
            }
        }
    }

    18、简单解码函数(与 php_encode 函数对应)

    function php_decode($str)   { 
        if ($str=='' && strlen($str)>128) return false; 
        for($i=0; $i<strlen($str); $i++){ 
            $c = ord($word); 
            if ($c>106 && $c<127) $c = $c-20; 
            if ($c>31 && $c<107) $c = $c+75; 
            $word = chr($c); 
            $s .= $word; 
        } 
        return $s; 
    }

    19、简单加密函数(与 php_decrypt 函数对应)

    function php_encrypt($str)  {   
        $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
        $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359';  
        if (strlen($str) == 0) return false;     
        for ($i=0; $i<strlen($str); $i++){    
            for ($j=0; $j<strlen($encrypt_key); $j++){    
                if ($str[$i] == $encrypt_key[$j]){   
                    $enstr .= $decrypt_key[$j];      
                    break;   
                }    
            }    
        }   
        return $enstr; 
    }

    20、简单解密函数(与 php_encrypt 函数对应)

    function php_decrypt($str)  { 
        $encrypt_key = 'abcdefghijklmnopqrstuvwxyz1234567890';
        $decrypt_key = 'ngzqtcobmuhelkpdawxfyivrsj2468021359'; 
        if (strlen($str) == 0) return false; 
        for ($i=0; $i<strlen($str); $i++){ 
            for ($j=0; $j<strlen($decrypt_key); $j++){ 
                if ($str[$i] == $decrypt_key[$j]){ 
                    $enstr .= $encrypt_key[$j]; 
                    break; 
                } 
            } 
        } 
        return $enstr; 
    }

    推荐学习:《PHP视频教程

    以上就是整理常见的PHP算法面试题的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:learnku,如有侵犯,请联系admin@php.cn删除
    专题推荐:php算法面试题
    上一篇:有关于PHP关键特性之命名空间的一些看法!!! 下一篇:利用debug_backtrace自定义个基本的日志打印函数(PHP代码示例)
    第16期线上培训班

    相关文章推荐

    • 总结分享一些关于redis缓存的面试题• 总结PHP面试题“数据库”相关知识• 汇总PHP核心技术经典面试题• 来会会有点水平的PHP基础面试题• 七道PHP经典面试题(附答案)

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网