PHP面试必备 - 风车算法详解

php
, ,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

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

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/**
 * @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);
}

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

1
2
3
4
5
6
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() 函数��组一下 坐标:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
  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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$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);

运行这段代码如下:

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
26
27
28
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 代码如下:

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

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

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
26
27
28
29
30
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

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

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

结果如下:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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了.

版权声明

  • 本文作者: PFinal南丞
  • 本文链接:
  • 版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！

相关阅读