Toeplitz matrisi

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Facebook
Geyim MatrisBaxılıb 150

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.

2 ölçülü verilmişdir matris ölçüsü (mxn), matrisin Toeplitz olub olmadığını yoxlayın. Toeplitz matrisi, yuxarıdan sola eyni diaqonaldakı elementlərin bütün diaqonallar üçün eyni olduğu bir matrisdir.

Nümunələr

Input
1 2 3 4
5 1 2 3
9 5 1 2
Buraxılış
doğru
Izahat
Çaprazlar [“1”, “1”, “1”], [“2”, “2”, “2”], [“3”, “3”], [“4”], [“5” ”,“ 5 ”], [“ 9 ”]
Hər diaqonalda bütün elementlər eyni olduğundan matris Toeplitzdir.

Input
1 2
2 2
Buraxılış
saxta
Izahat
Dialgonallar [“1”, “2”], [“2”], [“2”]
Çapraz [“1”, “2”] fərqli elementlərə malikdir, buna görə də matris toeplitz deyil.

Toeplitz Matrisini yoxlamaq üçün alqoritm

Bütün çaprazları tək-tək keçin və bütün elementlər hər hansı bir diaqonal üçün eyni deyilsə, matris Toeplitz deyil, əksinə Toeplitzdir.
Diaqonallar aşağıdakı şəkildə göstərildiyi kimi keçilməlidir,

Toeplitz matrisiPin

Diaqonalların başlanğıc nöqtələri yuxarıdakı misal üçün [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [2, 0].
Ya sütun və ya sıra başlanğıc nöqtələrində 0, başlanğıc nöqtəsindən başlayaraq sıra və sütunun dəyərini 1 artıraraq hər diaqonaldan keçin.

Toeplitz Matrix üçün izah

Nümunəni nəzərdən keçirək,
1 2 3 4
5 1 2 3
9 5 1 2

İlə bütün çaprazları keçin sıfır sıradakı başlanğıc nöqtəsi.
Çapraz 1 : Başlanğıc Noktası = (0, 0)
Elementlər = {1, 1, 1}
Bütün elementlər eynidir, buna görə davam edin.
Çapraz 2 : Başlanğıc Noktası = (0, 1)
Elementlər = {2, 2, 2}
Bütün elementlər eynidir, buna görə davam edin.
Çapraz 3 : Başlanğıc Noktası = (0, 2)
Elementlər = {3, 3, 3}
Bütün elementlər eynidir, buna görə davam edin.
Çapraz 4 : Başlanğıc Noktası = (0, 3)
Elementlər = {4}
Bütün elementlər eynidir, buna görə davam edin.

İlə bütün çaprazları keçin sıfır sütununda başlanğıc nöqtəsi.
Çapraz 1 : Başlanğıc Noktası = (0, 0)
Elementlər = {1, 1, 1}
Bütün elementlər eynidir, buna görə davam edin.
Çapraz 2 : Başlanğıc Noktası = (1, 0)
Elementlər = {5, 5}
Bütün elementlər eynidir, buna görə davam edin.
Çapraz 3 : Başlanğıc Noktası = (2, 0)
Elementlər = {9}
Bütün elementlər eynidir, buna görə davam edin.

Bütün diaqonallar eyni elementə malikdir, ona görə də verilən matris Toeplitzdir.

Toeplitz Matrix üçün JAVA Kodu

public class ToeplitzMatrix {
    private static boolean isToeplitz(int[][] matrix) {
        boolean ans = true;
        int n = matrix.length;
        int m = matrix[0].length;
        
        // First row diagonals
        for (int i = 0; i < m; i++) {
            int x = 0, y = i;
            int curr = matrix[x][y];
            x++; y++;
            while (x < n && y < m) {
                // If any element is not same, this can't be a toeplitz matrix
                if (matrix[x][y] != curr) {
                    ans = false;
                    break;
                }
                // Increment row and column by 1
                x++; y++;
            }
            if (!ans)
                break;
        }

        // First column diagonals
        for (int i = 1; i < n; i++) {
            int x = i, y = 0;
            int curr = matrix[x][y];
            x++; y++;
            while (x < n && y < m) {
                // If any element is not same, this can't be a toeplitz matrix
                if (matrix[x][y] != curr) {
                    ans = false;
                    break;
                }
                // Increment row and column by 1
                x++; y++;
            }
            if (!ans)
                break;
        }

        return ans;
    }

    public static void main(String[] args) {
        // Example 1
        int[][] matrix = new int[][] {
                {1, 2, 3, 4},
                {5, 1, 2, 3},
                {9, 5, 1, 2}};
        System.out.println(isToeplitz(matrix));

        // Example 2
        int[][] matrix2 = new int[][] {
                {1, 2},
                {2, 2}
        };
        System.out.println(isToeplitz(matrix2));
    }
}

Toeplitz Matrix üçün C ++ Kodu

#include<bits/stdc++.h> 
using namespace std;

int matrix[4][4];

bool isToeplitz(int n, int m) {
    bool ans = true;

    // First row diagonals
    for (int i = 0; i < m; i++) {
        int x = 0, y = i;
        int curr = matrix[x][y];
        x++; y++;
        while (x < n && y < m) {
            // If any element is not same, this can't be a toeplitz matrix
            if (matrix[x][y] != curr) {
                ans = false;
                break;
            }
            // Increment row and column by 1
            x++; y++;
        }
        if (!ans)
            break;
    }

    // First column diagonals
    for (int i = 1; i < n; i++) {
        int x = i, y = 0;
        int curr = matrix[x][y];
        x++; y++;
        while (x < n && y < m) {
            // If any element is not same, this can't be a toeplitz matrix
            if (matrix[x][y] != curr) {
                ans = false;
                break;
            }
            // Increment row and column by 1
            x++; y++;
        }
        if (!ans)
            break;
    }

    return ans;
}

int main() {
    // Example 1
    matrix[0][0] = 1;
    matrix[0][1] = 2;
    matrix[0][2] = 3;
    matrix[0][3] = 4;
    matrix[1][0] = 5;
    matrix[1][1] = 1;
    matrix[1][2] = 2;
    matrix[1][3] = 3;
    matrix[2][0] = 9;
    matrix[2][1] = 5;
    matrix[2][2] = 1;
    matrix[2][3] = 2;
    if (isToeplitz(3, 4)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    // Example 2
    matrix[0][0] = 1;
    matrix[0][1] = 2;
    matrix[1][0] = 2;
    matrix[1][1] = 2;
    if (isToeplitz(2, 2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (m * n)
Kosmik Mürəkkəblik = O (1) 
burada m və n - 2D matrisindəki sətir və sütun sayı.

References

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