Questions d'entrevue PHP Questions sur l'algorithme

Les questions d'algorithme apparaissent souvent dans les questions d'entretien PHP. Cet article partage principalement avec vous les questions d'algorithme des questions d'entretien PHP, dans l'espoir d'aider tout le monde.

Recommandations associées : "Résumé des questions d'entretien PHP 2019 (collection) "

Questions d'entretien - questions d'algorithme :

1 . Tri par insertion (tableau unidimensionnel) L'idée de base : Chaque fois qu'un élément de données à trier est inséré à la position appropriée dans le tableau précédemment trié, de sorte que le tableau soit toujours en ordre jusqu'à ce que tous les éléments de données à trier soient ajoutés. sont jusqu'à ce que l'insertion soit terminée. Exemple :

[mot-clé initial] [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. Tri par sélection (tableau unidimensionnel) Idée de base : Chaque passe sélectionne le plus petit (ou le plus grand) élément parmi les éléments de données à trier, l'ordre. est placé à la fin du tableau trié jusqu'à ce que tous les éléments de données à trier soient disposés. Exemple :

[Mot clé initial] [49 38 65 97 76 13 27 49]
13 après le premier tri [38 65 97 76 49 27 49]
13 après le deuxième tri 27 [65 97 76 49 38 49]
Après le troisième tri 13 27 38 [97 76 49 65 49]
Après le quatrième tri 13 27 38 49 [49 97 65 76]
Le cinquième Après le sixième passage de tri , 13 27 38 49 49 [97 97 76]
Après le sixième passage de tri, 13 27 38 49 49 76 [76 97]
Après le septième passage de tri, 13 27 38 49 49 76 76 [ 97]
Résultat final du tri 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. Tri à bulles (tableau unidimensionnel) Idée de base : Comparez les tailles des éléments de données à trier par paire. paire, et constatez que les deux Lorsque l'ordre des éléments de données est inversé, ils sont échangés jusqu'à ce qu'il n'y ait plus d'éléments de données inversés. Processus de tri : Imaginez que le tableau trié R [1..N] soit érigé verticalement et que chaque élément de données soit considéré comme une bulle pondérée. Selon le principe selon lequel les bulles légères ne peuvent pas se trouver sous les bulles lourdes, le tableau R est balayé par le bas. vers le haut. Chaque fois que des bulles légères qui violent ce principe sont scannées, elles sont amenées à « flotter » vers le haut, et ce processus est répété jusqu'à ce que les deux dernières bulles soient la plus légère en haut et la plus lourde en bas. exemple : 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



4. Tri rapide (tableau unidimensionnel) Idée de base : prendre n'importe quel élément de données dans la zone non ordonnée actuelle R[1..H] comme "ligne de base" pour la comparaison (il peut être enregistré comme X), utilisez ceci. Le benchmark divise la zone désordonnée actuelle en deux zones désordonnées plus petites à gauche et à droite : R[1..I-1] et R[I 1..H], et les éléments de données à gauche la sous-zone désordonnée est inférieure ou égale à l'élément de référence, les éléments de données dans la sous-zone non ordonnée de droite sont tous supérieurs ou égaux à l'élément de référence et la référence X est située à la position de tri finale, c'est-à-dire R [1..I-1]≤X.Key≤RI 1..H, lorsque R[1..I-1] et R[I 1..H] ne sont pas vides, effectuez le processus de division mentionné ci-dessus sur eux respectivement jusqu'à ce que tous les éléments de données dans les sous-zones non ordonnées aient été triés. Exemple :

Mot clé initial [49 38 65 97 76 13 27 49]

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

Après le premier échange [27 38 65 97 76 13 49 49]

---

Après le deuxième échange [27 38 49 97 76 13 65 49]

J scanne vers la gauche, la position reste inchangée, après le troisième échange [27 38 13 97 76 49 65 49]

I scanne vers la droite, la position reste inchangée, le quatrième échange Après [27 38 13 49 76 97 65 49]

J scan à gauche [27 38 13 49 76 97 65 49]
(processus d'une division)
mot-clé initial [49 38 65 97 76 13 27 49]
Après un tri [27 38 13] 49 [76 97 65 49]
Après deux tris [13] 27 [38] 49 [49 65] 76 [97]
Trois tris Après cela 13 27 38 49 49 [65] 76 97
Le résultat final du tri 13 27 38 49 49 65 76 97
Le statut après chaque tri



5. 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. Recherche binaire

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. Suppression du tableau linéaire (dans l'implémentation du tableau)

/** 
* 二分算法查找 
* @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. Longueur des cordes

---

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. Retournement des cordes

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

---

10. Comparaison des cordes

function strrev($str)	{ 	
    if ($str == '') return 0; 	
    for ($i=(strlen($str)-1); $i>=0; $i--){ 	 
        $rev_str .= $str[$i]; 	
    } 	
    return $rev_str; 
}

---

11. . Chaîne de recherche

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. Remplacement de chaîne

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. Insérer une chaîne de paragraphe

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. chaîne

---

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. Copier la chaîne

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. Caractère de connexion Chaîne

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

---

17. function (correspondant à la fonction php_decode)

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

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

---

18.

19. Fonction de cryptage simple (correspondant à la fonction php_decrypt)

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

---

20. Fonction de décryptage simple (correspondant à la fonction 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; 
}

Recommandations associées :

---

L'algorithme classique de PHP interroge Apple

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

Une question d'algorithme classique causée par une commande Linux couramment utilisée dans le projet

Une brève discussion de quelques questions d'algorithme de base sur les caractères et les tableaux en js

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!