Spiral Matrix LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google Intuit microsoft Kahin Paytm VMware ZillowBaxılıb 97

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 problemi deyir Spiral Matrixdə biz matrisin bütün elementlərini saat əqrəbi istiqamətində spiral formada çap etmək istəyirik.

Spiral Matrix LeetCode HəlliPin

Spiral Matrix LeetCode Həlli

 

Spiral matris üçün yanaşma:

Fikir

Problemi matrisi döngələrə bölmək və hər bir döngədə bütün elementləri bir-bir çap etməklə həyata keçirmək olar.

Müşahidə etmək olar ki, xarici döngənin elementləri əvvəlcə saat əqrəbi istiqamətində çap olunur, sonra daxili elementlər çap olunacaq. Hər bir hərəkətdə dörd döngəmiz var, əvvəlcə for loop iterasiyası soldan sağa hərəkəti, sonra ikinci for loop iterasiyası yuxarıdan aşağıya doğru hərəkəti təmsil edir, halbuki üçüncü döngə iterasiyası sağdan sola hərəkəti, dördüncü döngə isə yuxarıdan aşağıya doğru hərəkəti təmsil edir. aşağıdan yuxarıya. Eyni şəkildə, biz də daxili hərəkətlər üçün hərəkət edirik.

Alqoritm

  • rowstart, rowend, colstart və colend kimi dəyişənləri yaradın və işə salın.
  • rowstart və colstart müvafiq olaraq sıfıra başlayan sətir və sütunun ilkin mövqeyini təmsil edir.
  • rowend və coend müvafiq olaraq sətir və sütunun ölçüsünü təmsil edir.
  • Hamısı bitənə qədər xarici while döngəsini işə salın elementləri çap olunacaq və elementlər saat əqrəbi istiqamətində və spiral şəklində çap olunacaq.
  • Xarici döngənin hər iterasiyasında biz soldan sağa keçən dörd daxili döngəni keçirik, sonra yuxarıdan aşağıya sonuncu sütunu, sonra sağdan sola və sonuncu daxili döngəni aşağıdan yuxarıya doğru keçirik.

Kodu 

Spiral Matrix LeetCode Həlli üçün C++ Proqramı

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
       int m=matrix.size();
         vector<int>res;
          if(m==0)
          return res;
        int n=matrix[0].size();
        
        int rowstart=0;
        int rowend=m;
        int colstart=0;
        int colend=n;
        
        int k;
        
        while(rowstart<rowend && colstart<colend)
        {
          
            for(k=colstart;k<colend;k++)
            res.push_back(matrix[rowstart][k]);
            rowstart+=1;
            
            for(k=rowstart;k<rowend;k++)
            res.push_back(matrix[k][colend-1]);
            colend-=1;
            
            if(rowstart<rowend)
            {
                for(k=colend-1;k>=colstart;k--)
                res.push_back(matrix[rowend-1][k]);
                rowend-=1;
            }
            
            if(colstart<colend)
            {
                for(k=rowend-1;k>=rowstart;k--)
                res.push_back(matrix[k][colstart]);
                colstart+=1;
            }
            
        }
        return res;       
    }
};

 

Spiral Matrix LeetCode Həlli üçün Java Proqramı

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) 
    {
       int m=matrix.length;
          List<Integer>res=new ArrayList<>();
          if(m==0)
          return res;
        int n=matrix[0].length;
        
        int rowstart=0;
        int rowend=m;
        int colstart=0;
        int colend=n;
        
        int k;
        
        while(rowstart<rowend && colstart<colend)
        {
          
            for(k=colstart;k<colend;k++)
            res.add(matrix[rowstart][k]);
            rowstart+=1;
            
            for(k=rowstart;k<rowend;k++)
            res.add(matrix[k][colend-1]);
            colend-=1;
            
            if(rowstart<rowend)
            {
                for(k=colend-1;k>=colstart;k--)
                res.add(matrix[rowend-1][k]);
                rowend-=1;
            }
            
            if(colstart<colend)
            {
                for(k=rowend-1;k>=rowstart;k--)
                res.add(matrix[k][colstart]);
                colstart+=1;
            }
            
        }
        return res;   
    }
}

 

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

Zamanın mürəkkəbliyi

Spiral matrisin zaman mürəkkəbliyi: O(m*n), m və n isə müvafiq olaraq sıra və sütunun ölçüsünü təmsil edir.

Spiral Matrisin Kosmik Mürəkkəbliyi: O(1) heç bir əlavə boşluq istifadə edilmir.

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

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