일반적인 PHP 알고리즘 인터뷰 질문 컴파일
- 藏色散人앞으로
- 2021-05-28 13:42:555187검색
이 글은 일반적인 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 1차 정렬 후 [38 65 97 76 49 27 49]
13 27 2차 정렬 후 [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이 아래쪽부터 스캔된다고 상상해 보세요. 이 원리를 위반하는 가벼운 거품이 스캔되면 위쪽으로 "부유"됩니다. 마지막 두 개의 거품이 위쪽에 있고 무거운 거품이 아래쪽에 있을 때까지 이 과정이 반복됩니다.
예:
49 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 9 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]의 데이터 요소를 비교를 위한 "기준선"으로 선택하고(X로 기록될 수 있음) 이 기준을 사용하여 현재 무질서한 영역을 왼쪽의 두 개의 더 작은 무질서한 영역으로 나눕니다. 오른쪽: R [1..I-1] 및 R [I 1..H], 왼쪽의 순서가 지정되지 않은 하위 영역의 데이터 요소는 모두 참조 요소보다 작거나 같습니다. 오른쪽의 정렬되지 않은 하위 영역은 모두 참조 요소보다 크거나 같습니다. 벤치마크 X는 최종 정렬 위치에 있습니다. 즉, R [1..I-1] ≤ ]가 비어 있지 않으면 위에서 언급한 작업을 수행합니다. 순서가 지정되지 않은 하위 영역의 모든 데이터 요소가 정렬될 때까지 각각에 대한 분할 프로세스를 수행합니다. 예:
초기 키워드 [49 38 65 97 76 13 27 49]
첫 번째 교환 후 [27 38 65 97 76 13 49 49]
두 번째 교환 후 [27 38 49 97 76 13 65 49 ]
J 왼쪽 스캔, 세 번째 교환 후 위치 변경되지 않음 [27 38 13 97 76 49 65 49]
I 오른쪽 스캔, 네 번째 교환 후 위치 변경 없음 [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 ]
두 번 정렬 후 [13] 27 [38] 49 [49 65] 76 [97]
세 번 정렬 후 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. Hill 정렬(쉘 정렬) — 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;
}17. 단순 인코딩 기능(php_decode 기능에 해당)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;
}18. 단순 디코딩 기능(php_encode 기능에 해당)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;
}
}
}19. 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;
}추천 학습: "
PHP 비디오 튜토리얼위 내용은 일반적인 PHP 알고리즘 인터뷰 질문 컴파일의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!