Diaqonal Traversal LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Qapılar Facebook google microsoft Robinlik Viza
Goldmann SachsBaxılıb 81

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

Diaqonal Traversal LeetCode Həlli – 2D tam ədəd massivi verilmişdir nums, qayıt bütün elementləri nums aşağıdakı şəkillərdə göstərildiyi kimi diaqonal qaydada.

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Diaqonal Traversal LeetCode HəlliPin

Diaqonal Traversal LeetCode Həlli üçün izahat

Əsas İdeya

Bu problemin birinci cərgəsi və sonuncu sütunu müvafiq diaqonal üçün başlanğıc nöqtəsi kimi xidmət edəcəkdir. Diaqonal daxilində bir element verilmişdir, deyək [i, j], biz bir cərgə yuxarı və bir sütun irəli getməklə diaqonalla yuxarı qalxa bilərik, yəni [i – 1, j + 1] və ya, bir sıra aşağı və bir sütun sola getməklə diaqonaldan aşağı enə bilərik, yəni [i + 1, j – 1]Qeyd ki, bu gedən diaqonallara aiddir right to left yalnız. Soldan sağa gedənlər üçün riyaziyyat dəyişəcək.

2D matrisdə elementlər eynidir diaqonal eyni məbləğə malikdir onların indeksləri.

Beləliklə, əgər bizdə hamımız varsa eyni cəmi olan elementlər onların indekslərini bir yerə toplayın, o zaman bu elementləri sıra ilə çap etmək kifayətdir.

Alqoritm

  1. Bütün elementləri müvafiq vedrə daxil edin, yəni (i+j)-ci kovada ədəd[i][j].
  2. 0-dan maksimuma qədər hər bir vedrə üçün vedrədəki bütün elementləri çap edin.
    Qeyd: Burada diaqonallar aşağıdan yuxarıya doğrudur, lakin biz girişi keçdik birinci cərgədən matris son sıraya qədər. Ona görə də lazımdır elementləri tərs qaydada çap edin.

Diaqonal Traversal LeetCode HəlliPin

Kodu

Diaqonal keçid üçün C++ kodu

class Solution {
public:
   vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        
        const int N = matrix.size();
        const int M = matrix[0].size();
        
        vector<int> res;
        for(int s = 0; s <= N + M - 2; ++s)
        {
            // for all i + j = s
            for(int x = 0; x <= s; ++x) 
            {
                int i = x;
                int j = s - i;
                if(s % 2 == 0) swap(i, j);

                if(i >= N || j >= M) continue;
                
                res.push_back(matrix[i][j]);
            }
        }
        
        return res;
    }
};

Diaqonal keçid üçün Java kodu

class Solution {
   public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0) return new int[0];
        int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = matrix[r][c];
            if ((r + c) % 2 == 0) { // moving up
                if      (c == n - 1) { r++; }
                else if (r == 0)     { c++; }
                else            { r--; c++; }
            } else {                // moving down
                if      (r == m - 1) { c++; }
                else if (c == 0)     { r++; }
                else            { r++; c--; }
            }   
        }   
        return arr;
    }
}

Diaqonal keçid üçün Python kodu

class Solution:
    def findDiagonalOrder(self, matrix):
        entries = [(i+j, (j, i)[(i^j)&1], val)
                   for i, row in enumerate(matrix)
                   for j, val in enumerate(row)]
        return [e[2] for e in sorted(entries)]

Diaqonal Traversal LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O(n^2) çünki tam matrisin keçidi tələb olunur.

Kosmik Mürəkkəblik

O(n) çünki biz sətir + sütun düymələrinin cəmini saxlamaq üçün heşməpdən istifadə edirik.

Referans: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

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