几个面试算法

几个面试算法

 

 

#!/usr/local/php7/bin/php
<?php
$arr = array(1,3,9,23,54);
//螺旋矩阵
$matrix = [
 [ 1, 2, 3  ,4 ,5],
 [ 6, 7, 8  ,9,10],
 [ 11,12,13,14,15],
 [ 16,17,18,19,20],
 [ 21,22,23,24,25]
];

// echo   "23 的位置：".erfen($arr,0,count($arr),23)."\n\n";
// print_r(bucket($arr));
// print_r(quickSort($arr));
// print_r(mergeSort($arr));
print_r(matrix($matrix));




//二分查找
function erfen($arr,$low,$hight,$find){	
	$mid = ceil(($low+$hight)/2);
	if($arr[$mid] == $find){
		return $mid;
	}elseif($arr[$mid] > $find){
		return erfen($arr,$mid-1,$hight,$find);
	}elseif($arr[$mid] < $find){
		return erfen($arr,$mid+1,$hight,$find);
	}
	
	// while($low <= $hight){
		// $mid = ceil(($low+$hight)/2);
		// echo $mid."\n";
		// if($arr[$mid]==$find){
			// return $mid;
		// }elseif($arr[$mid]<$find){
			// $low   = $mid+1;                
		// }else{
			// $hight = $mid-1;
		// }
	// }
	return -1;
}

// 木桶排序
function bucket($parameter){
	$bucket = [];
    $arrayStore =array_fill(0, max($parameter)+1, 0);
    $count = count($parameter);
    foreach($parameter as $k => $v){
        $arrayStore[$v]++;
    }
    foreach($arrayStore as $k => $v){
        if($v>0){
            for($j=0;$j<$v;$j++){
                $bucket[]= $k;
            }
        }
    }
	return $bucket;
}

// 快排
function quickSort(array $arr){
    $count = count( $arr );
    if( $count <= 1 ) return $arr;

    $left = $right = array();
    $base = $arr[0];
	
	for($i = 1;$i<$count ;$i++){
		if($arr[$i] < $base){
			$left[] = $arr[$i];
		}else{
			$right[] = $arr[$i];
		}
	}
	return array_merge(quickSort($left),(array)$base,quickSort($right));
}

//归并
function mergeSort(array $numbers=array()) 
{
    $count = count( $numbers );
    if( $count <= 1 ) return $numbers;

    $half  = ceil( $count / 2 );
    $arr2d = array_chunk($numbers, $half);

    $left   = mergeSort($arr2d[0]);
    $right  = mergeSort($arr2d[1]);

    while (count($left) && count($right))
    {
        if ($left[0] < $right[0])
            $reg[] = array_shift($left);
        else
            $reg[] = array_shift($right);
    }
    return array_merge($reg, $left, $right);
}


//螺旋矩阵
function matrix($arr){
	$row = count($arr);		//高
	$col=count($arr[0]);	//宽
	$result = array();
	$small = $col < $row ? $col : $row;
	$count = ceil($small / 2);

	for($i=0; $i<$count; $i++)
	{
		$maxRight  = $col -1 -$i;//右边最大坐标
		$maxBottom = $row -1-$i;//下面最大坐标

		for($j=$i; $j<=$maxRight; $j++)          	 //构造上边一条线  纵坐标最小,横坐标递增
		{
			$result[] = $arr[$i][$j];
		}
		for($j=$i+1; $j<=$maxBottom; $j++)           //构造右边一条线 纵坐标递增,横坐标最大
		{
			$result[] = $arr[$j][$maxRight];
		}


		for($j=$maxRight-1;$j>=$i; $j--)             //构造下边一条线 纵坐标最大,横坐标递减
		{
			$result[] = $arr[$maxBottom][$j];
		}

		for($j=$maxBottom-1;$j>$i;$j--)              //构造左边一条线 纵坐标递减,横坐标最小
		{
			$result[] = $arr[$j][$i];
		}
	}

	return implode(",",$result);
}