Spiral Matrix III LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Facebook TeslaBaxılıb 68

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Spiral matris III LeetCode Həlli – Siz hüceyrədən başlayırsınız (rStart, cStart) bir rows x cols şərqə baxan şəbəkə. Şimal-qərb küncü şəbəkənin birinci cərgəsində və sütununda, cənub-şərq küncü isə sonuncu cərgədə və sütundadır.

Bu şəbəkədəki hər mövqeyə baş çəkmək üçün saat əqrəbi istiqamətində spiral şəklində gəzəcəksiniz. Siz şəbəkənin hüdudlarından kənara çıxdığınız zaman, biz şəbəkədən kənarda gəzməyə davam edirik (lakin daha sonra şəbəkə sərhədinə qayıda bilərik.). Nəhayət, hamıya çatırıq rows * cols şəbəkənin boşluqları.

Qayıtmaq torun mövqelərini ziyarət etdiyiniz ardıcıllıqla təmsil edən koordinatlar massivi.

Misal:

Input:

sıra = 5,

cols = 6,

rStart = 1,

cStart = 4Spiral Matrix III LeetCode Həlli

Çıxış: 

[[1,4], [1,5], [2,5], [2,4], [2,3], [1,3], [0,3], [0,4], [ 0,5], [3,5], [3,4], [3,3], [3,2], [2,2], [1,2], [0,2], [4,5, 4,4], [4,3], [4,2], [4,1], [3,1], [2,1], [1,1], [0,1], [4,0] , [3,0], [2,0], [1,0], [0,0], [XNUMX]]

Spiral Matrix III LeetCode Həlli üçün izahat:

Intuisiya:

Bir-bir addım atın.
Məkan şəbəkənin içərisindədirsə, onu əlavə edin res.
Bəs yolu necə simulyasiya etmək olar?

Bu bezdirici görünür, amma yolu müşahidə etsək:

sağa hərəkət et 1 addım, sağa dön
aşağı hərəkət 1 addım, sağa dön
sola keçin 2 addımlar, sağa dönün
yuxarı hərəkət edin 2 addımlar, sağa dön,
sağa hərəkət et 3 addımlar, sağa dönün
aşağı hərəkət 3 addımlar, sağa dönün
sola keçin 4 addımlar, sağa dönün
yuxarı hərəkət edin 4 addımlar, sağa dön,

addımların ardıcıllığını tapa bilərik: 1,1,2,2,3,3,4,4,5,5....

Beləliklə, anlamaq üçün iki şey var:

  1. ardıcıllığı necə yaratmaq olar 1,1,2,2,3,3,4,4,5,5
  2. sağa necə dönmək olar?Spiral Matrix III LeetCode HəlliPin
  • addım uzunluğu ilə başlayır 1, bir dəfə sağa hərəkət edin, sonra dönün; bir dəfə aşağıya keçin
  • Addım uzunluğunu artırın, 1 + 1 = 2, sola 2 dəfə hərəkət edin, sonra dönün; yuxarıya 2 dəfə hərəkət edin
  • Beləliklə, hər bir addım uzunluğu üçün hərəkət edəcəyik step 2 istiqamət üçün, sonra artırın step bir tərəfindən; və təkrarlayın
  • Ümumiləşdirmək üçün:
    • Step == 1, move*step, turn, move*step, turn
    • Step += 1, move*step, turn, move*step, turn
    • Step += 1, move*step, turn, move*step, turn
    • ... ... repeat

Spiral Matrix III LeetCode Həlli üçün kod

Java Proqramı

class Solution {
    public int[][] spiralMatrixIII(int R, int C, int x, int y) {
        int[][] res = new int[R * C][2];
        int dx = 0, dy = 1, n = 0, tmp;
        for (int j = 0; j < R * C; ++n) {
            for (int i = 0; i < n / 2 + 1; ++i) {
                if (0 <= x && x < R && 0 <= y && y < C)
                    res[j++] = new int[] {x, y};
                x += dx;
                y += dy;
            }
            tmp = dx;
            dx = dy;
            dy = -tmp;
        }
        return res;
    }
}

C ++ Proqramı

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r, int c) {
        vector<vector<int>> res = {{r, c}};
        int dx = 0, dy = 1, tmp;
        for (int n = 0; res.size() < R * C; n++) {
            for (int i = 0; i < n / 2 + 1; i++) {
                r += dx, c += dy;
                if (0 <= r && r < R && 0 <= c && c < C)
                    res.push_back({r, c});
            }
            tmp = dx, dx = dy, dy = -tmp;
        }
        return res;
    }
};

Python proqramı

class Solution(object):
    def spiralMatrixIII(self, R, C, x, y):
        res = []
        dx, dy, n = 0, 1, 0
        while len(res) < R * C:
            for i in xrange(n / 2 + 1):
                if 0 <= x < R and 0 <= y < C:
                    res.append([x, y])
                x, y = x + dx, y + dy
            dx, dy, n = dy, -dx, n + 1
        return res

Spiral Matrix III LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O(max(R,C)^2)
Kosmik mürəkkəblik: O(R*C) çıxış üçün

Crack Sistemi Dizayn Müsahibələri
Translate »