Правильное решение литкода анаграммы

Постановка задачи Допустимый литкод анаграммы Решение. Даны две строки s и t, вернуть true, если t является анаграммой s, и false в противном случае. Анаграмма — это слово или фраза, образованная путем перестановки букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз. Пример 1: Ввод: s = «анаграмма», t = «нагарам» Вывод: …

Подробнее

Изоморфные строки Решение LeetCode

Постановка задачи Изоморфные строки Решение LeetCode. Имея две строки s и t, определить, изоморфны ли они. Две строки s и t изоморфны, если символы в s можно заменить, чтобы получить t. Все вхождения символа должны быть заменены другим символом с сохранением порядка символов. Никакие два символа не могут отображаться в …

Подробнее

Решение для монотонного массива Leetcode

Постановка задачи: решение литкода монотонного массива. Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums монотонно возрастает, если для всех i <= j nums[i] <= nums[j]. Массив nums монотонно убывает, если для всех i <= j, nums[i] >= nums[j]. Учитывая целочисленный массив nums, вернуть true, если данный …

Подробнее

Решение «Дай пять» LeetCode

Постановка задачи: решение High Five LeetCode. Дан список оценок разных учащихся с именем «элемент», где «элемент» имеет два поля: элемент [0] представляет собой идентификатор учащегося, а элемент [1] представляет собой балл учащегося, например. item[i]=[IDi, SCOREi] Возвращает ответ в виде массива пар результатов, где результат[j] = …

Подробнее

Диапазон Сумма решения BST LeetCode

Range Sum of BST LeetCode Solution говорит, что: учитывая корень, узел двоичного дерева поиска и два целых числа, низкий и высокий, верните сумму значений всех узлов со значением в инклюзивном диапазоне [низкий, высокий]. Пример 1: Ввод: root = [10,5,15,3,7,null,18], low = 7, high = 15 Вывод: 32 Объяснение: …

Подробнее

Повернуть строку Решение LeetCode

Постановка задачи Rotate String LeetCode Решение. Имея две строки s и target, вернуть true тогда и только тогда, когда s может стать target после некоторого количества сдвигов s. Сдвиг на s состоит в перемещении самого левого символа s в крайнее правое положение. Например, если s = «abcde», то будет…

Подробнее

Номер столбца листа Excel Решение LeetCode

Постановка задачи Номер столбца листа Excel LeetCode Решение гласит, что при заданной строке columnTitle, которая представляет заголовок столбца, отображаемый на листе Excel, вернуть соответствующий номер столбца. Например: А -> 1 В -> 2 С -> 3 … Z -> 26 АА -> 27 АВ -> 28 … …

Подробнее

Найдите решение LeetCode городского судьи

Постановка задачи: Найдите литкод городского судьи Решение: В городе есть n человек, помеченных цифрами от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если существует городской судья, то: Городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. …

Подробнее

Решение LeetCode с перекрытием прямоугольников

Постановка задачи: прямоугольное перекрытие Решение LeetCode — говорится, что прямоугольник с выравниванием по оси представлен в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2 , y2) — координата его правого верхнего угла. Его верхний и нижний края параллельны оси X, а левый …

Подробнее

Максимальное количество населения в год Решение LeetCode

Постановка задачи

Максимальное количество населения в год Решение LeetCode говорит, что - Вам дан двумерный целочисленный массив logs где каждый logs[i] = [birthi, deathi] указывает годы рождения и смерти ith человек.

Игровой автомат население какого-то года х - количество людей, живущих в течение этого года. ith человек исчисляется в году xнаселение России, если x находится в в том числе ассортимент [birthi, deathi - 1]. Обратите внимание, что человек не учитываются в год, в котором они умирают.

Return Максимальная численность населения Год.

 

Пример 1:

Входной сигнал:

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

Вывод:

 1993

Объяснение:

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

Пример 2:

Входной сигнал:

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

Вывод:

 1960

Объяснение:

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

 

Ограничения:

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

 

АЛГОРИТМ –

  • Чтобы найти максимальный год населения. Во-первых, мы сосредоточимся на общей численности населения в каждом году, проверяя каждый интервал данной матрицы, найдем максимальное количество и вернем год максимального значения. Если количество одинаковое, мы просто возвращаем предыдущий год (самый ранний год).

Подход к максимальной численности населения в год Решение LeetCode

– Во-первых, мы создадим один массив размером 101, потому что ограничения по годам лежат в диапазоне от 1950 до 2050.

— после этого мы запустим цикл от 0 до длины логов и увеличим количество массива по индексу (logs[i][o]) на 1 и уменьшим количество массива по индексу (logs[i ][1]) на 1

- снова мы запустим цикл от 0 до длины массива и сделаем одну переменную prev подсчетом и обновим каждый элемент массива с помощью array+prev и обновим prev с помощью prev = array[i].

- наконец, мы запустим цикл, найдем максимальное значение в массиве и вернем этот конкретный индекс (index+1950). Отсюда найти максимальный год населения.

Максимальное количество населения в год Решение Leetcode

Код:

Максимальный год населения Решение 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

Максимальный год населения Решение 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;
        
        
    }
}

Анализ сложности решения Leetcode с максимальным населением в год:

Сложность времени

Временная сложность приведенного выше решения составляет O (n).

Сложность времени

Пространственная сложность приведенного выше решения составляет O (1).

Поскольку мы сделали массив длины = 101. Значит, мы можем считать его постоянным

 

 

 

 

 

 

Translate »