记一道数字旋转排列算法题
记一道数字旋转排列算法题
面试的时候遇到一道算法题，当时没做出来，也没有什么思路。睡觉前突然想到解法，记录一下。
题的大意如下，数字以1开始，并围绕1做逆时针旋转，其中1的坐标为(0, 0)，如下图所示：
要求给一个坐标，求其未知的数是多少？例：给出(1, 0)，该坐标的数为2；给出(-1, -2)，该坐标上的数为22。
你可以先思考一下，或者写写试试。点开查看答案
说下解题思路，由点的坐标可以得出目标值所在的圈数p，比如5在第2圈，p的大小为坐标x或y较大绝对值n再+1，比如18为(-2,1)，绝对值n为2，则18在第3圈(n+1)，然后从(n, -n)顺时针穷举该圈的数即可。
代码实现：
public int getTheNumber(int x, int y) {
if (x == 0 && y == 0) {
return 1;
}
int n = Math.max(Math.abs(x), Math.abs(y));
int p = n + 1;//圈数
int max = (2 * p - 1) * (2 * p - 1);//所在圈的最大值
int x1 = n;
int y1 = -n;
int res = max;
while (x1 != x || y1 != y) {//从最大值开始顺时针依次递减，直到找到坐标的数
res--;
if (x1 > -n && y1 == -n) {
x1--;
continue;
}
if (x1 == -n && y1 < n) {
y1++;
continue;
}
if (x1 < n && y1 == n) {
x1++;
continue;
}
if (x1 == n && y1 > -n) {
y1--;
}
}
return res;
}突然又想到如果问题是给一个数，求它的坐标呢？
思路也是一样的，先求出这个数所在的区间，也就是第几圈，然后穷举233333感觉有点蠢啊不过没其他思路了
