您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)常見(jiàn)的PHP算法面試題有哪些,小編覺(jué)得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
1、插入排序(一維數(shù)組) 基本思想:每次將一個(gè)待排序的數(shù)據(jù)元素,插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置,使數(shù)列依然有序;直到待排序數(shù)據(jù)元素全部插入完為止。
示例:
[初始關(guān)鍵字] [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、選擇排序(一維數(shù)組) 基本思想:每一趟從待排序的數(shù)據(jù)元素中選出最小(或最大)的一個(gè)元素,順序放在已排好序的數(shù)列的最后,直到全部待排序的數(shù)據(jù)元素排完。 示例:
[初始關(guān)鍵字] [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]
最后排序結(jié)果 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、冒泡排序(一維數(shù)組) 基本思想:兩兩比較待排序數(shù)據(jù)元素的大小,發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換,直到?jīng)]有反序的數(shù)據(jù)元素為止。 排序過(guò)程:設(shè)想被排序的數(shù)組 R[1..N]垂直豎立,將每個(gè)數(shù)據(jù)元素看作有重量的氣泡,根據(jù)輕氣泡不能在重氣泡之下的原則, 從下往上掃描數(shù)組 R,凡掃描到違反本原則的輕氣泡,就使其向上” 漂浮”,如此反復(fù)進(jìn)行,直至最后任何兩個(gè)氣泡都是輕者在上,重者在下為止。
示例:
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、快速排序(一維數(shù)組) 基本思想:在當(dāng)前無(wú)序區(qū) R [1..H] 中任取一個(gè)數(shù)據(jù)元素作為比較的” 基準(zhǔn)”(不妨記為 X), 用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū):R [1..I-1] 和 R [I 1..H],且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素, 右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素,而基準(zhǔn) X 則位于最終排序的位置上,即 R [1..I-1]≤X.Key≤RI 1..H, 當(dāng) R [1..I-1] 和 R [I 1..H] 均非空時(shí),分別對(duì)它們進(jìn)行上述的劃分過(guò)程,直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?示例:
初始關(guān)鍵字 [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]
(一次劃分過(guò)程)
初始關(guān)鍵字 [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
最后的排序結(jié)果 13 27 38 49 49 65 76 97
各趟排序之后的狀態(tài)
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 要查找的數(shù)組 * @param int $min_key 數(shù)組的最小下標(biāo) * @param int $max_key 數(shù)組的最大下標(biāo) * @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、線性表的刪除(數(shù)組中實(shí)現(xiàn))
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、字符串長(zhǎng)度
function strlen($str) { if ($str == '') return 0; $count = 0; while (1){ if ($str[$count] != NULL){ $count++; continue; }else{ break; } } return $count; }
9、字符串翻轉(zhuǎn)
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、復(fù)制字符串
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、簡(jiǎn)單編碼函數(shù)(與 php_decode 函數(shù)對(duì)應(yīng))
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、簡(jiǎn)單解碼函數(shù)(與 php_encode 函數(shù)對(duì)應(yīng))
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、簡(jiǎn)單加密函數(shù)(與 php_decrypt 函數(shù)對(duì)應(yīng))
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、簡(jiǎn)單解密函數(shù)(與 php_encrypt 函數(shù)對(duì)應(yīng))
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; }
關(guān)于“常見(jiàn)的PHP算法面試題有哪些”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺(jué)得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。