标签: 数学
难度: Medium
标签: 数学
难度: Medium
运行时间: 25 ms
内存: 16.0 MB
class Solution: def orchestraLayout(self, N: int, x: int, y: int) -> int: L = min(x, N - 1 - x, y, N - 1 - y) ans = 4 * (N - L) * L x -= L y -= L N -= 2 * L if x == 0: ans += y + 1 elif y == N - 1: ans += N ans += x elif x== N - 1: ans += N + N - 1 ans += N - 1 - y else: ans += N + N - 1 + N - 1 ans += N - 1 - x return (ans - 1) % 9 + 1
该题解的整体思路是通过计算目标位置[Xpos, Ypos] (即 x, y) 相对于最外层螺旋的层级 L 来简化问题。首先,计算出目标位置所在的层级 L,该层级是到达 x 和 y 最近的边界的最小值。然后计算从外层到第 L 层之前所有层的元素总数。接着,考虑第 L 层的具体位置,根据 x 和 y 的相对位置在该层的不同部分(上、右、下、左)来计算具体的索引。最后,利用该索引值来确定乐器编号,因为编号是循环的,使用取模运算来实现。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution: def orchestraLayout(self, N: int, x: int, y: int) -> int: # 计算目标位置属于第几层 L = min(x, N - 1 - x, y, N - 1 - y) # 计算前L层总共包含的元素个数 ans = 4 * (N - L) * L # 计算目标位置在当前层的偏移量 x -= L y -= L # 当前层的大小 N -= 2 * L # 判断目标位置在当前层的哪一边,并计算相对于当前层起点的偏移 if x == 0: ans += y + 1 elif y == N - 1: ans += N ans += x elif x== N - 1: ans += N + N - 1 ans += N - 1 - y else: ans += N + N - 1 + N - 1 ans += N - 1 - x # 将总偏移量转换为乐器编号 return (ans - 1) % 9 + 1
在二维矩阵中,螺旋层级是从外围向内逐渐缩小的,每一层都对应矩阵的一个边框。对于任意位置[x, y],其所在的螺旋层级由其到最外层的距离决定。这里的`min(x, N - 1 - x, y, N - 1 - y)`计算的是[x, y]到最外层上下左右边界的最近距离。这个最小值决定了[x, y]最多是从外部数来的第几层,因此可以用来确定[x, y]所在的螺旋层级。
每一层的螺旋可以看作一个边长为`N - 2L`的正方形框架(L是层级,从0开始计数)。该框架的周长(不包括内部的下一层的边)是`4(N - 2L - 1) + 4 = 4(N - 2L) = 4(N - L) - 4L`。对于前L层,每增加一层,其边长减少2(向内缩小),因此第L层的周长就是`4(N - 2L)`。当我们将从0到L-1每一层的周长相加,实际上是在求一个等差数列的和,但我们只需要最外层到第L层之前的总和,所以公式是`4 * (N - L) * L`,这里`(N - L)`表示最外层边长减去层数L的结果,乘以L层每层的周长。
减去L的操作是为了将坐标[x, y]从原始的全局坐标转换为当前层级L的局部坐标。这样转换后,[x, y]表示的是在第L层的相对位置,而不是在整个矩阵的绝对位置。这一转换是必要的,因为它简化了在第L层内计算相对位置的过程,从而可以更简单地计算出从当前层的起始点到目标点的距离。局部坐标让我们可以直接使用边界从0开始的索引来计算偏移量,无需关心外层的具体大小和位置。