Solución Leetcode de anagrama válida

Enunciado do problema Anagrama válido Leetcode Solución – Dadas dúas cadeas s e t, devolve verdadeiro se t é un anagrama de s, e falso en caso contrario. Un anagrama é unha palabra ou frase formada reorganizando as letras dunha palabra ou frase diferente, normalmente usando todas as letras orixinais exactamente unha vez. Exemplo 1: Entrada: s = “anagrama”, t = “nagaram” Saída: …

Le máis

Cadenas isomórficas Solución LeetCode

Enunciado do problema Cordas isomórficas LeetCode Solución – Dadas dúas cadeas s e t, determine se son isomórficas. Dúas cadeas s e t son isomórficas se os caracteres de s poden substituírse para obter t. Todas as ocorrencias dun personaxe deben substituírse por outro carácter conservando a orde dos caracteres. Non se poden asignar dous personaxes ao...

Le máis

Solución Leetcode de matriz monótona

Declaración do problema: a solución Leetcode de matriz monótona: dada unha matriz é monótona se é monótona crecente ou monótona decrecente. Unha matriz nums é monótona crecente se para todo i <= j, nums[i] <= nums[j]. Unha matriz nums é monótona decrecente se para todo i <= j, nums[i] >= nums[j]. Dada unha matriz enteira nums, devolve verdadeiro se o dado...

Le máis

Solución High Five LeetCode

Declaración do problema: a solución de High Five LeetCode: dada unha lista de puntuacións de diferentes estudantes chamado "elemento", onde o "elemento" ten dous campos item[0] representa a identificación do alumno, e item[1] representa a puntuación do alumno, por exemplo. item[i]=[IDi, SCOREi] Devolve a resposta como resultado dunha matriz de pares, onde result[j] =...

Le máis

Rango Suma da solución BST LeetCode

Suma do intervalo da solución BST LeetCode di que: dada a raíz do nodo dunha árbore de busca binaria e dous números enteiros baixo e alto, devolve a suma dos valores de todos os nodos cun valor no rango inclusivo [baixo, alto]. Exemplo 1: Entrada: raíz = [10,5,15,3,7,nulo,18], baixo = 7, alto = 15 Saída: 32 Explicación: …

Le máis

Xire a cadea Solución LeetCode

Enunciado do problema Solución LeetCode de rotación da cadea – Dadas dúas cadeas s e obxectivo, devolve verdadeiro se e só se s pode converterse en obxectivo despois dun número de desprazamentos en s. Un desprazamento en s consiste en mover o carácter máis á esquerda de s á posición máis dereita. Por exemplo, se s = "abcde", entón...

Le máis

Número de columna da folla de Excel Solución LeetCode

Declaración do problema Número de columna da folla de Excel A solución LeetCode di que Dada unha cadea columnTitle que representa o título da columna como aparece nunha folla de Excel, devolve o seu número de columna correspondente. Por exemplo: A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28 … …

Le máis

Atopa a solución LeetCode de Town Judge

Declaración do problema: atopar o xuíz da cidade Leetcode Solución: nunha cidade, hai n persoas etiquetadas de 1 a n. Corre o rumor de que unha destas persoas é en segredo o xuíz da cidade. Se o xuíz da cidade existe, entón: O xuíz da cidade non confía en ninguén. Todo o mundo (agás o xuíz municipal) confía no xuíz municipal. …

Le máis

Rectangle Overlap Solución LeetCode

Enunciado do problema: Rectangle Overlap LeetCode Solution – di que Un rectángulo aliñado no eixe represéntase como unha lista, [x1, y1, x2, y2], onde (x1, y1) é a coordenada da súa esquina inferior esquerda e (x2) , y2) é a coordenada da súa esquina superior dereita. Os seus bordos superior e inferior son paralelos ao eixe X, e o seu esquerdo...

Le máis

Ano de poboación máxima Solución LeetCode

Declaración do problema

Ano de poboación máxima Solución LeetCode di que: recibes unha matriz de enteiros 2D logs onde cada un logs[i] = [birthi, deathi] indica os anos de nacemento e morte do ith persoa.

o poboación dun ano x é o número de persoas vivas durante ese ano. O ith unha persoa cóntase no ano xa poboación de se x está no incluso alcance [birthi, deathi - 1]. Teña en conta que a persoa é non contados no ano en que morren.

retorno o Ano de poboación máxima.

 

Exemplo 1:

Entrada:

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

saída:

 1993

Explicación:

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

Exemplo 2:

Entrada:

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

saída:

 1960

Explicación:

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

 

Restricións:

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

 

ALGORITMO -

  • Co fin de atopar o ano de poboación máxima. En primeiro lugar, centrarémonos no número total de poboación de cada ano comprobando cada intervalo da matriz dada e atoparemos o reconto máximo e devolveremos o ano de valor máximo. Se o reconto é o mesmo, simplemente devolvemos o ano anterior (o ano máis antigo).

Enfoque para o ano de poboación máxima Solución LeetCode

– En primeiro lugar, crearemos unha matriz de tamaño 101 porque as limitacións dos anos están no intervalo de 1950 a 2050.

– despois diso, executaremos un bucle de 0 ata a lonxitude dos rexistros e aumentaremos o reconto da matriz en index(logs[i][o]) en 1 e diminuiremos o reconto da matriz no índice (logs[i ][1]) por 1

– de novo executaremos un bucle desde 0 ata a lonxitude da matriz e faremos que unha variable prev conte e actualizaremos cada elemento da matriz mediante array+prev e actualizaremos prev by prev = array[i].

– por fin, executaremos un bucle e atoparemos o valor máximo na matriz e devolveremos ese índice en particular (índice+1950). Polo tanto, atopar o ano máximo de poboación.

Ano de poboación máxima Solución Leetcode

código:

Ano de poboación máxima Solución 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

Ano de poboación máxima Solución 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;
        
        
    }
}

Análise de complexidade do ano de poboación máxima Solución Leetcode:

Complexidade do tempo

A complexidade temporal da solución anterior é O(n).

Complexidade do tempo

A complexidade espacial da solución anterior é O(1).

Como fixemos unha matriz de lonxitude = 101. Así que podemos considerala constante

 

 

 

 

 

 

Translate »