时间复杂度:
O(2^n)
function fib($n){
if( in_array($n, [0, 1]) ) return $n;
return fib($n-1) + fib($n-2);
}时间复杂度:
O(n), 空间复杂度:O(1)
function fib($n){
if( in_array($n, [0, 1]) ) return $n;
$f0 = 0;
$f1 = 1;
$f2 = null;
for($i=0; $i<$n; $i++){
$f2 = $f0 + $f1;
$f0 = $f1;
$f1 = $f2;
}
return $f2;
}function roll($arr){
//获取数组中所有值的和
$count = array_sum($arr);
$rand = 0;
foreach($arr as $k => $v){
$rand = mt_rand(1, $count);
if( $rand <= $v){
return $k;
}
else{
$rand -= $v;
}
}
}
$array = ['a' => 5, 'b' => 3, 'c' => 1];
echo roll($array);
function poker($array){
$count = count($array);
for($i=0; $i<$count; $i++){
$rand = rand(200, 300);
$index = $rand % $count;
$tmp = $array[$i];
$array[$i] = $array[$index];
$array[$index] = $tmp;
}
return $array;
}
$array = array('a', 'b', 'c', 'd', 'e', 'f', 'g');
print_r( poker($array) );
<?php
class Node {
public $data;
public $next;
public function __construct($data=null, $next=null){
$this->data = $data;
$this->next = $next;
}
}
class Link {
public $head=null;
public $size=0;
public function __construct(){
//$this->head = new Node();
}
//遍历
public function traverse(){
//当前指针位置移动到头部
$curIndex = $this->head;
$tmp = [];
//移动指针一直到没有数据位置
while( !is_null($curIndex) ){
array_push($tmp, $curIndex->data);
//移动指针到当前的下一个节点
$curIndex = $curIndex->next;
}
return $tmp;
}
//头插
public function addAtHead($data){
$node = new Node($data, $this->head);
$this->head = $node;
$this->size++;
return $this;
}
//尾插
public function addAtTail($data){
$node = new Node($data);
$curIndex = $this->head;
//判断当前链表是否为空
if( is_null($curIndex) ){
$this->head = $node;
}
else{
//如果链表不为空，则进行遍历
while( !is_null($curIndex->next) ){
$curIndex = $curIndex->next;
}
$curIndex->next = $node;
}
$this->size++;
return $this;
}
public function addAtIndex($data, $index){
//判断index是头尾的情况
$count = $this->size;
if( $index <= 0 ){
$this->addAtHead($data);
}
if( $index > $count ){
$this->addAtTail($data);
}
//将指针移动到index-1的位置
$curIndex = $this->head;
for($i=0;$i<$index-1;$i++){
$curIndex = $curIndex->next;
}
//新建一个节点，其next是index之后的链表
$node = new Node($data, $curIndex->next);
$curIndex->next = $node;
$this->size++;
return $this;
}
public function delAtIndex($index){
$count = $this->size;
$curIndex = $this->head;
//如果删除的是第一个节点
if( $index == 0 ){
$this->head = $curIndex->next;
$this->size--;
return $this;
}
//如果删除的是最后一个节点
if( $index < 0 || $index > $count ){
echo "没有这个节点\n";
return $this;
}
//将指针移到index-1的位置
for($i=0;$i<$index-1;$i++){
$curIndex = $curIndex->next;
}
//echo "<pre>"; print_r($curIndex);exit;
//此时，curIndex->next所处的位置，也就是index
//将从index开始的链表赋给tmp(tmp所处的位置 = index+2)
$tmp = $curIndex->next;
//index+2后的链表赋值跟index
$curIndex->next = $tmp->next;
$this->size--;
return $this;
}
public function print(){
print_r( $this );
}
}
$link = new Link;
$link->addAtHead(3)
->addAtHead(2)
->addAtHead(1)
->addAtTail(8)
->addAtTail(4)
->addAtTail(5)
->addAtIndex(10, 3)
->delAtIndex(2)
->print();
//$res = $link->traverse();
//$size = $link->size;
//echo "{$size}<pre>"; print_r($res);exit;
从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒
N 个数字来排队,两两相比小靠前,外层循环 N-1,内层循环 N-1-i
function bobble($arr){
//获取长度
$count = count($arr);
//第一层, 控制轮次
for($i=0; $i<$count-1; $i++){
//内循环, 对比当前跟后一个值, 调换大的
for($k=0; $k<$count-1-$i; $k++){
if( $arr[$k] > $arr[$k+1]){
$tmp = $arr[$k+1];
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
选择第一个元素为基准元素, 比基准元素大的放入右边, 比基准元素小的放入左边; 递归左右元素排序后, 合并
function quick($arr){
//获取数组长度
$count = count($arr);
//判断是否需要继续二分
if( $count <= 1 ) return $arr;
//定义一个基准值
$base = $arr[0];
//定义两个栈用于存放结果
$left = [];
$right = [];
//遍历
for($i=1; $i<$count; $i++){
if( $arr[$i] > $base ){
$right[] = $arr[$i];
}
else{
$left[] = $arr[$i];
}
}
//递归处理left/right
$left = quick($left);
$right = quick($right);
//合并
return array_merge($left, [$base], $right);
}在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止
function select($arr){
$count = count($arr);
//第一层, 控制轮次
for($i=0; $i<$count-1; $i++){
//先假设最小值在第一位
$p = $i;
for($k=$i+1; $k<$count; $k++){
//$arr[$p] 是当前已知最小值
if($arr[$p] > $arr[$k]){
//比较并记录最小值位置
$p = $k;
}
}
//最小值保存到$p; 如果位置与当前假设位置不同, 则位置互换
if( $p != $i ){
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}假设前面的数已经是排好顺序的, 现在要把第n个数插到前面的有序数中, 使得这n个数也是排好顺序的; 如此反复循环,直到全部排好顺序
function insert($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
//内层循环进行比较并插入
for($k=$i-1;$k>=0;$k--){
if($tmp < $arr[$k]){
//发现插入的元素较小, 则将后面元素与前面元素互换
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
else{
//如果碰到不需要移动的元素, 不再进行比较
break;
}
}
}
return $arr;
}function order($arr, $find){
$count = count($arr);
for($i=0; $i<$count-1; $i++){
if($find == $arr[$i]){
return $i;
}
}
return false;
}function binary($arr, $find){
$mid = floor(count($arr) / 2);
//取数组中间值, 如果中间值即是查找值, 则返回下标
if( $find == $arr[$mid] ){
return $mid;
}
//数组从中间位置分割成left / right 两部分
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid+1, $mid);
//如果查找值小于中间值, 则递归查找left数组
if( $find < $arr[$mid] ){
return binary($left, $find);
}
//如果查找值大于中间值, 则递归查找right数组
if( $find > $arr[$mid] ){
return binary($right, $find);
}
}顶部出栈, 尾部入栈, 循环遍历
function ysf($n, $m){
$i = 1;
while(true){
if( count($n) <= 1 ){
return $n;
}
$tmp = array_shift($n);
if( $i != $m){
array_push($n, $tmp);
$i++;
continue;
}
$i = 1;
}
}
$foo = range(1, 10);
print_r(ysf($foo, 11));function gg($n){
for($i=1;$i<=5;$i++){
if( ($n - 1) % 5 == 0 ){
$n = ($n - 1) / 5 * 4;
//echo $n;
continue;
}
return false;
}
return true;
}
//从小到大进行试探
$n = 1;
while(true){
//因为需要被5整除, 所以此处可以改成`$n = $n+5`以降低试探次数
$n++;
if( gg($n) ){
echo $n;exit;
}
}Copyright © 2016 yjiang's cake