İç içə Siyahı Çəki Cəmi II LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Facebook LinkedInBaxılıb 87

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

İç İçə Siyahı Çəki Cəmi II LeetCode Həlli – Sizə tam ədədlərin iç-içə siyahısı verilir nestedList. Hər bir element ya tam ədəd, ya da elementləri tam ədədlər və ya digər siyahılar ola bilən siyahıdır.

The dərinlik tam ədəd onun daxilində olduğu siyahıların sayıdır. Məsələn, daxili siyahı [1,[2,2],[[3],2],1] hər bir tam ədədin dəyərinə malikdir dərinlik. Qoy maxDepth olmaq maksimum dərinlik istənilən tam ədəddən.

The çəki tam ədəddir maxDepth - (the depth of the integer) + 1.

Qayıtmaq hər tam ədədin cəmi nestedList onunla vurulur çəki.

misal

Test işi 1:

Input:

iç içə siyahı = [[1, 1], 2, [1, 1]]

Çıxış:

8

İç içə Siyahı Çəki Cəmi II LeetCode HəlliPin

Explanation:

Çəkisi 1 olan dörd 1, çəkisi 2 olan bir 2.

1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

Yanaşma:

Məbləği hesablamadan əvvəl maksimum dərinliyi tapmalıyıq. Beləliklə, indiyə qədər ziyarət etdiyimiz tam ədədləri qeyd etmək üçün HashMap istifadə edirik.

Bütün girişləri ziyarət etdikdən və maxDepth-i əldə etdikdən sonra məbləği hesablamağa başlaya bilərik.
HashMap-də biz ziyarət etdiyimiz bütün tam ədədləri qeyd etməyə ehtiyac yoxdur, sadəcə olaraq, cari dərinlikdə tam ədədlərin cəmini qeyd etməliyik.

İki keçidli həll

  • İlk keçiddə iç içə siyahının maksimum dərinliyini əldə edin. Rekursiya göz qabağındadır – siyahıdan keçin və əgər iç içə Siyahı varsa, onun dərinliyini tapın. Son dərinlik istənilən iç içə Siyahıdan maksimum dərinlikdir.

Keşlə Tək Keçid Həlli

  • Daxili Siyahı Çəki Cəmi I kimi həlli mühəndisləşdirin, lakin hər bir səviyyədə cəmi heç bir çəki olmadan saxlayın.
  • Tamamlandıqdan sonra dərinlik olacaq maksimum səviyyəni biləcəksiniz. Çəkili məbləği hesablamaq üçün bundan istifadə edin.

BFS kimi yanaşmadan istifadə edərək Tək Keçid Həll

  • Səviyyədəki bütün tam ədədləri level_sum-a əlavə edin. Tam ədəd olmayan (və siyahı növü olan) bütün elementləri növbəti iterasiya üçün siyahıya itələyin. Bu siyahını hamarlaşdırdığınızdan əmin olun, əks halda sonsuz döngə.
  • İndi biz yalnız bir dəfə level_sum başlatırıq. Və ona ardıcıl səviyyənin tam ədədləri əlavə olunur. Səviyyə başa çatdıqdan sonra onu total_sum-a əlavə edirik. Bu, təbii olaraq vurma məntiqini həyata keçirir - aşağı səviyyəli məbləğlər ümumi məbləğə dəfələrlə əlavə olunur.

İç İçə Siyahı Çəki Cəmi üçün kod II

Python proqramı

class Solution(object):
    def depthSumInverse(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        total_sum, level_sum = 0, 0
        while len(nestedList):
            next_level_list = []
            for x in nestedList:
                if x.isInteger():
                    level_sum += x.getInteger()
                else:
                    for y in x.getList():
                        next_level_list.append(y)
            total_sum += level_sum
            nestedList = next_level_list
        return total_sum

Java Proqramı

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        if (nestedList == null) return 0;
        Queue<NestedInteger> queue = new LinkedList<NestedInteger>();
        int prev = 0;
        int total = 0;
        for (NestedInteger next: nestedList) {
            queue.offer(next);
        }
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            int levelSum = 0;
            for (int i = 0; i < size; i++) {
                NestedInteger current = queue.poll();
                if (current.isInteger()) levelSum += current.getInteger();
                List<NestedInteger> nextList = current.getList();
                if (nextList != null) {
                    for (NestedInteger next: nextList) {
                        queue.offer(next);
                    }
                }
            }
            prev += levelSum;
            total += prev;
        }
        return total;
    }
}

İç-içə Siyahı Çəki Cəmi II LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: Hər bir daxili element içəriyə qoyulur queue və düz bir dəfə növbədən çıxarılıb.

Kosmik Mürəkkəblik: O(N). BFS-də kosmik mürəkkəblik üçün ən pis vəziyyət elementlərin əksəriyyəti eyni dərinlikdə olduqda baş verir.

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