Algorithmusfragen tauchen häufig in PHP-Interviewfragen auf. In diesem Artikel werden hauptsächlich die Algorithmusfragen von PHP-Interviewfragen mit Ihnen geteilt, in der Hoffnung, allen zu helfen.
Verwandte Empfehlungen: „Zusammenfassung der PHP-Interviewfragen 2019 (Sammlung) “
Interviewfragen – Algorithmusfragen:
1 . Einfügungssortierung (eindimensionales Array) Die Grundidee: Jedes Mal, wenn ein zu sortierendes Datenelement an der entsprechenden Position im zuvor sortierten Array eingefügt wird, bleibt das Array erhalten, bis alle zu sortierenden Datenelemente vorhanden sind sind, bis die Einfügung abgeschlossen ist. Beispiel:
[Anfangsschlüsselwort] [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. Auswahlsortierung (eindimensionales Array) Grundidee: Jeder Durchgang wählt das kleinste (oder größte) Element aus den zu sortierenden Datenelementen aus, die Reihenfolge wird am Ende des sortierten Arrays platziert, bis alle zu sortierenden Datenelemente angeordnet sind. Beispiel:
[Initial keyword] [49 38 65 97 76 13 27 49]
13 nach der ersten Sortierung [38 65 97 76 49 27 49]
13 nach der zweiten Sortierung 27 [65 97 76 49 38 49]
Nach der dritten Sortierung 13 27 38 [97 76 49 65 49]
Nach der vierten Sortierung 13 27 38 49 [49 97 65 76]
Die fünfte Nach dem sechsten Sortierdurchgang , 13 27 38 49 49 [97 97 76]
Nach dem sechsten Sortierdurchgang, 13 27 38 49 49 76 [76 97]
Nach dem siebten Sortierdurchgang, 13 27 38 49 49 76 76 [ 97]
Endgültiges Sortierergebnis 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. Blasensortierung (eindimensionales Array) Grundidee: Vergleichen Sie die Größen der zu sortierenden Datenelemente paarweise Paar und stellen Sie fest, dass die beiden Datenelemente bei umgekehrter Reihenfolge so lange ausgetauscht werden, bis keine Datenelemente mehr in umgekehrter Reihenfolge vorhanden sind. Sortiervorgang: Stellen Sie sich vor, dass das sortierte Array R [1..N] vertikal aufgebaut ist und jedes Datenelement als gewichtete Blase betrachtet wird. Gemäß dem Prinzip, dass sich leichte Blasen nicht unter schweren Blasen befinden können, wird das Array R von unten gescannt Nach oben Wenn leichte Blasen, die gegen dieses Prinzip verstoßen, gescannt werden, werden sie zum „Schwimmen“ gebracht, und dieser Vorgang wird wiederholt, bis die letzten beiden Blasen die leichtere oben und die schwerere unten sind. Beispiel: 49
76 97 65 49 49 49 49 4913 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97. 97
4. Schnelle Sortierung (eindimensionales Array) Grundidee: Nehmen Sie ein beliebiges Datenelement im aktuellen ungeordneten Bereich R[1..H] als „Basislinie“ zum Vergleich (es kann aufgezeichnet werden). als X), verwenden Sie dies. Der Benchmark unterteilt den aktuellen ungeordneten Bereich in zwei kleinere ungeordnete Bereiche links und rechts: R[1..I-1] und R[I 1..H] und die Datenelemente auf der linken Seite Der ungeordnete Unterbereich ist kleiner oder gleich dem Referenzelement, die Datenelemente im ungeordneten Unterbereich rechts sind alle größer oder gleich dem Referenzelement und die Referenz X befindet sich an der endgültigen Sortierposition, also R [1..I-1]≤X.Key≤RI 1..H, Wenn sowohl R[1..I-1] als auch R[I 1..H] nicht leer sind, führen Sie den oben genannten Divisionsprozess durch auf diesen jeweils so lange, bis alle Datenelemente in den ungeordneten Teilbereichen sortiert sind. Beispiel:
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;
}J scannt nach links, die Position bleibt unverändert, nach dem dritten Austausch [27 38 13 97 76 49 65 49]
I scannt nach rechts, die Position bleibt unverändert, nach dem vierten Austausch [27 38 13 49 76 97 65 49]J-Scan links [27 38 13 49 76 97 65 49]
(ein Teilungsprozess)
Anfangsschlüsselwort [49 38 65 97 76 13 27 49]
Nach einer Sortierung [27 38 13] 49 [76 97 65 49]
Nach zwei Sortierungen [13] 27 [38] 49 [49 65] 76 [97]
Drei Sortierungen Danach 13 27 38 49 49 [65] 76 97
Das endgültige Sortierergebnis 13 27 38 49 49 65 76 97
Der Status nach jeder Sortierung
5. Hope 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;
}
}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;
}
}
}
}/**
* 二分算法查找
* @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;
}
}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;
}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;
}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;
}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<count($s); $i++){
$newstr .= $st[$i];
}
return $newsstr;
}Verwandte Empfehlungen:
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;
}Eine kurze Diskussion einiger grundlegender Algorithmusfragen zu Zeichen und Arrays in js
Das obige ist der detaillierte Inhalt vonPHP-Interviewfragen, Algorithmusfragen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
Algorithmus zum Ersetzen von Seiten
So öffnen Sie eine PHP-Datei
So entfernen Sie die ersten paar Elemente eines Arrays in PHP
Was tun, wenn die PHP-Deserialisierung fehlschlägt?
So verbinden Sie PHP mit der MSSQL-Datenbank
So verbinden Sie PHP mit der MSSQL-Datenbank
So laden Sie HTML hoch
So lösen Sie verstümmelte Zeichen in PHP
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
