PHP 面接での質問 アルゴリズムに関する質問
- 小云云オリジナル
- 2018-03-01 10:39:5917647ブラウズ
アルゴリズムの質問は PHP の面接の質問でよく出題されますが、この記事では主に PHP の面接の質問のアルゴリズムの質問を紹介し、皆様のお役に立てれば幸いです。
関連おすすめ: 「2019年PHP面接質問まとめ(集)」
面接質問 - アルゴリズム質問:
1. 挿入ソート(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]
1回目のソート後、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次元配列） 基本的な考え方：ソート対象のデータ要素の大きさをペアごとに比較し、順序が逆転している場合は、逆転したデータがなくなるまでデータを入れ替える要素。 ソート処理: ソートされた配列 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 7 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. クイックソート (1 次元配列) 基本的な考え方: 現在の順序付けされていない領域 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 回目の交換後 [27 38 49 97 76 13 65 49]
J は次のようにスキャンします左、3 回目の交換後、位置は変化しません [27 38 13 97 76 49 65 49]
右にスキャンします、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、文字列の削除
リーリー15, 文字列をコピー
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, 文字列を接続
function strcpy($s1, $s2){
if (strlen($s1)==NULL || !isset($s2)) return;
for ($i=0; $i<strlen($s1); $i++){
$s2[] = $s1[$i];
}
return $s2;
}17, 簡易エンコード関数(php_decode関数に相当)
function php_encode ($str) { if ($str=='' &&) strlen($str)>128) return false; for($i=0; $i
18. 簡易復号関数（php_encode関数に相当）
function strcat($s1, $s2){
if (!isset($s1) || !isset($s2)) return;
$newstr = $s1;
for($i=0; $i<count($s); $i++){
$newstr .= $st[$i];
}
return $newsstr;
}19. 簡易暗号化関数（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、簡易復号関数（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;
}関連する推奨事項:
プロジェクトでよく使用される Linux コマンドによって引き起こされる古典的なアルゴリズムの質問
js の文字と配列に関するいくつかの基本的なアルゴリズムの質問について簡単に説明します
以上がPHP 面接での質問 アルゴリズムに関する質問の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。