LeetCode LCP 29. 樂團站位（數學 等引數列）

1. 題目

某樂團的演出場地可視作 num * num 的二維矩陣 grid（左上角坐標為 [0,0])，每個位置站有一位成員，
樂團共有 9 種樂器，樂器編號為 1~9，每位成員持有 1 個樂器，

為保證聲樂混合效果，成員站位規則為：自 grid 左上角開始順時針螺旋形向內回圈以 1，2，…，9 回圈重復排列，
例如當 num = 5 時，站位如圖所示

請回傳位于場地坐標 [Xpos,Ypos] 的成員所持樂器編號，

示例 1：
輸入：num = 3, Xpos = 0, Ypos = 2
輸出：3

解釋：

示例 2：
輸入：num = 4, Xpos = 1, Ypos = 2
輸出：5

解釋：

提示：
1 <= num <= 10^9
0 <= Xpos, Ypos < num

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/SNJvJP
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

2. 解題

從 (0, -1) 出發，發現 每個邊走到盡頭的步數規律 n, n-1, n-1, n-2, n-2 …

2.1 模擬超時

class Solution {
public:
    int orchestraLayout(int num, int xPos, int yPos) {
        long long tot = 1LL*num*num, ct = 0;
        long long x0 = 0, y0 = 0, x1 = 0 , y1 = -1, delta = num, i = 0;
        long long d, idx;
        while(ct < tot)
        {
            if(i%2 == 1)
                delta--;//奇數的時候，步長減少 1
            ct += delta; // 總的格數
            if(i%4==0) // 四個方向挪動的坐標
            {
                y1 += delta;
            }
            else if(i%4 == 1)
            {
                x1 += delta;
            }
            else if(i%4 == 2)
            {
                y1 -= delta;
            }
            else
            {
                x1 -= delta;
            }
            if(x0 == xPos && x1 == xPos && 
                ((yPos >= y0 && yPos <= y1) || (yPos >= y1 && yPos <= y0)))
            {	// 如果在前后端點之間，則找到位置
                d = abs(y1-yPos); // 計算偏差
                idx = ct-d; // 減去偏差格數
                break;
            }
            else if(y0 == yPos && y1 == yPos && 
                ((xPos >= x0 && xPos <= x1) || (xPos >= x1 && xPos <= x0)))
            {
                d = abs(x1-xPos);
                idx = ct-d;
                break;
            }
            x0 = x1;
            y0 = y1;
            i++;
        }
        return (idx%9==0) ? 9 : (idx%9);  // 回傳序號
    }
};

2.2 優化通過

• 先找出這個坐標處在第幾層
• 等引數列求和，所有外層的格子數目
• 再利用上面的代碼，遍歷所在的一圈就可以找出答案

class Solution {
public:
    int orchestraLayout(int num, int x, int y) {
        int a = num-x, b = num-y;
        int layer = min(x+1,min(a, min(y+1, b)));//所在的圈
        layer--;// 外面有多少個完整的圈
        long long  ct = 4LL*layer*(num-layer), idx;
        // 每圈的邊長 為 n, 則 格子數 為 4(n-1)
        // 第 layer 圈 的邊長 n-2(layer-1)
        // 外部完全圈的格子總數：layer*4(n-1+n-2(layer-1)-1)/2
        // = 2*layer*(2n-1-2layer+2-1) = 4*layer(n-layer)
        int delta = num - 2*layer, i = 0;
        // (x,y)點 所在圈的 邊長 delta 
        int x0 = layer,y0 = layer-1, x1 = layer, y1 = layer-1, d;
        // 起點坐標 x1, y1
        while(i < 4) { // 遍歷 目標點所在的圈
            if(i%2 == 1)
                delta--;
            ct += delta;
            if(i%4==0)
            {
                y1 += delta;
            }
            else if(i%4 == 1)
            {
                x1 += delta;
            }
            else if(i%4 == 2)
            {
                y1 -= delta;
            }
            else
            {
                x1 -= delta;
            }
            if(x0 == x && x1 == x && 
                ((y >= y0 && y <= y1) || (y >= y1 && y <= y0)))
            {
                d = abs(y1-y);
                idx = ct-d;
                break;
            }
            else if(y0 == y && y1 == y && 
                ((x >= x0 && x <= x1) || (x >= x1 && x <= x0)))
            {
                d = abs(x1-x);
                idx = ct-d;
                break;
            }
            x0 = x1;
            y0 = y1;
            i++;
        }
        return (idx%9==0) ? 9 : (idx%9);
    }
};

0 ms 5.7 MB C++

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！