首頁 >後端開發 >php教程 >PHP面試題之演算法題

PHP面試題之演算法題

小云云
小云云原創
2018-03-01 10:39:5917812瀏覽

php面試題中也會常出現演算法題,本文主要和大家分享PHP面試題之演算法題,希望能幫助大家。

相關推薦:《2019年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 297] 13#J=5(76) [38 49 65 76 297] 13
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]
在第二趟排序後133 13次排序後133。 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 38 49 38 38 38 38 38
97 65 38 4965 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 27 76 97 76 76 76 76
49 49 49 76 ee
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 97765199727 1997 271 97 49]
一趟排序之後[27 38 13] 49 [76 97 65 49]
二趟排序之後[13] 27 [38] 49 列名之後13 27 38 49 49 [65]76 97
最後的排序結果13 27 38 49 49 65 76 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; 
}

##5、希爾排序(shell sort)— O(n log n)
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;
    }
}

6、二分查找
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;
            }
        }
    }
}

7、線性表的刪除(在陣列中實作)
/** 
* 二分算法查找 
* @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; 	
    } 
}

8、字串長度

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

9、字串翻轉

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

10、字串比較
function strrev($str)	{ 	
    if ($str == &#39;&#39;) return 0; 	
    for ($i=(strlen($str)-1); $i>=0; $i--){ 	 
        $rev_str .= $str[$i]; 	
    } 	
    return $rev_str; 
}

11、尋找字串
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; 
}

12、字串替換
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; 
}

#13、插入一段字串
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; 
}

14、刪除一段字串

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

15、複製字串

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

16、連接字串
function strcpy($s1, $s2){ 
    if (strlen($s1)==NULL || !isset($s2)) return; 
    for ($i=0; $i<strlen($s1); $i++){ 
        $s2[] = $s1[$i]; 
    } 
    return $s2; 
}

17、簡單編碼函數(對應於php_decode函數)

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


18、簡單解碼函數(對應於php_encode)

function strcat($s1, $s2){ 
    if (!isset($s1) || !isset($s2)) return; 
    $newstr = $s1; 
    for($i=0; $i<count($s); $i++){ 
        $newstr .= $st[$i]; 
    } 
    return $newsstr; 
}

# 19.簡單加密函數(對應於php_decrypt函數)

function php_decode($str)	{ 
    if ($str==&#39;&#39; && 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; 
}

20、簡單解密函數(對應於php_encrypt)
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; 
}


#php的經典演算法題之分蘋果

#

一條專案中常用的linux指令引發的經典演算法題

#淺聊js中字元和陣列一些基本演算法題

#

以上是PHP面試題之演算法題的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn