Giltig Anagram Leetcode-lösning

Problemformulering Giltigt Anagram Leetcode Lösning – Givet två strängar s och t, ​​returnera sant om t är ett anagram av s, och annars falskt. Ett anagram är ett ord eller en fras som bildas genom att ordna om bokstäverna i ett annat ord eller en fras, vanligtvis med alla originalbokstäver exakt en gång. Exempel 1: Ingång: s = "anagram", t = "nagaram" Utdata: …

Läs mer

Isomorphic Strings LeetCode Solution

Problembeskrivning Isomorfa strängar LeetCode Lösning – Med tanke på två strängar s och t, ​​avgör om de är isomorfa. Två strängar s och t är isomorfa om tecknen i s kan ersättas för att få t. Alla förekomster av ett tecken måste ersättas med ett annat tecken med bibehållen ordning på tecken. Inga två tecken får mappas till …

Läs mer

Monotonic Array Leetcode-lösning

Problembeskrivning: Den monotona arrayen Leetcode-lösning – Givet att en array är monoton om den antingen är monotont ökande eller monotont minskande. En array nums är monotont ökande om för alla i <= j, nums[i] <= nums[j]. En array nums är monotont avtagande om för alla i <= j, nums[i] >= nums[j]. Givet ett heltalsmatrisantal, returnera sant om det givna ...

Läs mer

Rotera sträng LeetCode-lösning

Problembeskrivning Rotera sträng LeetCode Lösning – Givet två strängar s och mål, returnera sant om och endast om s kan bli mål efter ett visst antal skift på s. En växling på s består av att flytta tecknet längst till vänster i s till positionen längst till höger. Till exempel, om s = "abcde", kommer det att ...

Läs mer

Rektangelöverlappning LeetCode-lösning

Problembeskrivning: Rektangelöverlappning LeetCode Solution – säger att en axelinriktad rektangel representeras som en lista, [x1, y1, x2, y2], där (x1, y1) är koordinaten för dess nedre vänstra hörn, och (x2) , y2) är koordinaten för dess övre högra hörn. Dess övre och nedre kanter är parallella med X-axeln, och dess vänstra …

Läs mer

Maximal befolkningsår LeetCode-lösning

Problemdeklaration

Maximal befolkningsår LeetCode-lösning säger att – Du får en 2D-heltalsmatris logs där var och en logs[i] = [birthi, deathi] anger födelse- och dödsåren för den ith person.

Du har nu möjlighet befolkning på något år x är antalet människor som levde under det året. De ith en person räknas i året xs befolkning om x är i inklusive område [birthi, deathi - 1]. Observera att personen är det inte räknas det år de dör.

Retur den maximala befolkningen år.

 

Exempel 1:

Ingång:

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

Produktion:

 1993

Förklaring:

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

Exempel 2:

Ingång:

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

Produktion:

 1960

Förklaring:

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

 

Begränsningar:

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

 

ALGORITM –

  • För att hitta den maximala befolkningsåret. Först kommer vi att fokusera på den totala antalet populationen under varje år genom att kontrollera varje intervall i den givna matrisen och kommer att hitta det maximala antalet och returnera året med maximalt värde. Om antalet är detsamma återkommer vi helt enkelt föregående år (tidigaste året).

Metod för maximal befolkningsår LeetCode-lösning

– Först kommer vi att skapa en array av storlek 101 eftersom begränsningarna för år ligger i intervallet 1950 till 2050.

– efter det kommer vi att köra en slinga från 0 till längden på loggar och kommer att öka antalet av arrayen vid index(logs[i][o]) med 1 och minska antalet av arrayen vid index (logs[i] ][1]) av 1

– igen kommer vi att köra en slinga från 0 till längden på arrayen och göra en variabel prev count och uppdatera varje element i arrayen med array+prev och uppdatera prev by prev = array[i].

– äntligen kommer vi att köra en loop och hitta det maximala värdet i arrayen och returnera det specifika indexet (index+1950). Hitta därför det maximala befolkningsåret.

Maximal befolkningsår Leetcode-lösning

Koda:

Maximal befolkningsår Python Leetcode lösning:

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

Maximal befolkningsår Java Leetcode-lösning:

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;
        
        
    }
}

Komplexitetsanalys av maximal befolkningsår Leetcode-lösning:

Tidskomplexitet

Tidskomplexiteten för ovanstående lösning är O(n).

Tidskomplexitet

Rymdkomplexiteten för ovanstående lösning är O(1).

Som vi har gjort en matris med längd = 101. Så vi kan betrakta den som konstant

 

 

 

 

 

 

Translate »