PHP 面试风车算法

作者:南丞 时间:2019-10-27 02:00

最近在面试的过程中遇到了一个挺有意思的 面试题, 让写一个 函数 效果如下:

foo(4); // 调用函数foo 传参数 效果如下:
/**
  7, 8, 9, 10
  6, 1, 2, 11
  5, 4, 3, 12
  16,15,14,13
*/

foo(5); //调用函数foo 传参数 效果如下:
/**
  13,14,15,16, 17
  12, 3, 4, 5, 18
  11, 2, 1, 6, 19
  10, 9, 8, 7, 20
  25, 24,23,22,21
*/
foo($n)

按照上面的结果,分析了下整了如下函数:

	/**
	 * @param $num
	 * @param int $direction 方向  1 为  顺时针旋转 2 为逆时针旋转
	 * @return mixed
	 */
	function foo($num, $direction = 1)
	{
		//填充map
		$data = new stdClass();
		$data->x = 1;
		if ($direction == 1) {
			$data->y = $num;
		} elseif ($direction == 2) {
			$data->y = 1;
		}
		$data->num = $num;
		$data->len = $num * $num;
		$data->tmp_data = [];
		$data->rate = 1;//方向
		$data->struct = create_struct($num);
		for ($i = $data->len; $i >= 1; $i--) {
			$data->i = $i;
			$key = change_key($data, $direction);
			$data->tmp_data[$key] = $i;
			unset($data->struct[$key]);
		}
		
		//根据y坐标分组
		$data->struct = create_struct($num);
		foreach ($data->tmp_data as $key => $value) {
			$data->struct[$key] = $value;
		}
		for ($i = 1; $i <= $data->num; $i++) {
			$start = ($i - 1) * $data->num;
			$end = $data->num;
			$slice = array_slice($data->struct, $start, $end);
			$data->slice[] = $slice;
		}
		
		return $data->slice;
	}
	
	function create_struct($num)
	{
		$struct = [];
		for ($i = 1; $i <= $num; $i++) {
			//嵌套
			for ($m = 1; $m <= $num; $m++) {
				$key = $m.','.$i;
				$struct[$key] = '';
			}
		}
		
		return $struct;
	}
	
	function change_key($data, $direction)
	{
		$key = $data->x.','.$data->y;
		if (isset($data->struct[$key])) {
			return $key;
		}
		switch ($data->rate) {
			// LEFT 方向
			case 1:
				$data->tmp_x = $data->x + 1;
				$key = $data->tmp_x.','.$data->y;
				if (isset($data->struct[$key])) {
					$data->x = $data->tmp_x;
					
					return $key;
				} else {
					if ($direction = 1) {
						$data->rate = 4;
					} elseif ($direction = 2) {
						$data->rate = 2;
					}
				}
				break;
			// DOWN 方向
			case 2:
				$data->tmp_y = $data->y + 1;
				$key = $data->x.','.$data->tmp_y;
				if (isset($data->struct[$key])) {
					$data->y = $data->tmp_y;
					
					return $key;
				} else {
					if ($direction = 1) {
						$data->rate = 1;
					} elseif ($direction = 2) {
						$data->rate = 3;
					}
				}
				break;
			// RIGHT 方向
			case 3:
				$data->tmp_x = $data->x - 1;
				$key = $data->tmp_x.','.$data->y;
				if (isset($data->struct[$key])) {
					$data->x = $data->tmp_x;
					
					return $key;
				} else {
					if ($direction = 1) {
						$data->rate = 2;
					} elseif ($direction = 2) {
						$data->rate = 4;
					}
				}
				break;
			// UP 方向
			case 4:
				$data->tmp_y = $data->y - 1;
				$key = $data->x.','.$data->tmp_y;
				if (isset($data->struct[$key])) {
					$data->y = $data->tmp_y;
					
					return $key;
				} else {
					if ($direction = 1) {
						$data->rate = 3;
					} elseif ($direction = 2) {
						$data->rate = 1;
					}
				}
				break;
		}
		
		return change_key($data, $direction);
	}

其中原理是把效果按照 坐标的形式去处理,比如:

foo(4)       按照坐标化处理就是:

  7, 8, 9, 10            1,1  2,1  3,1  4,1
  6, 1, 2, 11            1,2  2,2  3,2  4,2
  5, 4, 3, 12            1,3  2,3  3,3  4,3
  16,15,14,13            1,4  2,4  3,4  4,4

然后我们通过 create_struct() 函数去组合一下 坐标:

array (size=16)
  '1,1' => string '' (length=0)
  '2,1' => string '' (length=0)
  '3,1' => string '' (length=0)
  '4,1' => string '' (length=0)
  '1,2' => string '' (length=0)
  '2,2' => string '' (length=0)
  '3,2' => string '' (length=0)
  '4,2' => string '' (length=0)
  '1,3' => string '' (length=0)
  '2,3' => string '' (length=0)
  '3,3' => string '' (length=0)
  '4,3' => string '' (length=0)
  '1,4' => string '' (length=0)
  '2,4' => string '' (length=0)
  '3,4' => string '' (length=0)
  '4,4' => string '' (length=0)

