1 function BubbleSort(&$arr){ 2 for($i=0;$i
1 $arr=[3,5,1,3,7,8,9,5,0,5]; 2 QuickSort($arr,0,count($arr)-1); 3 echo json_encode($arr); 4 function QuickSort(&$arr,$left,$right){ 5 if($left<$right){ 6 $key=$arr[$left]; 7 $low=$left; 8 $high=$right; 9 while ($low < $high) {10 while ($arr[$high] >= $key && $low < $high) {11 $high --;12 }13 $arr[$low]=$arr[$high];14 while ($arr[$low] <= $key && $low < $high) {15 $low ++;16 }17 $arr[$high]=$arr[$low];18 }19 $arr[$low]=$key;20 QuickSort($arr,$left,$low-1);21 QuickSort($arr,$low+1,$right);22 }23 }
1 $arr1=[0,3,5,5,7,8,9,20,30,57]; 2 echo binarySearch($arr1,20); 3 function binarySearch($arr,$element){ 4 $left = 0; 5 $right = count($arr)-1; 6 while ($left<$right){ 7 $mid =round(($left+$right)/2); 8 if($arr[$mid]>$element){ 9 $right = $mid-1;10 11 }else if($arr[$mid]<$element){12 $left = $mid+1;13 }else{14 return $mid;15 }16 }17 return -1;18 }
1 function moveTower($n,$A="A",$B="B",$C="C"){ 2 if($n==1){ 3 echo "{ $n}:{ $A}-->{ $C}\n"; 4 }else{ 5 //将最上面的n-1个从A通过C移动到B 6 $this->moveTower($n-1,$A,$C,$B); 7 //将最下面第n个最大的盘子直接从A移动到C 8 echo "{ $n}:{ $A}-->{ $C}\n"; 9 //再将现在都在B上的n-1个从B通过A移动到C上10 $this->moveTower($n-1,$B,$A,$C);11 }12 }
1 class StackByQueue{ 2 private $queue1=null; 3 private $queue2=null; 4 function __construct() 5 { 6 $this->queue1 = new \SplQueue(); 7 $this->queue2 = new \SplQueue(); 8 } 9 function __destruct()10 {11 $this->queue1=null;12 $this->queue2=null;13 }14 15 public function Pop(){16 if($this->queue1->isEmpty()){17 return null;18 }19 while($this->queue1->count()!=1){20 $this->queue2->enqueue($this->queue1->dequeue());21 }22 $pop = $this->queue1->dequeue();23 while(!$this->queue2->isEmpty()){24 $this->queue1->enqueue($this->queue2->dequeue());25 }26 return $pop;27 28 }29 public function Push($ele){30 $this->queue1->enqueue($ele);31 }32 }
1 class QueueByStack{ 2 private $stack1=null; 3 private $stack2 = null; 4 function __construct() 5 { 6 $this->stack1 = new \SplStack(); 7 $this->stack2 = new \SplStack(); 8 } 9 function __destruct()10 {11 $this->stack1 = null;12 $this->stack2 = null;13 }14 15 public function EnQueue($ele){16 $this->stack1->push($ele);17 }18 public function DeQueue(){19 while(!$this->stack1->isEmpty()){20 $this->stack2->push($this->stack1->pop());21 }22 if($this->stack2->isEmpty()){23 return null;24 }else{25 $pop = $this->stack2->pop();26 while(!$this->stack2->isEmpty()){27 $this->stack1->push($this->stack2->pop());28 }29 return $pop;30 }31 }32 }
早晨一女生背着一堆书出了图书馆，结果警报响了，大妈让女生看看是哪本书把警报弄响了，那女生把书倒出来，准备一本一本的测。大妈见状急了，把书分成两份，第一份过了一下，响了。又把这一份分成两份接着测，三回就找到了，大妈用鄙视的眼神看着女生，仿佛在说O(n)和O(logn)都分不清。
结果图书馆丢了n-1本书。class TreeNode{ public $number = 0; public $level = 0; public $originNumber = 0; public function __construct($originNumber0, $number0, $level0) { $this->number = $number0; $this->level = $level0; $this->originNumber = $originNumber0; }}function getHalf(TreeNode $treeNode, &$arr){ $maxLevel = 4; $number = $treeNode->number; $level = $treeNode->level; $originNumber = $treeNode->originNumber; $a_half = intval($number / 2); $b_half = $number - $a_half; $level++; if ($level > $maxLevel || $a_half == 0 || $b_half == 0) { return; } if (($a_half == 1 && $level == $maxLevel) || ($b_half == 1 && $level == $maxLevel)) { !in_array($originNumber, $arr) && $arr[] = $originNumber; return; } if ($a_half > 1) { getHalf(new TreeNode($originNumber, $a_half, $level), $arr); } if ($b_half > 1) { getHalf(new TreeNode($originNumber, $b_half, $level), $arr); }}$arr0 = [];for ($i = 0; $i < 1000; $i++) { getHalf(new TreeNode($i, $i, 0), $arr0);}echo json_encode($arr0);die;输出：[9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31]
1 class STreeNode 2 { 3 public $level = 0; 4 public $leftChild = null; 5 public $rightChild = null; 6 public $parent = null; 7 public $key = null; 8 public $data = null; 9 } 10 11 class STree 12 { 13 14 public $root = null; 15 16 public function __construct(STreeNode $root) 17 { 18 $this->root = $root; 19 } 20 21 /** 22 * @desc: 二叉树节点插入 23 * @author: 流火行者 24 * @date: 2019/3/12 6:41 PM 25 * --------------------------------- 26 * 支付宝首页搜“510992378”查看留言 27 * --------------------------------- 28 * @param STreeNode $childNode 29 * @param STreeNode $parentNode 30 */ 31 public function insert(STreeNode $childNode, STreeNode $parentNode) 32 { 33 $childNode->level = $parentNode->level + 1; 34 $childNode->parent = $parentNode; 35 $childNode->data = []; 36 if ($childNode->key > $parentNode->key) { 37 if ($parentNode->rightChild == null) { 38 $parentNode->rightChild = $childNode; 39 } else { 40 $this->insert($childNode, $parentNode->rightChild); 41 } 42 } else { 43 if ($parentNode->leftChild == null) { 44 $parentNode->leftChild = $childNode; 45 } else { 46 $this->insert($childNode, $parentNode->leftChild); 47 } 48 } 49 } 50 51 public function search($key, STreeNode $parentNode = null, &$list = []) 52 { 53 if ($parentNode == null) return; 54 if ($key == $parentNode->key) { 55 $list[] = $parentNode; 56 } else { 57 $this->search($key, $parentNode->leftChild, $list); 58 $this->search($key, $parentNode->rightChild, $list); 59 } 60 } 61 62 public function delete() 63 { 64 65 } 66 67 /** 68 * @desc: 递归前序遍历 69 * @author: 流火行者 70 * @date: 2019/3/12 6:41 PM 71 * --------------------------------- 72 * 支付宝首页搜“510992378”查看留言 73 * --------------------------------- 74 * @param STreeNode|null $node 75 */ 76 public function preOrderTraverse(STreeNode $node = null) 77 { 78 if ($node == null) return; 79 echo $node->key . PHP_EOL; 80 $this->inOrderTraverse($node->leftChild); 81 $this->inOrderTraverse($node->rightChild); 82 } 83 84 public function preOrderTraverseLoop() 85 { 86 $stack = new SplStack(); 87 $pNode = $this->root; 88 while (!$stack->isEmpty() || $pNode != null) { 89 if ($pNode != null) { 90 echo $pNode->key . PHP_EOL; 91 $stack->push($pNode); 92 $pNode = $pNode->leftChild; 93 } else { 94 $node = $stack->pop(); 95 96 $pNode = $node->rightChild; 97 98 } 99 }100 }101 102 /**103 * @desc: 递归中序遍历104 * @author: 流火行者105 * @date: 2019/3/12 6:41 PM106 * ---------------------------------107 * 支付宝首页搜“510992378”查看留言108 * ---------------------------------109 * @param STreeNode|null $node110 */111 public function inOrderTraverse(STreeNode $node = null)112 {113 if ($node == null) return;114 $this->inOrderTraverse($node->leftChild);115 echo $node->key . '|level=' . $node->level . PHP_EOL;116 $this->inOrderTraverse($node->rightChild);117 }118 119 /**120 * @desc: 循环中序遍历121 * @author: 流火行者122 * @date: 2019/3/12 6:40 PM123 * ---------------------------------124 * 支付宝首页搜“510992378”查看留言125 * ---------------------------------126 */127 public function inOrderTraverseLoop()128 {129 $stack = new SplStack();130 $pNode = $this->root;131 while ($pNode != null || !$stack->isEmpty()) {132 if ($pNode != null) {133 $stack->push($pNode);134 $pNode = $pNode->leftChild;135 } else {136 $node = $stack->pop();137 echo $node->key . '|';138 $pNode = $node->rightChild;139 }140 }141 }142 143 /**144 * @desc: 后序遍历（递归）145 * @author: 流火行者146 * @date: 2019/3/12 6:40 PM147 * ---------------------------------148 * 支付宝首页搜“510992378”查看留言149 * ---------------------------------150 * @param STreeNode|null $node151 */152 public function postOrderTraverse(STreeNode $node = null)153 {154 if ($node == null) return;155 $this->postOrderTraverse($node->leftChild);156 $this->postOrderTraverse($node->rightChild);157 echo $node->key . PHP_EOL;158 }159 160 /**161 * @desc: 循环后序遍历162 * @author: 流火行者163 * @date: 2019/3/12 6:58 PM164 * ---------------------------------165 * 支付宝首页搜“510992378”查看留言166 * ---------------------------------167 */168 public function postOrderTraverseLoop()169 {170 //todo171 }172 173 /**174 * @desc: 层次遍历175 * @author: 流火行者176 * @date: 2019/3/12 6:40 PM177 * ---------------------------------178 * 支付宝首页搜“510992378”查看留言179 * ---------------------------------180 */181 public function layerOrderTraverseLoop()182 {183 $queue = new SplQueue();184 $queue->enqueue($this->root);185 echo PHP_EOL;186 while (!$queue->isEmpty()) {187 $o = $queue->dequeue();188 if (empty($o)) break;189 echo 'key=' . $o->key . "#level=" . $o->level . PHP_EOL;190 if ($o->leftChild != null) {191 $queue->enqueue($o->leftChild);192 }193 if ($o->rightChild != null) {194 $queue->enqueue($o->rightChild);195 }196 }197 }198 199 }200 201 $arr = [3, 7, 2, 4, 6, 9];202 //$arr = [2,7,3,6,9,2.5,4];203 204 //$arr = array_reverse($arr);205 $rootNode = new STreeNode();206 $rootNode->level = 0;207 $rootNode->key = 5;208 $rootNode->data = [];209 $tree = new STree($rootNode);210 foreach ($arr as $item) {211 $node = new STreeNode();212 $node->key = $item;213 $node->data = [];214 $tree->insert($node, $rootNode);215 }216 //$tree->inOrderTraverse($tree->root);217 //$tree->inOrderTraverseLoop();218 $tree->postOrderTraverse($rootNode);219 echo PHP_EOL;220 $tree->postOrderTraverseLoop();221 //$tree->layerOrderTraverseLoop();222 $list = [];223 //$tree->search(37,$tree->root,$list);
1 $list = [3, 5, 1, 2, 7, 3, 8, 2, 9]; 2 3 mergerSort($list, 0, count($list) - 1); 4 5 function mergerSort(&$arr = [], $left, $right) 6 { 7 $mid = intval(($left + $right) / 2); 8 if ($left < $right) { 9 mergerSort($arr, $left, $mid);10 mergerSort($arr, $mid + 1, $right);11 echo 'left:'.json_encode(array_slice($arr, $left, $mid - $left + 1)) . PHP_EOL;12 echo 'right:'.json_encode(array_slice($arr, $mid + 1, $right - $mid)) . PHP_EOL;13 mergeArray($arr,$left,$mid,$right);14 }15 }16 17 function mergeArray(&$arr = [], $left, $mid, $right)18 {19 $i = $left;20 $j = $mid + 1;21 $k = 0;22 $temp = [];23 //有序两个数组合并24 while ($i <= $mid && $j <= $right) {25 if ($arr[$i] <= $arr[$j]) {26 $temp[$k++] = $arr[$i++];27 } else {28 $temp[$k++] = $arr[$j++];29 }30 }31 //左侧剩余的直接合并，左和右只可能有一个有剩余32 while ($i <= $mid) {33 $temp[$k++] = $arr[$i++];34 }35 //右侧剩余的直接合并36 while ($j <= $right) {37 $temp[$k++] = $arr[$j++];38 }39 //修改原数组40 $k=0;41 while ($left<=$right){42 $arr[$left++] = $temp[$k++];43 }44 echo 'merge'.json_encode($temp) . PHP_EOL;45 echo PHP_EOL;46 }47 48 输出：49 left:[3]50 right:[5]51 merge[3,5]52 53 left:[3,5]54 right:[1]55 merge[1,3,5]56 57 left:[2]58 right:[7]59 merge[2,7]60 61 left:[1,3,5]62 right:[2,7]63 merge[1,2,3,5,7]64 65 left:[3]66 right:[8]67 merge[3,8]68 69 left:[2]70 right:[9]71 merge[2,9]72 73 left:[3,8]74 right:[2,9]75 merge[2,3,8,9]76 77 left:[1,2,3,5,7]78 right:[2,3,8,9]79 merge[1,2,2,3,3,5,7,8,9]
未完待续....