生成 public lis hex 内存 常见 count col
冒泡排序
- <?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);
- ?>
快速排序
- function quick_sort($array) {
- if (count($array) <= 1) return $array;
- $key = $array[0];
- $left_arr = array();
- $right_arr = array();
- for ($i=1; $i<count($array); $i++){
- if ($array[$i] <= $key)
- $left_arr[] = $array[$i];
- else
- $right_arr[] = $array[$i];
- }
- $left_arr = quick_sort($left_arr);
- $right_arr = quick_sort($right_arr);
- return array_merge($left_arr, array($key), $right_arr);
- }
经典猴子选大王算法
- <?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 内置函数。
- <?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);
- ?>
顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组
- <?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 实现一个双向队列
- <?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);
- }
- }
- ?>
有 5 个人偷了一堆苹果,准备在第二天分赃。晚上,有一人遛出来,把所有菜果分成 5 份,但是多了一个,顺手把这个扔给树上的猴了,自己先拿 1/5 藏了。没想到其他四人也都是这么想的,都如第一个人一样分成 5 份把多的那一个扔给了猴,偷走了 1/5。第二天,大家分赃,也是分成 5 份多一个扔给猴了。最后一人分了一份。问:共有多少苹果?
- for ($i = 1; ; $i++)
- {
- if ($i%5 == 1) {
- //第一个人取五分之一,还剩$t
- $t = $i - round($i/5) - 1;
- if($t % 5 == 1)
- {
- //第二个人取五分之一,还剩$r
- $r = $t - round($t/5) - 1;
- if($r % 5 == 1)
- {
- //第三个人取五分之一,还剩$s
- $s = $r - round($r/5) - 1;
- if($s % 5 == 1)
- {
- //第四个人取五分之一,还剩$x
- $x = $s - round($s/5) - 1;
- if($x % 5 == 1)
- {
- //第五个人取五分之一,还剩$y
- $y = $x - round($x/5) - 1;
- if ($y % 5 == 1) {
- echo $i;
- break;
- }
- }
- }
- }
- }
- }
- }
汉诺塔游戏:
1. 有三根杆子 A,B,C。A 杆上有若干碟子
2. 每次移动一块碟子, 小的只能叠在大的上面
3. 把所有碟子从 A 杆全部移到 C 杆上
- function hanoi($n, $x, $y, $z) {
- if ($n == 1) {
- echo'move disk 1 from'.$x.'to'.$z."\n";
- } else {
- hanoi($n - 1, $x, $z, $y);
- echo'move disk'.$n.'from'.$x.'to'.$z."\n";
- hanoi($n - 1, $y, $x, $z);
- }
- }
- hanoi(3, 'A', 'B', 'C');
ShortUrl 短网址算法
1、将长网址 md5 生成 32 位签名串, 分为 4 段, 每段 8 个字节;
2、对这四段循环处理, 取 8 个字节, 将他看成 16 进制串与 0x3fffffff(30 位 1) 与操作, 即超过 30 位的忽略处理;
3、这 30 位分成 6 段, 每 5 位的数字作为字母表的索引取得特定字符, 依次进行获得 6 位字符串;
4、总的 md5 串可以获得 4 个 6 位串; 取里面的任意一个就可作为这个长 url 的短 url 地址;
存储数据库使用 TTServer 等 Nosql 比较合适。
- <?php
- function shorturl($input) {
- $base32 = array (
- 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
- 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
- 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
- 'y', 'z', '0', '1', '2', '3', '4', '5'
- );
- $hex = md5($input);
- $hexLen = strlen($hex);
- $subHexLen = $hexLen / 8;
- $output = array();
- for ($i = 0; $i < $subHexLen; $i++) {
- //把加密字符按照8位一组16进制与0x3FFFFFFF(30位1)进行位与运算
- $subHex = substr ($hex, $i * 8, 8);
- $int = 0x3FFFFFFF & (1 * ('0x'.$subHex));
- $out = '';
- for ($j = 0; $j < 6; $j++) {
- //把得到的值与0x0000001F进行位与运算,取得字符数组chars索引
- $val = 0x0000001F & $int;
- $out .= $base32[$val];
- $int = $int >> 5;
- }
- $output[] = $out;
- }
- return $output;
- }
- ?>
- 整理一下进制的转换
- 二进制转换十进制:
- 10101转换成十进制如下:
- 从右边数分别标注为0,1,2,3,4即:2^0*1 + 2^1*0 + 2^2*1 + 2^3*0 + 2^4*1 = 1 + 0 + 4 + 0 + 16 = 21;
- 十进制转换成二进制:
- 21转换成二进制如下:
- 21对2取余分别是10余1, 5余0, 2余1, 1余0即:最后一个余数是1不能再除2 因此:10101
- 十六进制:
- 它由0-9,A-F组成,字母不区分大小写,A-F对应10-15;
- 一般为了区分十六进制我们习惯在前面加个'0x'例如十六进制 32和0x32 其实是一样的
- 十六进制转换成十进制:
- 0x32转换成十进制如下:
- 从右边数分别标注为0,1 即:16^0*2 + 16^1*3 = 2 + 48 = 50;
- 十进制转换成十六进制:
- 50转换成十六进制如下:
- 50对16取余是3余2 最后一个余数是3不能再除16 因此:32 习惯变成0x32
- 位运算:
- 程序中的所有数在计算机内存中都是以二进制的形式储存的,位运算说穿了,就是直接对整数在内存中的二进制位进行操作。
- 举个例子,6的二进制是110,11的二进制是1011,那么6 and (&)11的结果就是2,它是二进制对应位进行逻辑运算的结果(0表示False,1表示True,空位都当0处理)。
- 6可以看成是0110 11是1011 位运算得到的就是10 即:2
- 位运算中还有个 >> 移位(从右边移位) 例如:6 >> 1 & 11
- 6可以看成是0110 >> 移1位 变成0011 然后再& 11(1011)就得到11 即:3
- 备注: x & y 将得到的数是0 ~ x的值
常见算法 php 实现
来源: http://www.bubuko.com/infodetail-2252652.html