一个面试题

今天朋友过来问了我一个问题,他面试过程中碰到的,题目具体我也不知道,需要实现的效果如下:

1

2

3

4

5

16

17

18

19

6

15

24

25

20

7

14

23

22

21

8

13

12

11

10

9

这个题应该就是让递增数字实现螺旋型排列(具体我也不好描述),大致思考了下,出来一个思路:

创建一个递增数的循环,从1到x*y(即最大值),每当达到一行的尾部就拐弯,到达最大值时结束循环,这个过程中每次循环都填充一个数字到相应的坐标。

这个思路有两个要点:

  1. 前进方向

  2. 拐角检测

前进方向我分为4个部分,即右、下、左、上,分别用:1、2、3、4代替

拐角检测需要主要两点:1、当后一个坐标已经被填充时拐弯或者超出高或者宽时拐弯

下面是具体实现的代码:

// 输入宽和高
$x = 5;
$y = 5;
// 初始化当前的坐标和当前方向
$direction = 1;
$xp = 0;
$yp = 0;
// 初始化当前数字和最大数字
$id = 1;
$max = $x * $y;
// 初始化数组
$array = array();
while (true) {
    if ($id > $max) {
        break;
    }
    // 填充数字
    $array[$xp][$yp] = $id;
    $id ++;
    // 判断是否越界,如果越界则拐弯
    switch ($direction) {
        case 1:
            $yp ++;
            if (isset($array[$xp][$yp]) || $yp >= $y) {
                $direction = 2;
                $yp --;
                $xp ++;
            }
            break;
        case 2:
            $xp ++;
            if (isset($array[$xp][$yp]) || $xp >= $x) {
                $direction = 3;
                $xp --;
                $yp --;
            }
            break;
        case 3:
            $yp --;
            if (isset($array[$xp][$yp]) || $yp < 0) {
                $direction = 4;
                $yp ++;
                $xp --;
            }
            break;
        case 4:
            $xp --;
            if (isset($array[$xp][$yp]) || $xp < 0) {
                $direction = 1;
                $xp ++;
                $yp ++;
            }
            break;
    }
}
// 显示
echo "<table>";
for ($i=0;$i<$x;$i++) {
    echo "<tr>";
    for ($k=0;$k<$y;$k++) {
        echo "<td>{$array[$i][$k]}</td>";
    }
    echo "</tr>";
}
echo "</table>";

$x和$y的值可以随意修改,比如我们修改为:$x = 10; $y = 5;则显示效果如下:

1

2

3

4

5

26

27

28

29

6

25

44

45

30

7

24

43

46

31

8

23

42

47

32

9

22

41

48

33

10

21

40

49

34

11

20

39

50

35

12

19

38

37

36

13

18

17

16

15

14

Published: July 29 2011

blog comments powered by Disqus