PHP面试经典算法题整理

最近在准备PHP面试。看了几个经典的算法，记录一下

约瑟夫环（线性代数）

function king($n, $m){$p = 0;//上一轮出列序号for ($i = 2; $i <= $n; $i++) {$p = ($p+$m)%$i;}return $p+1;}

约瑟夫环（队列）

function king($n, $m){$arr = range(1, $n);$i = 0;while (count($arr) > 1) {if (($i+1)%$m == 0) {unset($arr[$i]);} else {array_push($arr, $arr[$i]);unset($arr[$i]);}$i++;}return array_shift($arr);}

有一母牛，到4岁可生育，每年一头，所生均是一样的母牛，到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。

function cows($n){$cow = array(1);for ($i = 1; $i <= $n; $i++) {$new_num = 0;foreach ($cow as $age => $num) {if ($age < 4 || $age > 14) continue;$new_num += $num;}array_unshift($cow, $new_num);array_slice($cow, 0, 20);}return array_sum($cow);}

冒泡排序

function bubbleSort($arr){$num = count($arr);for ($i = 0; $i < $num; $i++) {for ($j = 0; $j < $num - $i -1; $j++) {if ($arr[$j] > $arr[$j + 1]) {$temp = $arr[$j];$arr[$j] = $arr[$j+1];$arr[$j+1] = $temp;}}}return $arr;}

快速排序

function quickSort($arr){if (count($arr) <= 1) return $arr;$key = array_shift($arr);$leftArr = array();$rightArr = array();foreach ($arr as $value) {if ($key > $value) {$leftArr[] = $value;} else {$rightArr[] = $value;}}return array_merge(quickSort($leftArr), [$key], quickSort($rightArr));}

插入排序法

function insertSort($array){ //从小到大排列　　//先默认$array[0]，已经有序，是有序表　　for($i = 1;$i < count($array);$i++){　　　　$insertVal = $array[$i]; //$insertVal是准备插入的数　　　　$insertIndex = $i - 1; //有序表中准备比较的数的下标　　　　while($insertIndex >= 0 && $insertVal < $array[$insertIndex]){　　　　　　$array[$insertIndex + 1] = $array[$insertIndex]; //将数组往后挪　　　　　　$insertIndex--; //将下标往前挪，准备与前一个进行比较　　　　}　　　　if($insertIndex + 1 !== $i){　　　　　　$array[$insertIndex + 1] = $insertVal;　　　　}　　}}

选择排序

function selectSort($arr){$newArr = array();while (count($arr) > 1) {$min = null;$minKey = null;foreach ($arr as $key => $value) {if (is_null($min) || is_null($minKey)) {$min = $value;$minKey = $key;} elseif ($min > $value) {$min = $value;$minKey = $key;}}$newArr[] = $min;unset($arr[$minKey]);}$newArr[] = current($arr);return $newArr;}

多进程读写同一文件问题

function fileRead($file){$fp = fopen($file, \'w+\');$retry = 1;//LOCK_SH共享锁定（读取的程序）、LOCK_EX独占锁定（写入的程序）while (!flock($fp, LOCK_EX) && $retry < 10) {$retry++;}if ($retry >= 10) {return false;}$data = \'good\';fwrite($fp, $data);flock($fp, LOCK_UN);fclose($fp);}

读取文件夹下的文件

function dirFile($dir){if (is_file($dir)) return $dir;$source = opendir($dir);while ($file = readdir($source)) {if (in_array($file, [\'.\', \'..\'])) {continue;} elseif (is_dir($dir.\'/\'.$file)) {$fileArr[$dir][] = dirFile($dir.\'/\'.$file);} else {$fileArr[] = $dir.\'/\'.$file;}}closedir($source);return $fileArr;}

判断括号闭合，多种类型

function checkClose($str){$checkStr = array(\'(\'=>\')\', \'{\'=>\'}\', \'[\'=>\']\');$queue = array();$len = strlen($str);for($i=0; $i<$len; $i++) {if (isset($checkStr[$str[$i]])) {array_push($queue, $str[$i]);} elseif (in_array($str[$i], $checkStr)) {//若出现右半部分括号，则必须与栈中最后一个元素相匹配，否则即为不是闭合的if ($str[$i] != $checkStr[end($queue)]) {return false;}array_pop($queue);} else {continue;}}return empty($queue);}

判断括号闭合，一种括号类型

function checkCloseOne($str){$d = 0;$len = strlen($str);for ($i = 0; $i < $len; $i++) {if ($str[$i] == \'(\') {$d++;}if ($str[$i] == \')\') {$d--;}if ($d < 0) {return false;}}if ($d == 0) return true;return false;}