item name queue lis 双向 joseph test 数据结构和算法
- <?php
- class Test implements Iterator{
- private $item = array('id'=>1,'name'=>'php');
- public function rewind(){
- reset($this->item);
- }
- public function current(){
- return current($this->item);
- }
- public function key(){
- return key($this->item);
- }
- public function next(){
- return next($this->item);
- }
- public function valid(){
- return($this->current()!==false);
- }
- }
- //测试
- $t=new Test;
- foreach($t as $k=>$v){
- echo$k,'--->',$v,'<br/>';
- }
- ?>
- <?php
- class Deque{
- private $queue=array();
- public function addFirst($item){
- return array_unshift($this->queue,$item);
- }
- public function addLast($item){
- return array_push($this->queue,$item);
- }
- public function removeFirst(){
- return array_shift($this->queue);
- }
- public function removeLast(){
- return array_pop($this->queue);
- }
- }
- ?>
- <?php
- // 冒泡排序
- function bubble_sort(&$arr){
- for ($i=0,$len=count($arr); $i < $len; $i++) {
- for ($j=1; $j < $len-$i; $j++) {
- if ($arr[$j-1] > $arr[$j]) {
- $temp = $arr[$j-1];
- $arr[$j-1] = $arr[$j];
- $arr[$j] = $temp;
- }
- }
- }
- }
- // 测试
- $arr = array(10,2,36,14,10,25,23,85,99,45);
- bubble_sort($arr);
- print_r($arr);
- ?>
- <?php
- //快速排序
- function partition(&$arr,$low,$high){
- $pivotkey = $arr[$low];
- while($low<$high){
- while($low < $high && $arr[$high] >= $pivotkey){
- $high--;
- }
- $temp = $arr[$low];
- $arr[$low] = $arr[$high];
- $arr[$high] = $temp;
- while($low < $high && $arr[$low] <= $pivotkey){
- $low++;
- }
- $temp=$arr[$low];
- $arr[$low]=$arr[$high];
- $arr[$high]=$temp;
- }
- return$low;
- }
- function quick_sort(&$arr,$low,$high){
- if($low < $high){
- $pivot = partition($arr,$low,$high);
- quick_sort($arr,$low,$pivot-1);
- quick_sort($arr,$pivot+1,$high);
- }
- }
- ?>
该算法是通过分治递归来实现的,其效率很大程度上取决于参考元素的选择,可以选择数组的中间元素,也可以随机得到三个元素,然后选择中间的那个元素(三数中值法)。
另外还有一点,就是当我们在分割时,如果分割出来的子序列的长度很小的话(小于 5 到 20),通常递归的排序的效率就没有诸如插入排序或希尔排序那么快了。因此可以会去判断数组的长度,如果小于 10 的话,直接用插入排序,而不再递归调用这个快速排序。
这是著名的约瑟夫环问题
- <?php
- // 方案一,使用php来模拟这个过程
- function king($n,$m){
- $mokey = range(1, $n);
- $i = 0;
- while (count($mokey) >1) {
- $i += 1;
- $head = array_shift($mokey);//一个个出列最前面的猴子
- if ($i % $m !=0) {
- #如果不是m的倍数,则把猴子返回尾部,否则就抛掉,也就是出列
- array_push($mokey,$head);
- }
- // 剩下的最后一个就是大王了
- return $mokey[0];
- }
- }
- // 测试
- echo king(10,7);
- // 方案二,使用数学方法解决
- function josephus($n,$m){
- $r = 0;
- for ($i=2; $i <= $m ; $i++) {
- $r = ($r + $m) % $i;
- }
- return $r+1;
- }
- // 测试
- print_r(josephus(10,7));
- ?>
- <?php
- //二维数组排序,$arr是数据,$keys是排序的健值,$order是排序规则,1是降序,0是升序
- function array_sort($arr,$keys,$order=0){
- if(!is_array($arr)){
- return false;
- }
- $keysvalue=array();
- foreach($arr as $key => $val){
- $keysvalue[$key] = $val[$keys];
- }
- if($order == 0){
- asort($keysvalue);
- }else{
- arsort($keysvalue);
- }
- reset($keysvalue);
- foreach($keysvalue as $key => $vals){
- $keysort[$key] = $key;
- }
- $new_array=array();
- foreach($keysort as $key=> $val){
- $new_array[$key]=$arr[$val];
- }
- return$new_array;
- }
- //测试
- $person=array(
- array('id'=>2,'name'=>'zhangsan','age'=>23),
- array('id'=>5,'name'=>'lisi','age'=>28),
- array('id'=>3,'name'=>'apple','age'=>17)
- );
- $result = array_sort($person,'name',1);
- print_r($result);
- ?>
4
7/15
75%,每只老鼠都有顺时针、逆时钟两种运动方向,3 只老鼠共有 8 种运动情况,只有当 3 只老鼠都为顺时针或者逆时钟,它们才不会相遇,剩余的 6 中情况都会相遇,故相遇的概率为 6/8=75%。
- <?php
- /**
- * 顺序查找
- * @param array $arr 数组
- * @param $k 要查找的元素
- * @return mixed 成功返回数组下标,失败返回-1
- */
- function seq_sch($arr,$k){
- for ($i=0,$n = count($arr); $i < $n; $i++) {
- if ($arr[$i] == $k) {
- break;
- }
- }
- if($i < $n){
- return $i;
- }else{
- return -1;
- }
- }
- /**
- * 二分查找,要求数组已经排好顺序
- * @param array $array 数组
- * @param int $low 数组起始元素下标
- * @param int $high 数组末尾元素下标
- * @param $k 要查找的元素
- * @return mixed 成功时返回数组下标,失败返回-1
- */
- function bin_sch($array,$low,$high,$k){
- if ($low <= $high) {
- $mid = intval(($low + $high) / 2);
- if ($array[$mid] == $k) {
- return $mid;
- } elseif ($k < $array[$mid]) {
- return bin_sch($array,$low,$mid - 1,$k);
- } else{
- return bin_sch($array,$mid + 1,$high,$k);
- }
- }
- return -1;
- }
- // 测试:顺序查找
- $arr1 = array(9,15,34,76,25,5,47,55);
- echo seq_sch($arr1,47);//结果为6
- echo "<br />";
- // 测试:二分查找
- $arr2 = array(5,9,15,25,34,47,55,76);
- echo bin_sch($arr2,0,7,47);//结果为5
- ?>
- <?php
- $card_num = 54;//牌数
- function wash_card($card_num){
- $cards = $tmp = array();
- for($i = 0;$i < $card_num;$i++){
- $tmp[$i] = $i;
- }
- for($i = 0;$i < $card_num;$i++){
- $index = rand(0,$card_num-$i-1);
- $cards[$i] = $tmp[$index];
- unset($tmp[$index]);
- $tmp = array_values($tmp);
- }
- return $cards;
- }
- // 测试:
- print_r(wash_card($card_num));
- ?>
冒泡排序,快速排序,插入排序,选择排序
php 面试题之二——数据结构和算法(高级部分)
来源: http://www.bubuko.com/infodetail-2222238.html