Сапраўднае рашэнне анаграмы Leetcode

Пастаноўка праблемы Сапраўдная анаграма Leetcode Рашэнне – дадзены два радкі s і t, вяртае true, калі t з'яўляецца анаграмай s, і false у адваротным выпадку. Анаграма - гэта слова або фраза, утвораная шляхам перастаноўкі літар іншага слова або фразы, звычайна з выкарыстаннем усіх зыходных літар роўна адзін раз. Прыклад 1: Уваход: s = «анаграма», t = «нагарам» Вывад: …

больш падрабязна

Ізаморфныя радкі LeetCode Solution

Пастаноўка праблемы. Ізаморфныя радкі LeetCode Рашэнне – дадзены два радкі s і t, вызначце, ці з'яўляюцца яны ізаморфнымі. Два радкі s і t ізаморфныя, калі сімвалы ў s можна замяніць, каб атрымаць t. Усе ўваходжанні сімвала павінны быць заменены іншым сімвалам з захаваннем парадку сімвалаў. Ніякія два знака не могуць адлюстроўвацца на ...

больш падрабязна

Манатонны масіў Leetcode Solution

Пастаноўка праблемы: Рашэнне манатоннага масіва Leetcode – дадзены масіў манатонны, калі ён альбо манатонна павялічваецца, альбо манатонна памяншаецца. Масіў nums манатонна ўзрастае, калі для ўсіх i <= j nums[i] <= nums[j]. Масіў nums манатонна памяншаецца, калі для ўсіх i <= j nums[i] >= nums[j]. Дадзены цэлы масіў nums, вярнуць ісціну, калі дадзена ...

больш падрабязна

Дай пяць Рашэнне LeetCode

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

больш падрабязна

Сума дыяпазону рашэння BST LeetCode

Сума дыяпазону BST LeetCode Solution кажа, што – Улічваючы корань вузел бінарнага дрэва пошуку і два цэлыя лікі нізкае і высокае, вяртае суму значэнняў усіх вузлоў са значэннем уключна дыяпазону [нізкі, высокі]. Прыклад 1: Уваход: корань = [10,5,15,3,7,нуль,18], нізкі = 7, высокі = 15 Выхад: 32 Тлумачэнне: …

больш падрабязна

Паварот радка LeetCode Solution

Пастаноўка праблемы Паварот радка LeetCode Рашэнне – Улічваючы два радкі s і мэта, вярнуць ісціну тады і толькі тады, калі s можа стаць мэтай пасля пэўнай колькасці зрухаў на s. Зрух на s заключаецца ў перамяшчэнні крайняга левага сімвала s у крайнюю правую пазіцыю. Напрыклад, калі s = "abcde", то гэта будзе ...

больш падрабязна

Нумар слупка аркуша Excel Рашэнне LeetCode

Пастаноўка праблемы Нумар слупка аркуша Excel. У LeetCode Solution сказана, што, улічваючы радок columnTitle, які прадстаўляе загаловак слупка ў выглядзе аркуша Excel, вяртае адпаведны нумар слупка. Напрыклад: A -> 1 B -> 2 C -> 3 … Z -> 26 AA -> 27 AB -> 28 … …

больш падрабязна

Знайдзіце рашэнне гарадскога суддзі LeetCode

Пастаноўка задачы: Знайдзіце гарадскога суддзю Рашэнне кода Leet: У горадзе n чалавек, пазначаных лічбамі ад 1 да n. Ходзяць чуткі, што адзін з гэтых людзей тайна з'яўляецца гарадскім суддзёй. Калі гродскі суддзя ёсць, то: Гродскі суддзя нікому не верыць. Гродскаму суддзю вераць усе (акрамя гродскага). …

больш падрабязна

Рашэнне LeetCode для перакрыцця прастакутніка

Пастаноўка праблемы: перакрыцце прамавугольніка LeetCode Solution – кажа, што прастакутнік, выраўнаваны па восі, прадстаўлены ў выглядзе спісу [x1, y1, x2, y2], дзе (x1, y1) з'яўляецца каардынатай яго ніжняга левага кута, а (x2 , y2) з'яўляецца каардынатай яго правага верхняга вугла. Яго верхні і ніжні краю раўналежныя восі Х, а левы ...

больш падрабязна

Максімальны год насельніцтва LeetCode Solution

Пастаноўка праблемы

Максімальны год насельніцтва LeetCode Solution кажа, што - вам дадзены 2D цэлы масіў logs дзе кожны logs[i] = [birthi, deathi] паказвае гады нараджэння і смерці ith чалавек.

,en насельніцтва некаторых год х - колькасць жывых людзей за гэты год. The ith чалавек залічваецца ў год x' насельніцтва калі x знаходзіцца ў У тым ліку дыяпазон [birthi, deathi - 1]. Звярніце ўвагу, што чалавек ёсць ня залічваецца ў год іх смерці.

Вяртаць Максімальны год насельніцтва.

 

Прыклад 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 Solution

– Спачатку мы створым адзін масіў памерам 101, таму што абмежаванні па гадах ляжаць у дыяпазоне з 1950 па 2050 год.

– пасля гэтага мы запусцім цыкл ад 0 да даўжыні логаў і павялічым колькасць масіва ў index(logs[i][o]) на 1 і паменшым колькасць масіва ў індэксе (logs[i [1]) на 1

– мы зноў запусцім цыкл ад 0 да даўжыні масіва і зробім адну зменную prev count і абнавім кожны элемент масіва па array+prev і update prev па prev = array[i].

– нарэшце, мы запусцім цыкл і знойдзем максімальнае значэнне ў масіве і вернем гэты канкрэтны індэкс (індэкс+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 »