从算法结果要求对比我们会发现旋转的最后一个值我们是知道的:

/**
  7, 8, 9, 10
  6, 1, 2, 11
  5, 4, 3, 12
  16,15,14,13
*/
// 最后一个值是 16  foo(4)
/**
  13,14,15,16, 17
  12, 3, 4, 5, 18
  11, 2, 1, 6, 19
  10, 9, 8, 7, 20
  25, 24,23,22,21
*/
// 最后一个值是 25  foo(5)

也就是最后一个值 是 $num*$num 最后一个值的坐标是 (1,$num)

接下来我们遍历坐标倒着把外圈的先整出来,代码如下:

$data = new stdClass(); //PHP内置类 用来返回特定的数据结构
$data->x = 1;
if ($direction == 1) {
     $data->y = $num;
} elseif ($direction == 2) {
     $data->y = 1;
}
$data->num = $num;
$data->len = $num * $num;
$data->tmp_data = [];
$data->rate = 1;//方向
$data->struct = create_struct($num);
for ($i = $data->len; $i >= 1; $i--) {
      $data->i = $i;
}
var_dump($data);

运行这段代码如下:

object(stdClass)[1]
  public 'x' => int 1        
  public 'y' => int 4
  public 'num' => int 4
  public 'len' => int 16
  public 'tmp_data' =>
    array (size=0)
      empty
  public 'rate' => int 1
  public 'struct' =>
    array (size=16)
      '1,1' => string '' (length=0)
      '2,1' => string '' (length=0)
      '3,1' => string '' (length=0)
      '4,1' => string '' (length=0)
      '1,2' => string '' (length=0)
      '2,2' => string '' (length=0)
      '3,2' => string '' (length=0)
      '4,2' => string '' (length=0)
      '1,3' => string '' (length=0)
      '2,3' => string '' (length=0)
      '3,3' => string '' (length=0)
      '4,3' => string '' (length=0)
      '1,4' => string '' (length=0)
      '2,4' => string '' (length=0)
      '3,4' => string '' (length=0)
      '4,4' => string '' (length=0)
  public 'i' => int 1

得到一个对象有开始 坐标 有 最后一个 点的值 然后我们开始用 change_key() 函数迭代,先给 1,4 坐标分配一个 16 代码如下:

$key = change_key($data, $direction);
$data->tmp_data[$key] = $i;
unset($data->struct[$key]);

然后在 change_key() 递归调用 填充 , 依次 向右走->向上->向左-> 向下 这样 得到数据如下:

object(stdClass)[1]
  public 'x' => int 2
  public 'y' => int 2
  public 'num' => int 4
  public 'len' => int 16
  public 'tmp_data' =>
    array (size=16)
      '1,4' => int 16
      '2,4' => int 15
      '3,4' => int 14
      '4,4' => int 13
      '4,3' => int 12
      '4,2' => int 11
      '4,1' => int 10
      '3,1' => int 9
      '2,1' => int 8
      '1,1' => int 7
      '1,2' => int 6
      '1,3' => int 5
      '2,3' => int 4
      '3,3' => int 3
      '3,2' => int 2
      '2,2' => int 1
  public 'rate' => int 3
  public 'struct' =>
    array (size=0)
      empty
  public 'i' => int 1
  public 'tmp_x' => int 2
  public 'tmp_y' => int 1

接下来一行一行的排列了代码如下:

$data->struct = create_struct($num);
foreach ($data->tmp_data as $key => $value) {
    $data->struct[$key] = $value;
}

结果如下:

object(stdClass)[1]
  public 'x' => int 2
  public 'y' => int 2
  public 'num' => int 4
  public 'len' => int 16
  public 'tmp_data' =>
    array (size=16)
      '1,4' => int 16
      '2,4' => int 15
      '3,4' => int 14
      '4,4' => int 13
      '4,3' => int 12
      '4,2' => int 11
      '4,1' => int 10
      '3,1' => int 9
      '2,1' => int 8
      '1,1' => int 7
      '1,2' => int 6
      '1,3' => int 5
      '2,3' => int 4
      '3,3' => int 3
      '3,2' => int 2
      '2,2' => int 1
  public 'rate' => int 3
  public 'struct' =>
    array (size=16)
      '1,1' => int 7
      '2,1' => int 8
      '3,1' => int 9
      '4,1' => int 10
      '1,2' => int 6
      '2,2' => int 1
      '3,2' => int 2
      '4,2' => int 11
      '1,3' => int 5
      '2,3' => int 4
      '3,3' => int 3
      '4,3' => int 12
      '1,4' => int 16
      '2,4' => int 15
      '3,4' => int 14
      '4,4' => int 13
  public 'i' => int 1
  public 'tmp_x' => int 2
  public 'tmp_y' => int 1

最后 把 $data->struct 属性 按照 $num 进行分组就 ok了.

评论:

回到顶部
回到顶部