Compiler des questions d'entretien courantes sur l'algorithme PHP

Cet article présente et organise les questions d'entretien courantes sur l'algorithme PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

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é, afin que le tableau reste en ordre jusqu'à ce que le tableau soit trié. l'élément de données doit être trié, trier jusqu'à ce que tous les éléments de données soient insérés.

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. Idée : à chaque passe, l'élément le plus petit (ou le plus grand) est sélectionné parmi les éléments de données à trier, et l'ordre est placé à la fin de la séquence triée 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]

Après le deuxième tri 13 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]

Après le cinquième tri 13 27 38 49 49 [97 97 76]

Après le sixième tri 13 27 38 49 49 76 [76 97]

Après le septième tri, 13 27 38 49 49 76 76 [97]

Le résultat final du tri est 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. idée : comparer les tailles des éléments de données à trier par paire, et lorsqu'on constate que l'ordre des deux é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 qu'une bulle légère qui viole ce principe est scannée, elle est amenée à « flotter » vers le haut. 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 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. Tri rapide (tableau unidimensionnel) Idée de base : Dans la zone non ordonnée actuelle R [1.. H ] Prenez n'importe quel élément de données comme "ligne de base" pour la comparaison (peut-être enregistré sous la forme R [I 1..H], et les éléments de données dans la sous-zone non ordonnée à gauche sont tous inférieurs ou égaux à l'élément de référence, les éléments de données dans la sous-zone non ordonnée à 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. Clé≤RI 1..H, lorsque R [1..I-1] et R [I 1..H] ne sont pas vides, effectuez le processus de division ci-dessus jusqu'à ce que tous les éléments de données des sous-zones non ordonnées soient triés. Exemple :

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

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

Deuxième après le troisiè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 Scan à droite, la position reste inchangée, après le quatrième échange [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]

Après trois tris 13 27 38 49 49 [65] 76 97

Tri final Résultat 13 27 38 49 49 65 76 97

Statut après chaque tri

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 (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 要查找的数组 
* @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;   
    } 
}

7. Suppression du tableau linéaire (implémenté dans un tableau)

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

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

9. 🎜>

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

11. Rechercher une chaîne

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

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. 🎜>15. Copiez une 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; 
}

17. Fonction d'encodage simple (correspondant à la fonction php_decode)

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

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

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

20. Fonction de décryptage simple (correspondant à la fonction php_encrypt)

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

Apprentissage recommandé : "

Tutoriel vidéo PHP

"

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!