Heim > Artikel > Backend-Entwicklung > PHP-Interviewfragen, Algorithmusfragen
PHP-Interviewfragen, Algorithmusfragen
- 小云云Original
- 2018-03-01 10:39:5917647Durchsuche
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;
}Nach dem ersten Austausch [27 38 65 97 76 13 49 49] Nach dem zweiten Austausch [27 38 49 97 76 13 65 49]
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;
}
}
6. Binäre Suche
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. Löschen der linearen Tabelle (in Array-Implementierung)
/**
* 二分算法查找
* @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. Saitenlängefunction 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. Saitenumdrehenfunction strlen($str) {
if ($str == '') return 0;
$count = 0;
while (1){
if ($str[$count] != NULL){
$count++;
continue;
}else{
break;
}
}
return $count;
}10. Saitenvergleich
function strrev($str) {
if ($str == '') return 0;
for ($i=(strlen($str)-1); $i>=0; $i--){
$rev_str .= $str[$i];
}
return $rev_str;
}
11 . Suchzeichenfolge
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. Zeichenfolgenersetzung 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. Löschen Sie a Zeichenfolge 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;
}15. Zeichenfolge kopieren 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;
}16. Verbindungszeichenfolge 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;
}17 Funktion (entspricht der Funktion 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; $s .= $word; return $s;
function strcpy($s1, $s2){
if (strlen($s1)==NULL || !isset($s2)) return;
for ($i=0; $i<strlen($s1); $i++){
$s2[] = $s1[$i];
}
return $s2;
}19. Einfache Verschlüsselungsfunktion (entsprechend der php_decrypt-Funktion)
function strcat($s1, $s2){
if (!isset($s1) || !isset($s2)) return;
$newstr = $s1;
for($i=0; $i<count($s); $i++){
$newstr .= $st[$i];
}
return $newsstr;
}20. Einfache Entschlüsselungsfunktion (entsprechend der php_encrypt-Funktion)
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;
}
PHPs klassischer Algorithmus stellt Apple in Frage
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!