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.
Mündəricat
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 = 4
Çı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:
- ardıcıllığı necə yaratmaq olar 1,1,2,2,3,3,4,4,5,5
- sağa necə dönmək olar?
- 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ınstep
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
