欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

几个面试算法

程序员文章站 2024-03-17 23:10:22
...

几个面试算法

 

 

#!/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);
}