面试中遇到的一个蛇形算法题

2017-02-16 00:24:58 admin ...

参加面试第一次遇到当场写算法题的,顺时针打印矩阵的坐标,如图所示

顺序为,0,1,2,3,4,9,14,19,24,23,22,21,20,15,10,5,6,7,8,13,18,17,16,11,12

假设 0的坐标为(0,0),1的坐标为(0,1),5的坐标为(1,0)其他以此类推。

题目是打印出来顺序的坐标。

总体思路采用一个大循环控制,循环条件当前的最大纵坐标不小于最小纵坐标,并且当前小横坐标不小于最大横坐标时,循环终止,然后再按照上右下左的顺序分四个小循环遍历。

第一步:实现等高等宽的矩阵(x=y)的坐标遍历。
第二步:采用记录标志的方式改进,实现x!=y或x=y矩阵的遍历。 第二步:采用记录标志的方式改进,实现x!=y或x=y矩阵的遍历。

第一步代码实现:

/**
 * [printXY 顺时针遍历等高等宽矩阵坐标]
 * @param  integer $n [矩阵宽高]
 * @return string     [坐标字符串]
 */
function printXY($n=1) 
{
    if($n<=1) return '(0,0)';

    $minTopX    = 0;    //当前最小横坐标
    $maxRightY  = $n-1; //当前最大纵坐标
    $maxBottomX = $n-1; //当前最大横坐标
    $minLeftY   = 0;    //当前最小纵坐标

    $sortXY = ''; //定义一个空字符串,用于接收坐标

    //当当前的最大纵坐标不小于最小纵坐标,并且当前小横坐标不小于最大横坐标时,循环终止
    while ($minLeftY <= $maxRightY && $minTopX 右->下->左
        // 当前上面一行
        for($j = $minLeftY; $j <= $maxRightY; $j++) {
            $sortXY .= '('.$minTopX.','.$j.') ';
        }
        $minTopX++;

        // 当前右边一行
        for($i = $minTopX; $i = $minLeftY; $j--) {
            $sortXY .=  '('.$maxBottomX.','.$j.') ';
        }
        $maxBottomX--;

        // 当前左边一行
        for($i = $maxBottomX; $i >= $minTopX; $i--) {
            $sortXY .= '('.$i.','.$minLeftY.') ';
        }
        $minLeftY++;
    }
    return $sortXY;
}

第二步的实现代码:

/**
 * [printXY2 顺时针遍历矩阵坐标]
 * @param  integer $x [矩阵宽度]
 * @param  integer $y [矩阵高度]
 * @return string     [坐标字符串]
 */
function printXY2($x=1,$y=1) 
{
    if($x<=1 && $y<=1) return '(0,0)';

    $minTopX    = 0;    //最小横坐标
    $maxRightY  = $y-1; //最大纵坐标
    $maxBottomX = $x-1; //最大横坐标
    $minLeftY   = 0;    //最小纵坐标

    $sortXY = ''; //定义一个空字符串,用于接收坐标
    $sortXYFlagArr[0][0] = false; //定义一个二维数组,记录是否被使用过。

    //当当前的最大纵坐标不小于最小纵坐标,并且当前小横坐标不小于最大横坐标时,循环终止
    while ($minLeftY <= $maxRightY && $minTopX 右->下->左

        // 当前上面一行
        for($j = $minLeftY; $j <= $maxRightY; $j++) {
            if(!isset($sortXYFlagArr[$minTopX][$j])){
                $sortXY .= '('.$minTopX.','.$j.') ';
                $sortXYFlagArr[$minTopX][$j] = true;
            }
        }
        $minTopX++;

        // 当前右边一行
        for($i = $minTopX; $i = $minLeftY; $j--) {
            if(!isset($sortXYFlagArr[$maxBottomX][$j])){
                $sortXY .=  '('.$maxBottomX.','.$j.') ';
                $sortXYFlagArr[$maxBottomX][$j] = true;
            }
        }
        $maxBottomX--;

        // 当前左边一行
        for($i = $maxBottomX; $i >= $minTopX; $i--) {

            if(!isset($sortXYFlagArr[$i][$minLeftY])){
                $sortXY .= '('.$i.','.$minLeftY.') ';
                $sortXYFlagArr[$i][$minLeftY] = true;
            }
        }
        $minLeftY++;
    }
    return $sortXY;
}

请大家指正。

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。