刚花了好长时间做了一个算法题,代码没多少,想了很久怎么做.
过程比较累心(调试验证错误,调试验证错误…),
最后分步骤完成了,但是没想到其他的解法…
算法基础还是比较差.
题目大概是这样的:
求平面坐标中(0,0)开始螺旋形移动到某点的距离 一个平面坐标,从0开始向(0,1)出发,每一步移动一个距离,成螺旋形移动, 例如:
(0,0) (0,1) (1,1) (1,0) (1,-1) (0,-1)….
具体线路参考下图. 问题是,给定一个坐标(x,y),求到这个点需要移动的距离. 复杂度要求O(1);
说说思路:
- 先根据给定的坐标找到一个参照点,例如(3,3),那参照点就是3,
- 然后画一个矩阵,求这个矩阵的面积就可以计算出到这个点需要移动的次数.
- 然后计算给定的坐标和参照点的距离,按照适当的处理这个距离就能得到移动到该坐标的距离
具体代码实现(php):
<?php
$x = 2;
$y = 1;
function solution($x, $y) {
if ($x + $y <= 0) {
$basic_point = abs(min($x, $y)) + 1;
} else {
$basic_point = abs(max($x, $y));
}
$margin = 2 * $basic_point - 1;
$all_step = $margin * 2 * $basic_point;
if ($y == $basic_point && $x != -($basic_point - 1)) {
//up margin
$tmp_step = $basic_point - $x;
} elseif ($x == -($basic_point - 1) && $y != -($basic_point - 1)) {
//left margin
$tmp_step = $basic_point - $y + $margin;
} elseif ($y == -($basic_point - 1) && $x != $basic_point) {
//down margin
$tmp_step = $basic_point - 1 + $x + 2 * $margin;
} else {
//right margin
$tmp_step = $basic_point - $y;
$tmp_step *= -1;
}
return $all_step - $tmp_step;
}
echo solution($x, $y);
感觉实现的还是有点复杂,计算参照点花了不少时间…
不确定是否一定正确,这个实现的比较另类,
感觉应该有更好的实现方式.有时间再来想想.