Spiral Matrix II Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Accenture Amazon alma Facebook google microsoft Kahin Über
meta tiktokBaxılıb 76

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

Bu sual Spiral matris II çox bənzəyir  Spiral matris 

Zəhmət olmasa, bu problemi həll etməzdən əvvəl daha yaxşı fikir əldə etmək üçün yuxarıdakı sualı sınamağa çalışın.

Bu sualda bizdən spiral qaydada elementləri olan n*n ölçülü matris yaratmaq tələb olunur və giriş kimi yalnız n verilir.

Spiral Matrix II Leetcode HəlliPin

Alqoritm

Aydın şəkildə müşahidə etsək, görə bilərik ki, n nə olursa olsun, spiral üçün istiqamətlərin sırası həmişə olacaq.

şərq->cənub->qərb->şimal->şərq->… və s.

Beləliklə, biz 4 göstəricidən istifadə edə və spiral istiqamətə uyğun olaraq boş/əvvəlcədən təyin edilmiş 2D vektoru keçə və nömrə saxlaya və rəqəmi 1 artıra bilərik.

4 göstəricidən istifadə edin – sol üçün l, sağ üçün r, yuxarı üçün t və aşağı üçün d;

İşlər:

  1. istiqamət şərqdir:
    1. yuxarı cərgədə soldan sağa bütün sütunları keçin
    2. hər dəfə ədədi saxlayın və ədədi artırın
    3. yuxarı 1 artır
    4. istiqamətini cənuba dəyişdirin
  2. istiqamət cənubdur
    1. bütün sətirləri yuxarıdan aşağıya, ən sağdakı sütunda keçin
    2. hər dəfə ədədi saxlayın və ədədi artırın
    3. sağa 1 azaldın
    4. istiqamətini qərbə dəyişdirin
  3. istiqamət qərbdir
    1. aşağı cərgədə sağdan sola bütün sütunları keçin
    2. hər dəfə ədədi saxlayın və ədədi artırın
    3. 1 azaldı
    4. istiqamətini qərbə dəyişdirin
  4. istiqamət şimaldır
    1. bütün cərgələri aşağıdan yuxarıya, ən sol sütunda keçin
    2. hər dəfə ədədi saxlayın və ədədi artırın
    3. 1 sol artım
    4. istiqamətini qərbə dəyişdirin

biz bunu bir müddət döngəsində sola <= sağa və yuxarı <= aşağıya qədər təkrarlaya bilərik

Aşağıdakı şəkil alqoritmi təsvir edir

Spiral Matrix II Leetcode HəlliPin

 

Kodu

Qeyd: Göstəricilər – sol üçün l, sağ üçün r, yuxarı üçün t, aşağı üçün d

Spiral Matrix II Leetcode Solution üçün C++ proqramı

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        char dir = 'E';
        vector<vector<int>> spiralMatrix(n, vector<int>(n,0));
        int num=1;
        int l=0, t=0, r=n-1, d=n-1;
        while(l<=r && t<=d) {
            if(dir == 'E') {
                for(int i=l; i<=r; i++) {
                    spiralMatrix[t][i] = num++;
                }
                t++;
                dir='S';
            }
            else if(dir=='S') {
                for(int i=t; i<=d; i++) {
                    spiralMatrix[i][r] = num++;
                }
                r--;
                dir='W';
            }
            else if(dir=='W') {
                for(int i=r; i>=l; i--) {
                    spiralMatrix[d][i] = num++;
                }
                d--;
                dir='N';
            }
            else {
                for(int i=d; i>=t; i--) {
                    spiralMatrix[i][l] = num++;
                }
                l++;
                dir='E';
            }
        }
        return spiralMatrix;
    }
};

Spiral Matrix II Leetcode Solution üçün Java proqramı

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] spiralMatrix = new int[n][n];
        int num=1;
        char dir='E';
        int l=0, t=0, r=n-1, d=n-1;
        while(l<=r && t<=d) {
            if(dir == 'E') {
                for(int i=l; i<=r; i++) {
                    spiralMatrix[t][i] = num++;
                }
                t++;
                dir='S';
            }
            else if(dir=='S') {
                for(int i=t; i<=d; i++) {
                    spiralMatrix[i][r] = num++;
                }
                r--;
                dir='W';
            }
            else if(dir=='W') {
                for(int i=r; i>=l; i--) {
                    spiralMatrix[d][i] = num++;
                }
                d--;
                dir='N';
            }
            else {
                for(int i=d; i>=t; i--) {
                    spiralMatrix[i][l] = num++;
                }
                l++;
                dir='E';
            }
        }
        return spiralMatrix;
    }
}

Spiral Matrix II Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi:

Burada n giriş verilir və biz spiral formada n*n matrisi üzərində təkrar edirik. Beləliklə, O (n ^ 2)

Kosmik Mürəkkəblik:

Biz istifadə etdik daimi əlavə yer num saxlamaq üçün, deməli O (1)

Referans: https://en.wikipedia.org/wiki/Spiral

 

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