2D Vektor LeetCode Həllini düzəldin

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

Düzləşdirin 2D Vektor LeetCode Həll - Dizayn və təkrarlayıcı üçün düzləşdirmək 2D vektor. dəstəkləməlidir next və hasNext əməliyyatları.

Həyata keçirir Vector2D sinif:

• Vector2D(int[][] vec) obyekti 2D vektoru ilə işə salır vec.
• next() 2D vektorundan növbəti elementi qaytarır və göstəricini bir addım irəli aparır. Siz güman edə bilərsiniz ki, bütün zənglər next etibarlıdır.
• hasNext() Yekunları true vektorda hələ də bəzi elementlər varsa, və false başqa cür.

misal

Test işi 1:

Input:

[“Vector2D”, “növbəti”, “növbəti”, “növbəti”, “Next var”, “Next”, “next”, “hasNext”]

[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]

Çıxış:

[null, 1, 2, 3, true, true, 4, false]

Izahat

1. Dəyişməz: Növbəti zəngdən əvvəl x,y üçün növbəti düzgün indeksi saxlayacağıq
2. hasNext biz növbəti çağırmazdan əvvəl çağırılır
3. Unutmayın ki, boş sıralarımız ola bilər
4. Sonra x = vec2d[x,y] çıxarırıq. Əgər y+1 cari cərgənin uzunluğundan azdırsa, y-ni y+1-ə təyin edin. Əks halda, x-i növbəti sıraya artırın. Bu nöqtədə (və başlanğıcda) boş cərgələri tənzimlədiyinizə əmin olun.
5. hasNext sadəcə etibarlı sıra nömrəsini yoxlamalıdır.

İdeya iki iterator saxlamaqdır, it1 iteratordur Siyahılar siyahısında təkrarlamaq. it2 birdir İterator hazırda ziyarət etdiyi Siyahının iteratorudur. Biz hasNext-ə zəng etdikdə növbəti uyğun it1-ni tapmağa çalışırıq. Əgər cari it2 hasNext varsa, o zaman biz eyni it2-dən istifadə etməyə davam edirik, əks halda Next olan Siyahı tapana qədər it2 vasitəsilə Siyahılar siyahısına enirik. Əgər sona çatsaq (!it1.hasNext) bu o deməkdir ki, biz bütün imkanları tükətmişik və biz yalanı qaytarırıq. next() sadəcə olaraq it1.next() funksiyasını qaytarır, çünki hasNext() it2 hasNext olduğuna zəmanət verir.

1. İki göstəricidən istifadə edin, x -> alt massiv indeksi. y -> alt massivdəki ədədin indeksi
2. Daxili next(), cari nömrəni qeyd edin, sonra göstəriciləri köçürün. (* Sonra next() adlanır, x & y həmişə növbəti yerini göstərəcək)
3. Hərəkət x növbəti boş olmayan massivə və ya vektordan kənarda yoxdursa

Flatten 2D Vector üçün kod

Java Proqramı

import java.util.NoSuchElementException;

class Vector2D {
    
    private int[][] v;
    private int row;
    private int col;

    public Vector2D(int[][] v) {
        this.v = v;
        row = 0;
        col = 0;
    }
    
    public int next() {
        skipEmptyRows();
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        int next = v[row][col++];
        // Increment row if col reaches the end of the current row
        if (col == v[row].length) {
            row++;
            col = 0;
        }
        return next;
    }
    
    public boolean hasNext() {
        skipEmptyRows();
        return row < v.length - 1 || (row == v.length - 1 && col < v[row].length);
    }
    
    private void skipEmptyRows() {
        // Skip empty rows
        while (row < v.length && v[row].length == 0) {
            row++;
        }
    }
}

Python proqramı

class Vector2D(object):
    def skip_empty_rows_x(self):
        while self.x < len(self.vec2d) and len(self.vec2d[self.x]) == 0:
            self.x = self.x + 1
        return

    def __init__(self, vec2d):
        """
        Initialize your data structure here.
        :type vec2d: List[List[int]]
        """
        self.vec2d = vec2d
        self.x, self.y = 0, 0
        self.skip_empty_rows_x()

    def next(self):
        """
        :rtype: int
        """
        x = self.vec2d[self.x][self.y]
        self.y = self.y+1
        if self.y == len(self.vec2d[self.x]):
            self.x, self.y = self.x+1, 0
            self.skip_empty_rows_x()
        return x

    def hasNext(self):
        """
        :rtype: bool
        """
        if self.x >= len(self.vec2d):
            return False
        return True

Flatten 2D Vector LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O (n)

Kosmik Mürəkkəblik: O (1) sabit məkandan istifadə etdiyimiz üçün.