PHP アルゴリズムの面接でよくある質問をまとめます

この記事は、PHP アルゴリズムの面接でよくある質問を紹介、整理したものです。一定の参考価値があります。困っている友人は参考にしてください。皆さんのお役に立てれば幸いです。

1. 挿入ソート (1 次元配列) 基本的な考え方: ソート対象のデータ要素が毎回、以前にソートされた配列内の適切な位置に挿入され、配列の順序が整うまで、すべてのデータ要素が挿入されるまでソートになります。

例:

[初期キーワード] [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. 選択ソート (1 次元配列) 基本アイデア: 各パスでは、ソート対象のデータ要素から最小 (または最大) の要素が選択され、ソート対象のすべてのデータ要素が配置されるまで、順序はソートされたシーケンスの最後に配置されます。例:

[初期キーワード] [49 38 65 97 76 13 27 49]

13 最初の並べ替え後 [38 65 97 76 49 27 49]

2 回目のソート 13 27 [65 97 76 49 38 49]

3 回目のソート後 13 27 38 [97 76 49 65 49]

4 回目のソート後 13 27 38 49 [49 97 65 76]

5 回目の並べ替え後 13 27 38 49 49 [97 97 76]

6 回目の並べ替え後 13 27 38 49 49 76 [76 97]

7 回目のソート、13 27 38 49 49 76 76 [97]

最終的なソート結果は 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 バブルソート (1 次元配列) 基本アイデア: ペアごとにソートされるデータ要素のサイズを比較し、2 つのデータ要素の順序が逆転していることが判明した場合、逆転したデータ要素がなくなるまでデータ要素を交換します。ソート処理: ソートされた配列 R[1..N] が垂直に配置され、各データ要素が重み付きバブルとみなされ、軽いバブルは重いバブルの下に存在できないという原理に従って、配列 R を下からスキャンします。この原則に違反する軽い泡がスキャンされるたびに、その泡は上向きに「浮き上がり」、最後の 2 つの泡が上部の軽い泡と下部の重い泡になるまでこのプロセスが繰り返されます。

例:

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. クイックソート（一次元配列） 基本的な考え方: 現在の順序付けされていない領域 R [1.. H ] 比較のための「ベースライン」として任意のデータ要素を取得します (おそらく R [I 1..H] として記録され、左側の順序付けされていないサブエリア内のデータ要素はすべて参照要素以下です。右側の順序なしサブエリアのデータ要素はすべて参照要素以上であり、参照 X は最終的な並べ替え位置、つまり R [1..I-1]≤X に位置します。 Key≤RI 1..H、R [1..I-1] と R [I 1..H] の両方が空でない場合、上記の除算プロセスは、順序付けされていないサブフィールド内のすべてのデータ要素が実行されるまで実行されます。エリアが整理されました。例:

最初のキーワード [49 38 65 97 76 13 27 49]

最初の交換後 [27 38 65 97 76 13 49 49]

2 回目 3 回目以降交換 [27 38 49 97 76 13 65 49]

J 左にスキャンすると、位置は変わりません。3 回目の交換後 [27 38 13 97 76 49 65 49]

I スキャン右にスキャンすると、4 回目の交換後も位置は変化しません [27 38 13 49 76 97 65 49]

J 左にスキャン [27 38 13 49 76 97 65 49]

(1回の分割処理)

初期キーワード [49 38 65 97 76 13 27 49]

1回のソート後 [27 38 13] 49 [76 97 65 49]

2 回の並べ替え後 [13] 27 [38] 49 [49 65] 76 [97]

3 回の並べ替え後 13 27 38 49 49 [65] 76 97

最終的な並べ替え結果 13 27 38 49 49 65 76 97

各ソート後のステータス

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. ヒル ソート (シェル ソート) — 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. 線形テーブルの削除 (配列で実装)

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. 文字列の長さ

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

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. 文字列のコピー

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. 簡易エンコード関数 (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; 
                $word = chr($c); 
                $s .= $word; 
            } 
            return $s; 
        }
    }
}

18. 簡易デコード関数 (php_encode 関数に相当)

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. 簡易暗号化関数 (php_decrypt 関数に相当)

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. 簡易復号化関数 (php_encrypt 関数に相当)

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

推奨学習: 「

PHP ビデオ チュートリアル」 "

以上がPHP アルゴリズムの面接でよくある質問をまとめますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。