Platné riešenie Anagram Leetcode

Vyhlásenie o probléme Platný anagram Leetcode Riešenie – Dané dva reťazce s a t vrátia hodnotu true, ak t je anagram s, a v opačnom prípade vráti hodnotu false. Anagram je slovo alebo fráza vytvorená preskupením písmen iného slova alebo frázy, pričom sa zvyčajne používajú všetky pôvodné písmená presne raz. Príklad 1: Vstup: s = „anagram“, t = „nagaram“ Výstup: …

Čítaj viac

Monotónne riešenie Leetcode Array

Vyhlásenie o probléme: Riešenie Monoton Array Leetcode – Dané pole je monotónne, ak sa buď monotónne zvyšuje alebo monotónne znižuje. Pole nums je monotónne rastúce, ak pre všetky i <= j, nums[i] <= nums[j]. Pole nums je monotónne klesajúce, ak pre všetky i <= j, nums[i] >= nums[j]. Dané celočíselné pole nums, vráti hodnotu true, ak je daný…

Čítaj viac

Rozsah Súčet riešenia BST LeetCode

Range Sum of BST LeetCode Solution hovorí, že – Vzhľadom na koreň, uzol binárneho vyhľadávacieho stromu a dve celé čísla nízke a vysoké, vráti súčet hodnôt všetkých uzlov s hodnotou v inkluzívnom rozsahu [nízka, vysoká]. Príklad 1: Vstup: odmocnina = [10,5,15,3,7,null,18], nízka = 7, vysoká = 15 Výstup: 32 Vysvetlenie: …

Čítaj viac

Otočte reťazec LeetCode Solution

Vyhlásenie o probléme Rotate String LeetCode Riešenie – Vzhľadom na dva reťazce s a cieľ vráťte hodnotu true vtedy a len vtedy, ak sa s môže stať cieľom po určitom počte posunov na s. Posun na s pozostáva z posunutia znaku s úplne vľavo do polohy úplne vpravo. Napríklad, ak s = „abcde“, potom bude ...

Čítaj viac

Číslo stĺpca hárka Excelu Riešenie LeetCode

Vyhlásenie o probléme Číslo stĺpca hárka Excel LeetCode Solution hovorí, že vzhľadom na reťazec columnTitle, ktorý predstavuje názov stĺpca, ako sa zobrazuje v hárku programu Excel, vráti zodpovedajúce číslo stĺpca. Napríklad: A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28 … …

Čítaj viac

Riešenie LeetCode prekrývajúce sa obdĺžnikom

Vyhlásenie o probléme: Rectangle Overlap LeetCode Solution – hovorí, že osovo zarovnaný obdĺžnik je reprezentovaný ako zoznam [x1, y1, x2, y2], kde (x1, y1) je súradnica jeho ľavého dolného rohu a (x2 , y2) je súradnica jeho pravého horného rohu. Jeho horný a spodný okraj sú rovnobežné s osou X a jeho ľavý…

Čítaj viac

Maximálny rok populácie Riešenie LeetCode

Vyhlásenie o probléme

Maximálny rok populácie Riešenie LeetCode hovorí, že – Dostali ste 2D celočíselné pole logs kde každý logs[i] = [birthi, deathi] označuje roky narodenia a úmrtia ith osoba.

و obyvateľstvo nejakého roka x je počet ľudí žijúcich v danom roku. The ith osoba sa počíta v r x's populácie ak x je v vrátane rozsah [birthi, deathi - 1]. Všimnite si, že osoba je nie počítané v roku, keď zomrú.

Návrat rok s maximálnym počtom obyvateľov.

 

Príklad 1:

vstup:

 logs = [[1993,1999],[2000,2010]]

Výkon:

 1993

Vysvetlenie:

 The maximum population is 1, and 1993 is the earliest year with this population.

Príklad 2:

vstup:

 logs = [[1950,1961],[1960,1971],[1970,1981]]

Výkon:

 1960

Vysvetlenie:

 
The maximum population is 2, and it had happened in years 1960 and 1970.
So the maximum population year is 1960.

 

Obmedzenia:

  • 1 <= logs.length <= 100
  • 1950 <= birthi < deathi <= 2050

 

ALGORITHM –

  • S cieľom nájsť rok s maximálnym počtom obyvateľov. Najprv sa zameriame na celkový počet obyvateľov v každom roku kontrolou v každom intervale danej matice a nájdeme maximálny počet a vrátime rok maximálnej hodnoty. Ak je počet rovnaký, jednoducho vrátime predchádzajúci rok (najskorší rok).

Prístup k maximálnej populácii Rok riešenie LeetCode

– Najprv vytvoríme jedno pole veľkosti 101, pretože obmedzenia rokov ležia v rozsahu 1950 až 2050.

– potom spustíme cyklus od 0 do dĺžky logov a zvýšime počet poľa na indexe (logs[i][o]) o 1 a znížime počet poľa na indexe (logs[i ][1]) od 1

– opäť spustíme cyklus od 0 do dĺžky poľa a spočítame jednu premennú prev a aktualizujeme každý prvok poľa pomocou array+prev a update prev pomocou prev = array[i].

– konečne spustíme cyklus a nájdeme maximálnu hodnotu v poli a vrátime tento konkrétny index (index + 1950). Nájdite teda maximálny počet obyvateľov v roku.

Riešenie Leetcode za rok s maximálnym počtom obyvateľov

kód:

Maximálny rok populácie Riešenie Python Leetcode:

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        arr = [0]*101
        for i in range(len(logs)):
            
            arr[logs[i][0]-1950] += 1
            
            arr[logs[i][1]-1950] -= 1
            
        
        previous = arr[0]
        for i in range(1,101):
            arr[i] += previous
            previous = arr[i]
            
        print(arr)
        maxi = 0
        ind = 0
        
        for i in range(len(arr)):
            if arr[i] > maxi:
                maxi = arr[i]
                ind = i + 1950
        print(maxi)        
        return ind

Maximálny rok populácie Riešenie Java Leetcode:

class Solution {
    public int maximumPopulation(int[][] logs) {
        
        int[] arr = new int[101];
        for(int i = 0;i < logs.length;i++){
            
            arr[logs[i][0]-1950] +=1;
            arr[logs[i][1]-1950] -=1;
            
            
        }
        
        int prev = arr[0];
        for(int i=1;i<arr.length;i++){
            
            arr[i] += prev;
            prev = arr[i];
            
        }
        
        int ind = 0;
        int maxi = 0;
        
        for(int i=0;i<arr.length;i++){
            
            if(maxi < arr[i]){
                
                maxi = arr[i];
                ind = i+1950;
            }
        }
        
        
        return ind;
        
        
    }
}

Analýza zložitosti riešenia Leetcode pre rok s maximálnym počtom obyvateľov:

Časová zložitosť

Časová zložitosť vyššie uvedeného riešenia je O(n).

Časová zložitosť

Priestorová zložitosť vyššie uvedeného riešenia je O(1).

Keďže sme vytvorili pole dĺžky = 101. Môžeme ho teda považovať za konštantné

 

 

 

 

 

 

Translate »