PHP面試題之算法題

2020-03-22 18:46:54

字體：大中小

來源：轉載

供稿：網友

php面試題中也會經常出現算法題，本文主要和大家分享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 $html' target='_blank'>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; }