二、 数据结构和算法
1.使对象可以像数组一样进行 foreach 循环， 要求属性必须是私有。 (Iterator 模式的 PHP5实现， 写一类实现 Iterator 接口)（腾讯）
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 functionvalid(){ return($this->current()!==false);}} //测试
$t=new Test;foreach($t as
$k=>$v){ echo$k,'--->',$v,'
';
}?>
2.用 PHP 实现一个双向队列（腾讯）
addFirst($item){ return array_unshift($this->queue,$item);} public function addLast($item){ returnarray_push($this->queue,$item);} public function removeFirst(){ returnarray_shift($this->queue);} public function removeLast(){ returnarray_pop($this->queue);}
}?>
3.请使用冒泡排序法对以下一组数据进行排序 10 2 36 14 10 25 23 85 99 45。
// 冒泡排序
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);?>
4.写出一种排序算法（要写出代码） ， 并说出优化它的方法。 （新浪）
//快速排序
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 的话， 直接用插入排序， 而不再递归调用这个快速排序。
5.一群猴子排成一圈， 按 1， 2， ...， n 依次编号。 然后从第 1 只开始数， 数到第 m 只,把它踢出圈， 从它后面再开始数， 再数到第 m 只， 在把它踢出去...， 如此不停的进行下去，直到最后只剩下一只猴子为止， 那只猴子就叫做大王。 要求编程模拟此过程， 输入 m、 n输出最后那个大王的编号。 （新浪） （小米）这是著名的约瑟夫环问题// 方案一， 使用 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));?>
6.写一个二维数组排序算法函数， 能够具有通用性， 可以调用 php 内置函数。
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);
} r
eset($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,'nam
e'=>'apple','age'=>17)
);
$result = array_sort($person,'name',1);
print_r($result);?>
7.用二分法查找一个长度为 10 的排好序的线性表， 查找不成功时最多需要比较次数是（小米）4
8.从 0,1,2,3,4,5,6,7,8,9， 这十个数字中任意选出三个不同的数字， “三个数字中不含 0和 5” 的概率是（小米）
7/15
9.一个三角形三个顶点有 3 只老鼠， 一声枪响， 3 只老鼠开始沿三角形的边匀速运动， 请问他们相遇的概率是（小米）75%， 每只老鼠都有顺时针、 逆时钟两种运动方向， 3 只老鼠共有 8 种运动情况， 只有当 3只老鼠都为顺时针或者逆时钟， 它们才不会相遇， 剩余的 6 中情况都会相遇， 故相遇的概率为 6/8=75%。
10.描述顺序查找和二分查找（也叫做折半查找） 算法， 顺序查找必须考虑效率， 对象可以是一个有序数组（小米）/**
* 顺序查找
* @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);//结果为
6echo "
"; // 测试： 二分查找
$arr2 = array(5,9,15,25,34,47,55,76); echo bin_sch($arr2,0,7,47);//
结果为 5?>
11.我们希望开发一款扑克游戏， 请给出一套洗牌算法， 公平的洗牌并将洗好的牌存储在一个整形数组里。 （鑫众人云）
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));?>
12.写出你所知道的排序方法（亿邮）冒泡排序， 快速排序， 插入排序， 选择排序
微信+17031115530，拉测试微信群交流
网友评论