Cuprins

Introducere 1.1
Listă Legată 1.2
Ciclul listei înlănț uite 1.2.1
Inversează lista înlănț uită 1.2.2
Ș terge un Nod într-o Listă Înregistrată 1.2.3
Îmbină două liste sortate 1.2.4
Intersecț ia a Două Liste Legate 1.2.5
Ciclul Listei Înlănț uite II 1.2.6
Listă legată palindromă 1.2.7
Îndepărtaț i elementele din lista înlănț uită 1.2.8
Eliminarea duplicatelor din lista legată sortată 1.2.9
Elimină duplicatele din lista legată sortată II 1.2.10
Schimbă nodurile în perechi 1.2.11
Eliminaț i nodul N de la sfârș itul listei 1.2.12
Copaci 1.3
Parcurgere Preorder 1.3.1
Iterator BST 1.3.2
Traversare Inorder 1.3.3
Arbore Simetric 1.3.4
Arbore Binare Echilibrat 1.3.5
Cea mai apropiată valoare din BST 1.3.6
Parcurgere postorder 1.3.7
Adâncimea maximă a arborelui binar 1.3.8
Inversează arborele binar 1.3.9
Aceeaș i arbore 1.3.10
Cel mai mic strămoș comun al unui arbore de căutare binar 1.3.11
Cel mai mic strămoș comun într-un arbore binar 1.3.12

1
 Arbori de Căutare Binari Unici 1.3.13
Arborele Binare de Căutare Unic II 1.3.14
Suma Căii 1.3.15
Suma maximă a căii din arborele binar 1.3.16
Parcurgerea arborilor binari pe niveluri 1.3.17
Validaț i arborii de căutare binară 1.3.18
Adâncimea minimă a unui arbore binar 1.3.19
Transformă un array sortat într-un arbore binar de căutare 1.3.20
Aplatizaț i arborele binar într-o listă legată 1.3.21
Construiț i un arbore binar din traversarea înordine ș i preordine 1.3.22
Cărț ile Binară 1.3.23
Recuperaț i arborele binar de căutare 1.3.24
Suma Căii II 1.3.25
Parcurgerea în ordine de nivel binar II 1.3.26
K-a cel mai mic element într-un BST 1.3.27
Construieș te un arbore binar din parcurgerea în ordine ș i parcurgerea în postordine 1.3.28
Vedere din partea dreaptă a arborelui binar 1.3.29
Suma numerelor de la rădăcină la frunză 1.3.30
Parcurgerea în ordine zigzag a unui arbore binar 1.3.31
Hotul de case III 1.3.32
Succesor în ordine în BST 1.3.33
Secvenț a consecutivă cea mai lungă din arborele binar 1.3.34
Verificarea secvenț ei preordine în Arborele de Căutare Binare 1.3.35
Arbore Binární Cu Susul În Jos 1.3.36
Numără Subarborele Unival 1.3.37
Serializare ș i Deserializare a Arborelui Binare 1.3.38
Grafice 1.4
Numărul de componente conectate într-un graf neorientat 1.4.1
Programul cursului 1.4.2
Graf arbore valid 1.4.3

2
 Programul cursurilor 2 1.4.4
Numărul insulelor 1.4.5
Heap-uri 1.5
Îmbină K liste legate sortate 1.5.1
Cel de-al K-lea element cel mai mare dintr-un tablou 1.5.2
Arregi 1.6
2 Sum II 1.6.1
2 Suma III 1.6.2
Conț ine duplicate 1.6.3
Rotează Array 1.6.4
3 Sume Mai Mici 1.6.5
3 Suma Aproape 1.6.6
3 Sumă 1.6.7
Două Sume 1.6.8
Plus Un 1.6.9
Cel mai bun moment pentru a cumpăra ș i a vinde acț iuni 1.6.10
Distanț a cea mai scurtă între cuvinte 1.6.11
Mută zerourile 1.6.12
Conț ine duplicate II 1.6.13
Element majoritar 1.6.14
Eliminaț i duplicatele dintr-un tablou sortat 1.6.15
Suma Greutăț ii Listelor Înglobate 1.6.16
Suma Ponderată a Listei Înglobate II 1.6.17
Elimină elementul 1.6.18
Intersecț ia a două array-uri II 1.6.19
Îmbinaț i tablourile sortate 1.6.20
Inversarea vocalelor dintr-un ș ir 1.6.21
Intersectia a Două Arne 1.6.22
Containerul cu cea mai multă apă 1.6.23
Produsul Array, cu excepț ia Sinelui 1.6.24

3
 Capcana pentru apă de ploaie 1.6.25
Subsirul maxim 1.6.26
Cel mai bun timp pentru a cumpăra ș i a vinde acț iuni II 1.6.27
Găseș te minimul într-un array sortat rotit 1.6.28
Triunghiul lui Pascal 1.6.29
Triunghiul lui Pascal II 1.6.30
Intervale rezumative 1.6.31
Numărul lipsă 1.6.32
Ș iruri 1.7
Anagram valid 1.7.1
Palindrom valabil 1.7.2
Model de cuvinte 1.7.3
Paranteze valide 1.7.4
Stringuri izomorfe 1.7.5
String invers 1.7.6
Manipularea biț ilor 1.8
Suma a două numere întregi 1.8.1
Număr singular 1.8.2
Numărul Unic II 1.8.3
Numărul unic III 1.8.4
Matematică 1.9
Inversarea întregului 1.9.1
Număr palindrom 1.9.2
Pow(x,n) 1.9.3
Submulț imi 1.9.4
Submulț imi II 1.9.5
Fraction la Decimal Recursiv 1.9.6
Numărul coloanei foii Excel 1.9.7
Titlu Coloană Foaie Excel 1.9.8
Zero-uri finale ale factorialului 1.9.9

4
 Număr fericit 1.9.10
Numără Primele 1.9.11
Plus Unu 1.9.12
Împarte două întregi 1.9.13
Înmulț iț i ș iruri 1.9.14
Puncte maxime pe o linie 1.9.15
Produsul tabloului cu excepț ia de sine 1.9.16
Puterea celor Trei 1.9.17
Împărț irea întregului 1.9.18
Puterea celor patru 1.9.19
Adaugă cifre 1.9.20
Număr urât 1.9.21
Numărul urât II 1.9.22
Număr Super Urât 1.9.23
Găsiț i K perechi cu cele mai mici sume 1.9.24
Autoîncruciș are 1.9.25
Pictaț i gardul 1.9.26
Comutator de Becuri 1.9.27
Jocul Nim 1.9.28
Matriț ă 1.10
Roteș te imaginea 1.10.1
Setaț i matricea cu zero 1.10.2
Căutaț i într-o matrice 2D 1.10.3
Caută o matrice 2D II 1.10.4
Matrice spiralată 1.10.5
Matricea spirală II 1.10.6
Design 1.11
Cache LRU 1.11.1

5
Introducere

Soluț iile mele Leetcode în Python

Această carte va conț ine soluț iile mele în Python pentru problemele de pe leetcode. În prezent, eu
voi încerca doar să public soluț iile acceptate. Planul este să includem în cele din urmă
explicaț ii detaliate pentru fiecare soluț ie. Fac asta doar de distracț ie.

6
Ciclul Listei Înlănț uite

Ciclul în lista înlănț uită

Dat fiind o listă legată, determină dacă are un ciclu în ea.

Urmărire: Poț i să o rezolvi fără a folosi spaț iu suplimentar?

URL: [Link]

# Defini ț ie pentru listă legată simplu.

# clasa ListNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie(object):

def areCicluri(self, cap):
"""
:tip cap: ListNode
:rtype: bool
"""
dacă capul == None:
returnează False
altfel:
fast = head
slow = head

în timp ce fast != None ș i [Link] != None:

slow = [Link]
rapid = [Link]
dacă rapid == lent:
pauză

dacă fast == None sau [Link] == None:

returnează Fals
elif rapid == lent:
returnează Adevărat

returnează Fals

7
Ciclul din Lista Legată

8
Inversează lista legată

Inversează lista legată

Inversează o listă legată simplu.

URL:[Link]

# Defini ț ie pentru listă legată simplu.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie (obiect):

def inversareLista(self, cap):
"""
:tip cap: NodLista
:rtype: ListNode
"""
dacă capul == None:
returnează Nimic

elif head != None ș i [Link] == None:

returnează capul

altfel:
temp = None
next_node = None
în timp ce head != None:
next_node = [Link]
[Link] = temp
temp = cap
cap = nod_urmator

returna ț i temp

9
Ș terge nodul dintr-o listă legată

Delete Node in a Linked List

Scrie o funcț ie pentru a ș terge un nod (cu excepț ia coada) dintr-o listă legată simplu, dat doar
acces la acel nod.

Se presupune că lista legată este 1 -> 2 -> 3 -> 4 ș i ț i se dă al treilea nod cu

valoarea 3, lista legată ar trebui să devină 1 -> 2 -> 4 după apelarea funcț iei tale.

URL: [Link]

# Defini ț ie pentru listă legată simplu.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie(obiect):

def stergeNod(self, nod):
"""
:tip nod: ListNode
:rtype: void Nu returna ț i nimic, modifica ț i nodul în loc
în schimb.
"""
dacă nodul == None:
trece
altfel:
next_node = [Link]
[Link] = next_node.val
[Link] = next_node.next

10
Îmbină două liste sortate

Fuzionarea a două liste sortate

Îmbinaț i două liste legate sortate ș i returnaț i-o ca o nouă listă. Noua listă ar trebui să fie
realizat prin îmbinarea nodurilor din primele două liste.

URL:[Link]

11
Fuzionarea a două liste sortate

Defini ț ie pentru listă simplu legată.

# clasa ListNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie (implicit):

def combinăDouăListe(self, l1, l2):
"""
:tip l1: ListNode
:tip l2: ListNode
:rtype: ListNode
"""
dacă l1 == None ș i l2 == None:
returna ț i nimic
elif l1 != None ș i l2 == None:
returnează l1

elif l2 != None ș i l1 == None:

return l2
altfel:
dummy = ListNode(0)
p = dummy

în timp ce l1 != None ș i l2 != None:

dacă [Link] < [Link]:
[Link]ător = l1
l1 = [Link]ător
altfel:
[Link] = l2
l2 = [Link]ător
p = [Link]ător

dacă l1 != None:
[Link]ătorul = l1

dacă l2 != None:
[Link] = l2

return [Link]

12
Îmbină două liste sortate

13
Intersecț ia a două liste legate

Intersecț ia a Două Liste Legate

Scrie un program pentru a găsi nodul la care se intersectează două liste legate simplu.
începe.

De exemplu, următoarele două liste legate:

A: a1 → a2↘c1 → c2 → c3↗
B: b1 → b2 → b3 încep să se intersecteze la nodul c1.

Notes:

Dacă cele două liste legate nu au nicio intersecț ie, întoarce null. Listele legate trebuie să
îș i păstrează structura originală după ce funcț ia returnează. Poț i presupune că există
nu există cicluri nicăieri în întreaga structură legată. Codul tău ar trebui să ruleze, de preferinț ă
în timp O(n) ș i foloseș te doar O(1) memorie.

URL: [Link]

# Defini ț ie pentru listă legată simplu.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasa Solu ț ie(object):

def obtineNodIntersectie(self, capA, capB):
"""
:tip cap1, cap1: ListNode
:rtype: ListNode
"""
Dacă headA == None ș i headB == None:
reveni Niciunul
elif headA == None ș i headB != None:
return None
elif headA != None ș i headB == None:
return None
altfel:
len_a = 0

14
Intersecț ia a două liste legate

len_b = 0

curent = capA
în timp ce current != None:
curent = [Link]
len_a += 1

current = headB
în timp ce current != None:
curent = [Link]ător
len_b += 1

diff = 0
current = None
dacă len_a > len_b:
diff = len_a - len_b
currentA = headA
currentB = headB
altfel:
diff = len_b - len_a
currentA = headB
currentB = headA

count = 0
în timp ce numărul este mai mic decât diferen ț a:

currentA = [Link]
count += 1

în timp ce currentA != None ș i currentB != None:

dacă currentA == currentB:
return currentA
altfel:
currentA = [Link]ător
currentB = [Link]

15
Ciclul listei legate II

Ciclul II al listei înlănț uite

Dat fiind o listă legată, returnaț i nodul unde începe ciclul. Dacă nu există ciclu,
return null.

Notă: Nu modificaț i lista legată.

Urmăreș te: Poț i să o rezolvi fără a folosi spaț iu suplimentar?

URL: [Link]

16
Ciclul în Lista Încatenată II

# Defini ț ie pentru listă simplu legată.

# clasa ListNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie (obiect):

def detectCycle(self, head):
"""
:tip cap: ListNode
:rtype: ListNode
"""
dacă head == None:
returnează capul

altfel:
fast = head
slow = head

has_cycle = False
în timp ce fast != None ș i [Link] != None:
lento = [Link]
rapid = [Link]ă[Link]ătoare

dacă rapid == lent:

has_cycle = True
pauză

dacă has_cycle == Fals:

return None

slow = head
în timp ce rapid != lent:
rapid = [Link]ător
slow = [Link]

întoarcere lentă

17
Listă legată palindromă

Listă legată palindrom

Având o listă simplu legată, determină dacă este un palindrom.

Urmărire: Ai putea să o faci în timp O(n) ș i spaț iu O(1)?

URL:[Link]

18
Lista înlănț uită palindromă

# Defini ț ie pentru listă legată simplu.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasa Solu ț ie(obiect):

def estePalindrom(self, cap):
"""
:tip cap: ListNode
:rtype: bool
"""
dacă cap == None:
returnează Adevărat

elif head != None ș i [Link] == None:

întoarce Adevărat

altfel:
fast = head
slow = head
stack = []
în timp ce fast != None ș i [Link] != None:
[Link]([Link])
slow = [Link]
fast = [Link]

#doamnă
dacă rapid != Nimic:
slow = [Link]

în timp ce lent != None:

dacă [Link] != [Link]():
returnează False
altfel:
încet = î[Link]ător

returnează Adevărat

19
Listă înlănț uită palindromă

20
Ș terge elementele din lista legată

Elimină elementele din lista legată

Eliminaț i toate elementele dintr-o listă legată de întregi care au valoarea val.

Exemplu dat: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Returnaț i: 1 --> 2 --> 3 -->
4 --> 5

URL: [Link]

21
Eliminaț i elementele din lista legată

Defini ț ie pentru listă legată simplu.

# clasa ListNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie(obiect):

def eliminaElemente(self, cap, val):
"""
:tip cap: NodListe
:type val: int
:rtype: ListNode
"""
dacă capul == None:
întoarce capul
elif cap != None ș i [Link]ător == None:
dacă [Link] == val:
întoarce None
altfel:
returnează capul

altfel:
dummy = ListNode(0)
[Link] = head
prev = dummy

în timp ce cap != Niciuna:

dacă [Link] == val:

[Link] = [Link]
cap = prev
prev = cap
head = [Link]

return [Link]

22
Eliminaț i duplicatele din lista înlănț uită sortată

Elimină duplicatele din lista legată sortată

Lista
Având o listă legată sortată, ș tergeț i toate duplicatele astfel încât fiecare element să apară doar o dată.

odată.

De exemplu, dat 1->1->2, returnează 1->2. Dat 1->1->2->3->3, returnează 1->2->3.

URL: [Link]

23
Eliminaț i duplicatele din lista legată sortată

Defini ț ie pentru listă legată simplu.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solu ț ie(object):

def eliminareDuplica(self, cap):
"""
:tip cap: ListNode
:rtype: ListNode
"""
dacă capul == Niciunul:

returnează capul

elif head != None ș i [Link] == None:

returnează capul

altfel:
lookup = {}
current = head
prev = cap
în timp ce current != None:
dacă [Link] este în lookup:

[Link] = [Link]
altfel:
lookup[[Link]] = Adevărat
prev = curent
curent = [Link]ător

returnează capul

24
Eliminaț i duplicatele din lista legată sortată II

Eliminarea duplicatelor din lista legată sortată

Lista II
Având o listă legată sortată, ș terge toate nodurile care au numere duplicate, lăsând
numai numere distincte din lista originală.

De exemplu, dat fiind 1->2->3->3->4->4->5, returnează 1->2->5. Dat fiind 1->1->1->2->3,

returnează 2->3.

URL:[Link]

# Defini ț ie pentru lista simplu legată

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasă Solution(object):
def stergeDuplicatele(self, cap):
"""
:tip cap: NodLista
:rtype: ListNode
"""
dacă capul == Niciunul:

întoarce capul
altfel:
dup_dict = {}
curent = cap
în timp ce current != None:
dacă [Link] este în dup_dict:
dup_dict[[Link]] += 1
altfel:
dup_dict[[Link]] = 1
curent = [Link]ător

list_values = []
curent = cap
în timp ce curent != Niciunul:

25
Elimină duplicatele din lista legată sortată II

dacă dup_dict[[Link]] > 1:

trece
altfel:
list_values.append([Link])
curent = [Link]ător
dacă list_values == []:
return None
altfel:
nod1 = ListNode(lista_valorilor[0])
cap = nodul1
pentru intrări în list_values[1:]:
new_node = ListNode(înregistrări)
[Link] = new_node
node1 = nou_nod

returnează capul

26
Schimbaț i nodurile în perechi

Schimbă nodurile în perechi

27
Elimină nodul N de la sfârș itul listei

Eliminaț i nodul N de la sfârș itul listei

Având o listă legată, elimină al n-lea nod de la sfârș itul listei ș i returnează capul listei.

De exemplu,

Lista legată dată: 1->2->3->4->5, ș i n = 2.

După ce se elimină al doilea nod de la sfârș it, lista legată devine 1->2->3->5.
Notă: n dat va fi întotdeauna valid. Încercaț i să faceț i asta într-o singură trecere.

URL:[Link]

28
Elimină nodul N de la finalul listei

# Defini ț ie pentru listă simplu legată.

# clasa ListNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None

clasa Solu ț ie(object):

def eliminaNDeLaSfâr ș it(self, cap, n):
"""
tip cap: ListNode
:tip n: int
:rtype: ListNode
"""
dacă capul == None:
returnare cap
altfel:
dummy = ListNode(0)
[Link] = head
fast = dummy
slow = dummy
pentru i în intervalul(n):

rapid = [Link]ător

în timp ce [Link] != None:

rapid = [Link]

slow = [Link]

[Link] = [Link]

întoarce [Link]

29
Copaci

Serializarea este procesul de convertire a unei structuri de date sau a unui obiect într-un
secvenț ă de biț i astfel încât să poată fi stocată într-un fiș ier sau în memoria tampon, sau transmisă
printr-o conexiune de reț ea care urmează să fie reconstruită mai târziu în aceeaș i sau în alta
mediu informatic.

Proiectaț i un algoritm pentru serializarea ș i deserializarea unui arbore binar. Nu există

restricț ie asupra modului în care ar trebui să funcț ioneze algoritmul tău de serializare/deserializare. Tu doar

trebuie să ne asigurăm că un arbore binar poate fi serializat într-un ș ir ș i acest ș ir poate

fie deserializat în structura de arbore originală.

De exemplu, puteț i serializa următorul arbore

1
/ \
2 3
/ \
4 5

ca

[1,2,3,null,null,4,5]

, la fel ca

cum serializarea unui arbore binar în LeetCode OJ

Nu trebuie să urmezi neapărat acest format, aș a că te rog să fii creativ.

găseș te diferite abordări singur.

Notă: Nu folosi variabile de membru de clasă/globali/statice pentru a stoca stări. Tu

algoritmii de serializare ș i deserializare ar trebui să fie fără stare.

URL: [Link]

# Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

30
Copaci

clasă Codec:
def __init__(self):
self.serialized_array = []
[Link] = 0

def serialize(self, root):

Codifică un arbore într-un singur ș ir.

:tip rădăcină: NodArbore

:rtype: str
"""
ajutorul_meu_de_serializare(rădăcină)
returnează self.serialized_array

def ajutor_serializare(self, radacina):

dacă rădăcina == None:

self.serialized_array.append(None)
întoarce-te
self.serialized_array.append([Link])
[Link]([Link]ânga)
[Link]([Link])

def deserializa(self, data):

Decodifică datele tale codificate într-un arbore.

:type data: str

:rtype: NodArbore
"""
dacă [Link] == len(data) sau data[[Link]] == None:
[Link] += 1
return None

root = TreeNode(data[[Link]])
[Link] += 1
[Link] = [Link](data)
[Link] = [Link](data)
returnează rădăcină

31
Păduri

# Obiectul tău Codec va fi instan ț iat ș i apelat astfel:

# codec = Codec()
# [Link]([Link](root))

32
Parcurgerea Preordonată

Parcurgerea preordine
Given a binary tree, return the preorder traversal of its nodes' values.

De exemplu: Având arbore binar {1,#,2,3}, 1 \ 2 / 3 returnează [1,2,3].

Notă: Soluț ia recursivă este trivială, ai putea să o faci iterativ?

URL:[Link]

# Defini ț ia unui nod de arbore binar.

# clasa TreeNode:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie:

# @param {TreeNode} radacina
# @return {integer[]}
def parcurgerePreordine(self, radacina):
dacă rădăcina == None:

return []
altfel:
preorderList = []
stack = []
[Link](root)
în timp ce (stiva != []) :

nod = [Link]()
[Link]([Link])
dacă [Link]:
[Link]([Link])
dacă [Link]ânga:
[Link]([Link])
returnează listaPreordine

33
Parcurgere Preordonată

34
Iterator de BST

Iterator BST
Implementaț i un iterator pentru un arbore binar de căutare (BST). Iteratorul dvs. va fi
iniț ializat cu nodul rădăcină al unui BST.

Apelarea metodei next() va returna următorul cel mai mic număr din BST.

Notă: next() ș i hasNext() ar trebui să ruleze în medie în O(1) timp ș i să folosească O(h)

memorie, unde h este înălț imea copacului.

URL: [Link]

35
Iterator BST

# Defini ț ie pentru un nod de arbore binar

# clasa NodArbore:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă BSTIterator:
# @param root, un nod rădăcină al unui arbore binar de căutare

def __init__(self, root):

[Link] = []
nod = rădăcină
în timp ce nodul != Nimic:

[Link](node)
nodul = [Link]ânga

# @return un boolean, dacă avem un următor număr mai mic

def areUrmator(self):
return len([Link]) != 0

# @return un întreg, următorul cel mai mic număr

def următorul(self):
nextNode = [Link]()
currentNode = [Link]
în timp ce currentNode != None:
[Link](currentNode)
noulNod = [Link]
return [Link]

Iteratorul dumneavoastră BST va fi apelat astfel:

# i, v = IteratoarulBST(root), []
# în timp ce [Link]ătorul(): [Link]ă([Link]ător())

36
Parcurgere Inordine

Parcurgere în ordine
Given a binary tree, return the inorder traversal of its nodes' values.

De exemplu: Având un arbore binar [1,null,2,3], 1 \ 2 / 3 returnează [1,3,2].

Notă: Soluț ia recursivă este trivială, ai putea să o faci iterativ?

URL:[Link]

# Defini ț ie pentru un nod de arbore binar.

# clasa NodArbore:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie:

# @param {TreeNode} rădăcină
# @return {integer[]}
def parcurgereInOrder(self, radacina):
dacă rădăcina == None:

return []
altfel:
result = []
stack = []
nod = rădăcină
în timp ce stiva sau nodul:

dacă nod:
[Link](nod)
nod = [Link]ânga
altfel:
nodd = [Link]()
[Link]ă([Link])
nod = [Link]
returnează rezultatul

37
Parcurgere Inordine

38
Arbore simetric

Copac simetric
Având un arbore binar, verifică dacă este un oglindă a sa (adică, simetric în jurul său)
centru).

Notă: Puncte bonus dacă poț i rezolva atât recursiv, cât ș i iterativ.

URL:[Link]

# Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie (obiect):

def esteSimetric(self, radacina):
"""
:tip rădăcină: NodArbore
:rtype: bool
"""
dacă radacina == None:
returnează Adevărat

altfel:
return [Link]([Link], [Link])

def esteOglinda(self, radacina1, radacina2):

dacă root1 == None ș i root2 == None:

returnează True
elif root1 == None sau root2 == None:
returnează Fals
altfel:
dacă [Link] == [Link]:
return [Link]([Link], [Link]) an
d [Link]([Link], [Link])
altfel:
returnează Fals

39
Copac simetric

40
Arbore binar echilibrat

Arbore Binare Echilibrat

Dat fiind un arbore binar, determinaț i dacă este echilibrat pe înălț ime.

Pentru această problemă, un arbore binar echilibrat pe înălț ime este definit ca un arbore binar în care
adâncimea celor două subarbori ai fiecărui nod nu diferă niciodată cu mai mult de 1.

URL: [Link]

41
Arbore Binariu Echilibrat

# Defini ț ie pentru un nod de copac binar.

# clasa Nodarboară:
# def __init__(self, x):
# [Link] = x
# [Link] = Niciunul
# [Link] = None

clasă Solu ț ie:

# @param {TreeNode} radacina
# @return {boolean}

def obtineInaltimea(self, radacina):

dacă rădăcina == None:

returnează 0

leftHeight = [Link]([Link])
dacă leftHeight == -1:
returnează -1

rightHeight = [Link]([Link])
dacă rightHeight == -1:
returnează -1

heightDiff = abs(leftHeight - rightHeight)

dacă heightDiff > 1:
return -1
altfel:
return max(leftHeight, rightHeight) + 1

def esteEchilibrat(self, radacina):

dacă [Link](root) == -1:

returnează Fals
altele:
returnează Adevărat

42
Valoarea cea mai apropiată din BST

Cea mai apropiată valoare din arborele binar de căutare

Având un arbore de căutare binar non-gol ș i o valoare ț intă, găseș te valoarea în

BST care este cel mai apropiat de obiectiv.

Notă: Valoarea ț intă dată este un număr în virgulă mobilă. Eș ti garantat că ai doar unul
valoarea unică din BST care este cea mai apropiată de ț intă.

URL:[Link]

43
Cea mai apropiată valoare BST

Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

class Solution(object):
def valoareaCeaMaiAproape(self, radacina, tinta):

"""
:tip rădăcină: TreeNode
:tip ț intă: float
:rtype: int
"""
min_dif = float("inf")
closestVal = None

dacă rădăcina == None:

întoarce None
altfel:
în timp ce rădăcina:

root_val = [Link]
val_dif = abs(root_val - target)
dacă val_dif < min_dif:
min_dif = val_dif
closestVal = root_val
dacă ț inta < valoarea rădăcină:

dacă [Link] != None:

root = [Link]ânga
altfel:
root = None
altfel:
dacă [Link] != None:
rădăcină = rădăcină.dreapta

altfel:
root = None
return closestVal

44
Cea mai apropiată valoare din BST

45
Parcurgere postordon

Parcurgere Postorder
Având un arbore binar, returnează parcurgerea în postordine a valorilor nodurilor sale.

De exemplu: Având un arbore binar {1,#,2,3}, 1 \ 2 / 3 returnează [3,2,1].

Notă: Soluț ia recursivă este trivială, ai putea să o faci iterativ?

URL:[Link]

46
Parcurgere Postorder

# Defini ț ia unui nod de arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie(object):

def parcurgerePostordinară(self, rădăcină):
"""
:tip rădăcină: NodArbore
:rtype: List[int]
"""
dacă rădăcina == Niciuna:

return []
altfel:
stack = []
out_stack = []
[Link](root)

în timp ce stiva != []:

current = [Link]()
out_stack.append([Link])
dacă [Link] != None:
[Link]([Link]ânga)
dacă [Link] != None:
[Link]([Link])

return out_stack[::-1]

47
Adâncimea maximă a arborelui binar

Adâncimea maximă a unui arbore binar

Dat fiind un arbore binar, găsiț i adâncimea sa maximă.

Adâncimea maximă este numărul de noduri de-a lungul celui mai lung drum din rădăcină
nod până la cel mai îndepărtat nod frunză.

URL: [Link]

Defini ț ia pentru un nod de arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie(obiect):

def adâncimeMaximă(self, rădăcină):

"""
:tip rădăcină: NodArbore
:rtype: int
"""
dacă rădăcina == None:

întoarce 0
altfel:
return max([Link]([Link]), [Link](r
[Link])) + 1

48
Inversare arbore binar

Inversează arborele binar

Inversează un arbore binar.

/ \ 2 7 / \ / \ 1 3 6 9 la 4 / \ 7 2 / \ / \ 9 6 3 1 Trivia: Această problemă a fost inspirată de aceasta

Google: 90% dintre inginerii noș tri folosesc software-ul pe care îl
am scris (Homebrew), dar nu poț i inversa un arbore binar pe o tablă albă, aș a că du-te dracului.
URL:[Link]

49
Inversare a arborelui binar

Defini ț ia unui nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def inversaArbore(self, radacina):
"""
:tip rădăcină: NodeDeArbore

:rtype: NodArbore
"""
dacă rădăcina == None:

return None
altfel:
stack = []
[Link](root)
în timp ce stiva != []:
curr_node = [Link]()
dacă curr_node.left != None sau curr_node.right !=
None:
temp = curr_node.stânga
curr_node.stanga = curr_node.dreapta
curr_node.dreapta = temp
dacă curr_node.dreapta != None:
[Link](curr_node.dreapta)
dacă curr_node.left != None:
[Link](curr_node.stanga)
returnează rădăcina

50
Acelaș i copac

Acelaș i copac

Având două copaci binari, scrieț i o funcț ie pentru a verifica dacă sunt egali sau nu.

Două arbori binari sunt consideraț i egali dacă sunt identici din punct de vedere structural ș i
nodurile au aceeaș i valoare.

URL:[Link]

# Defini ț ie pentru un nod de arbore binar.

# clasa NodArbore:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie:

# @param {TreeNode} p
# @param {TreeNode} q
# @return {boolean}
def esteAceea ș iArbore(self, p, q):
dacă p == None ș i q == None:
returnează Adevărat

altfel:
dacă p == None sau q == None:
returnează Fals
altfel:
dacă [Link] == [Link]:
return [Link]([Link], [Link]) ș i s
[Link]([Link], [Link])
altfel:
întoarce Fals

51
Cel mai mic strămoș comun al unui arbore de căutare binar

Cel mai mic strămoș comun al unui binar

Arbore de Căutare

Dat fiind un arbore de căutare binar (BST), găsiț i cel mai mic strămoș comun (LCA) al două
noduri date în BST.

Conform definiț iei LCA de pe Wikipedia: „Cel mai mic strămoș comun este
definit între două noduri v ș i w ca fiind nodul cel mai jos în T care are atât v cât ș i w
ca descendenț i (unde permitem unui nod să fie un descendent al său).

_______6______
/ \
___2__ ___8__

De exemplu, cel mai mic strămoș comun (LCA) al nodurilor 2

ș i 8 este 6. Un alt exemplu este LCA al nodurilor 2 ș i 4 este 2, deoarece un nod poate fi un
descendent al său conform definiț iei LCA.

URL:[Link]
copac

# Defini ț ie pentru un nod al unui arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def __init__(self):
self.inorder_list = []
self.postorder_list = []

def celMaiMediuComun(self, radacina, p, q):

"""

52
Cel mai mic strămoș comun al unui arbore binar de căutare

:type root: TreeNode

:type p: TreeNode
:tip q: NodArbore
:rtype: TreeNode
"""
dacă rădăcina == None:

return None
altfel:
self.inorder_traversal(rădăcină)
auto.postorder_traversal(rădăcină)
ob ț ineț i pozi ț iile lui node1 ș i node2 în ordine
parcurgerea copacului
index_node1 = self.inorder_list.index([Link])
index_node2 = self.inorder_list.index([Link])

dacă index_node1 < index_node2:

between_elems = self.inorder_list[index_node1 :
index_node2 + 1]
altfel:
between_elems = self.inorder_list[index_node2 :
index_node1 + 1]

lca_elem = self.find_elem_max_index(between_elems)

întoarce lca_elem

def găse ș te_elem_max_index(self, între_elemii):

max_index = -1
elem = None
pentru intrări în între_elem
elem_index = self.postorder_list.index(entries)
dacă elem_index > max_index:
max_index = elem_index
elem = entries
returnează elem

def traversare_in_ordine(self, nod):

dacă nod:
self.inorder_traversal([Link]ânga)

53
Cel mai mic strămoș comun al unui arbore de căutare binară

self.inorder_list.append([Link])
self.inorder_traversal([Link])

def parcurgere_postordine(self, nod):

dacă nod:
self.postorder_traversal([Link]ânga)
self.postorder_traversal([Link])
self.postorder_list.append([Link])

54
Cel mai mic strămoș comun într-o arbore binar

Cel mai mic strămoș comun într-un arbore binar

Dat fiind un arbore binar, găsiț i cel mai mic strămoș comun (LCA) al două noduri date în
copacul.

Conform definiț iei LCA de pe Wikipedia: „Cel mai mic strămoș comun este
definit între două noduri v ș i w ca fiind cel mai jos nod din T care are atât v cât ș i w
ca descendenț i (unde permitem unui nod să fie un descendent al său).

_______3______
/ \
___5__ ___1__

De exemplu, cel mai mic strămoș comun (LCA) al nodurilor 5

ș i 1 este 3. Un alt exemplu este LCA al nodurilor 5 ș i 4 este 5, deoarece un nod poate fi un
descendent al său conform definiț iei LCA.

URL:[Link]

55
Cel mai mic strămoș comun într-un arbore binar

Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie(object):

def celMaiMicStramosComun(self, radacina, p, q):

"""
:tip rădăcină: TreeNode
:tip p: NodArbore
:tip q: NodArbore
:rtype: NodArbore
"""
dacă rădăcina == None:

întoarce None

dacă root == p sau root == q:

returnează rădăcina

stânga = [Link](rădăcină.stânga, p, q)
dreapta = [Link]([Link], p, q)

dacă stânga != Niciuna ș i dreapta != Niciuna:

returnează rădăcina

dacă left == None:

întoarce-te la dreapta

altfel:
întoarce la stânga

56
Arbori de căutare binară unici

Arbori de căutare binare unici

Dat n, câte BST-uri structurale unice (arbori de căutare binară) stochează
valori 1...n?

De exemplu, având n = 3, există un total de 5 BST-uri unice.

13321\///\\321132//\\2123

URL: [Link]

57
Arbori de căutare binară unici

clasa Solu ț ie(object):

def numTrees(self, n):

"""
:tip n: int
:rtype: int
"""
solutions = [-1]*(n)
return [Link](n, solutions)

def numUniqueBST(self, n, solu ț ii):

dacă n < 0:
returnează 0

dacă n == 0 sau n == 1:
returnează 1

possibilities = 0

pentru i în range(0, n):

dacă solu ț ii[i] == -1:
solu ț ii[i] = [Link](i, solu ț ii)
dacă solu ț ii[n-1-i] == -1:
solu ț ii[n-1-i] = [Link](n-1-i, solu
tions)
posibilită ț i += solu ț ii[i]*soluț ii[n-1-i]
returna ț i posibilită ț ile

58
Arbori de căutare binară unici II

Copaci binari de căutare unici II

Dat fiind un număr întreg n, generează toate BST-uri (arbori binari de căutare) unice din punct de vedere structural

care stochează valori 1...n.

De exemplu, având n = 3, programul tău ar trebui să returneze toate cele 5 BST-uri unice arătate.

mai jos.

13321\///\\321132//\\2123

URL: [Link]

59
Arbori binari de căutare unici II

# Defini ț ia pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def generaCopaci(self, n):
"""
:tip n: int
rtype: List[TreeNode]
"""
dacă n == 0:
return []
altfel:
return self.tree_constructor(1, n)

def constructor_arbre(self, m, n):

results = []
dacă m > n:
[Link](None)
returna ț i rezultatele

pentru i în intervalul(m, n+1):

l = self.tree_constructor(m, i-1)
r = self.tree_constructor(i+1, n)
pentru arbori_stânga în l:
pentru copaci_drepti în r:
curr_node = TreeNode(i)
curr_node.left = left_trees
curr_node.dreapta = arbori_dreapta
[Link](curr_node)

returna ț i rezultatele

60
Arbori binari de căutare unici II

61
Suma Cărării

Suma Căii
Dat fiind un arbore binar ș i o sumă, determină dacă arborele are o cale de la rădăcină la frunză astfel încât

adică adunarea tuturor valorilor de-a lungul căii este egală cu suma dată.

De exemplu: Având următoarea arbore binar ș i suma = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7

2 1 returnează adevărat, deoarece există o cale de la rădăcină la frunză 5->4->11->2 ale cărei sumă este 22.

URL: [Link]

# Defini ț ie pentru un nod al unui arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

class Solution(object):

def areCaleSuma(self, radacina, suma):

"""
:tip rădăcină: NodArbore
:tip suma: int
:rtype: bool
"""
dacă rădăcina == Niciuna:

returnează Fals
altfel:
curent = rădăcină
s = []
[Link](current)
[Link]([Link])

în timp ce s != []:

pathsum = [Link]()
current = [Link]()

dacă nu există [Link] ș i nu există [Link]:

62
Suma Cărț ii

dacă pathsum == sum:

returnează Adevărat

dacă [Link]:
rightpathsum = pathsum + [Link]
[Link]([Link])
[Link](rightpathsum)

dacă [Link]:
leftpathsum = pathsum + [Link]
[Link]([Link])
[Link](suma_cale_stanga)

returnează Fals

63
Suma maximă pe calea unui arbore binar

Suma Maximă a Cărț ii Path în Arborele Binari

Dată fiind oarbă binară, găseș te suma maximă a cestei căi.

Pentru această problemă, un traseu este definit ca orice secvenț ă de noduri de la un anumit început

nod către orice nod în copac de-a lungul conexiunilor părinte-copil. Calea nu
nu este nevoie să treci prin rădăcină.

De exemplu: Având următoarea arbore binar,

1
/ \
2 3

Întoarce 6

URL:[Link]

64
Suma maximă a căii din arborele binar

Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def __init__(self):
[Link] = -[Link] - 1

# @param {TreeNode} radacina

# @return {integer}
def sumaCaleaMaxima(self, radacina):

[Link](root)
returnează [Link]

def gasesteMax(self,radacina):
dacă rădăcina == None:

întoarce 0
stânga = [Link]([Link]ânga)
dreapta = [Link](rădă[Link])
[Link] = max([Link] + left + right, [Link])
ret = [Link] + max(left,right)
dacă ret < 0:
returnează 0

altfel:
returna ț i ret

65
Parcurgerea unui Arbore Binara în Ordine pe Niveluri

Traversarea pe niveluri a unui arbore binar

Dat fiind un arbore binar, returnaț i parcurgerea pe niveluri a valorilor nodurilor sale. (adică, de la
de la stânga la dreapta, nivel cu nivel.

De exemplu: Având arbore binar [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 returnează-l

parcurgere pe niveluri ca: [[3], [9,20], [15,7]]

URL:[Link]

66
Parcurgerea unui arbore binar în ordinea nivelurilor

# Defini ț ia pentru un nod al unui arbore binar.

# clasa TreeNode:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

import Coada
clasa Solu ț ie:
# @param {TreeNode} radacina
# @return {integer[][]}
def parcurgereNivel(self, radacina):
dacă rădăcina == None:

return []
altfel:
q = [Link]()
[Link](root)
[Link]("#")
levelOrderTraversal = []
level = []
în timp ce [Link]() == Fals:
nod = [Link]()
dacă nodul == "#":
dacă [Link]() == Fals:
[Link]("#")
[Link](nivel)
level = []
altfel:
[Link]([Link])
dacă [Link]ânga:
[Link]([Link])
dacă [Link]:
[Link]([Link])

returna ț i parcurgerea nivelului

67
Validare arbore de căutare binar

Validare Arbore de Căutare Binare

Dat fiind un arbore binar, determinaț i dacă este un arbore de căutare binar valid (BST).

Presupuneț i că un BST este definit astfel:

Subarborele stâng al unui nod conț ine doar noduri cu chei mai mici decât cheia nodului.
Subarborele drept al unui nod conț ine doar noduri cu chei mai mari decât cheia nodului.
cheie. Atât subarborii stângi cât ș i cei drepț i trebuie să fie, de asemenea, arbori de căutare binară. Exemplul 1:

2 / \ 1 3 Arbore binar [2,1,3], returnează adevărat. Exemplul 2: 1 / \ 2 3 Arbore binar [1,2,3],

returnează fals.

URL:[Link]

68
Validaț i un arbore de căutare binar

# Definirea pentru un nod de arbore binar.

# clasa TreeNode:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None
import sys
clasă Solu ț ie:
def __init__(self):
[Link] = -[Link]-1
# @param {TreeNode} root
# @return {boolean}
def esteValidaBST(self, radacina):
dacă rădăcina == None:
returnează Adevărat

dacă [Link]([Link]) == Fals:

returnează Fals

data = [Link]
dacă datele <= [Link]:
returnează Fals

[Link] = date

dacă [Link]([Link]) == Fals:

întoarce Fals

returna ț i True

69
Adâncimea minimă a unui arbore binar

Adâncimea minimă a unui arbore binar

Dată fiind o arbore binar, găseș te-i adâncimea minimă.

Adâncimea minimă este numărul de noduri de-a lungul celui mai scurt drum de la rădăcină
nod până la cel mai apropiat nod frunză.

URL:[Link]

70
Adâncimea minimă a unui arbore binar

import sys
# Defini ț ie pentru un nod de arbore binar.
# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def adâncimeMinimă(self, rădăcină):

"""
:tip rădăcină: NodArbore
:rtype: int
"""
dacă rădăcina == Nimic:

return 0

dacă [Link] == None ș i [Link] == None:

întoarce 1

dacă [Link] != None:

stanga = [Link](rădăcină.stanga)

altfel:
left = [Link]

dacă [Link] != None:

dreapta = [Link]([Link])
altfel:
right = [Link]

return 1 + min(stanga, dreapta)

71
Transformaț i un array sortat într-un arbore de căutare binar

Conversia unui array sortat în arbore de căutare binar

Copac
Given an array where elements are sorted in ascending order, convert it to a
BST echilibrat în înălț ime.

URL: [Link]

72
Conversie a unui tablou sortat într-un arbore binar de căutare

# Defini ț ia pentru un nod de arbore binar.

# clasa NodArbore(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie (obiect):

def sortedArrayToBST(self, nums):
"""
:tip nums: Lista[int]
:rtype: TreeNode
"""
dacă nums == []:
return None
elif len(nums) == 1:
return TreeNode(nums[0])
altfel:
start = 0
end = len(nums) - 1
return self.to_bst(nums, start, end)

def la_bst(self, arr, start, end):

dacă len(arr) == 0 sau start > end:
return None
altfel:
mid = (start + end) // 2
nod = TreeNode(arr[mid])
[Link] = self.to_bst(arr, start, mid - 1)
[Link] = self.to_bst(arr, mid + 1, end)
returna ț i nodul

73
Transformaț i arborele binar într-o listă legată

Aplatizarea unui arbore binar într-o listă legată

Dat fiind un arbore binar, aplatizează-l într-o listă legată la locul său.

De exemplu, dat

1
/ \
2 5
/ \ \
3 4 6

Arborele aplatizat ar trebui să arate astfel: 1 \ 2 \ 3 \ 4 \ 5 \ 6

URL:[Link]

74
Aplatizarea unui arbore binar într-o listă legată

# Defini ț ie pentru un nod al unui arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie (obiect):

def aplatizare(self, radacina):

"""
:tip rădăcină: NodArbore
:rtype: void Nu returna ț i nimic, modifica ț i rădăcina în loc
e în schimb.
"""
dacă rădăcina == None:
întoarce rădăcina

stack = []
current = root

în timp ce((stiva != []) sau (curent != None)):

dacă [Link] != None:

[Link]([Link])

dacă [Link] nu este None:

[Link] = [Link]
[Link] = None
altfel:
dacă stiva != []:
temp = [Link]()
[Link] = temp

curent = [Link]

75
Construieș te un arbore binar din traversarea in ordine ș i preordine

Construiț i un arbore binar din ordinea în care sunt prezentate elementele ș i

Traversare Preordonată
Având parcursul preorder ș i inorder al unui arbore, construieș te arborele binar.

Notă: Puteț i presupune că duplicatele nu există în arbore.

URL:[Link]
traversarea-in-ordine/

# Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def construie ș teArbore(self, preorder, inorder):
"""
:tip preorder: List[int]
:tip inorder: List[int]
:rtype: NodArbore
"""
dacă len(inorder) == 1:
return TreeNode(inorder[0])
return self.create_tree(inorder, 0, len(inorder) - 1, pr
eorder, 0, len(preorder) - 1)

def search_divindex(self, inorder, low_inorder, high_inorder

, val):
pentru i în intervalul(low_inorder, high_inorder+1):
dacă inorder[i] == val:
returnează i
returnează -1

def crea ț i_arbore(self, inorder, low_inorder, high_inorder, pr

eorder, low_preorder, high_preorder):

76
Construieș te un arbore binar din parcurgerea în ordine ș i parcurgerea preordine

dacă (low_preorder > high_preorder) sau (low_inorder > high

_inordine):
returnează Nimic

root = TreeNode(preorder[low_preorder])
div_index = self.search_divindex(inorder, low_inorder, h
igh_inorder, [Link]
size_left_subtree = div_index - low_inorder
size_right_subtree = high_inorder - div_index

[Link] = self.create_tree(inorder, div_index + 1, hi

gh_inorder, preorder,
low_preorder + 1 + size_le
ft_subtree,
low_preorder + size_left_s
subarbore + dimensiunea_subarborelui_drept

[Link] = self.create_tree(inorder, low_inorder, div_i

index - 1, preordonare,
low_preorder + 1, low_preor
der + size_left_subtree)

întoarce rădăcina

77
Cărț i ale unui arbore binar

Cărț ile căii binare

Având un arbore binar, returnaț i toate căile de la rădăcină la frunze.

De exemplu, având următorul arbore binar:

Toate căile de la rădăcină la frunză sunt:

["1->2->5","1->3"]

URL: [Link]

# clasa NodArbore:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie:

# @param {TreeNode} root
# @return {string[]}
def căiArboreBinare(self, rădăcină):
dacă rădăcina == None:

return []
altfel:
paths = []
current = root
s = []
[Link](curent)
[Link](str([Link]))

în timp ce s != []:

#pathsum = [Link]()
calea = [Link]()
current = [Link]()

dacă nu există [Link] ș i nu există [Link]:

[Link](path)

78
Cărț ile binare ale copacului

dacă [Link]:
rightstr = calea + "->" + str([Link].v
al)
[Link]([Link])
[Link](rightstr)

dacă [Link]:
leftstr = cale + "->" + str([Link]
)
[Link]([Link]ânga)
[Link](leftstr)
returna ț i căile

79
Recuperaț i Arborele Binare de Căutare

Recuperaț i arborele de căutare binar

Două elemente ale unui arbore de căutare binar (BST) au fost schimbate din greș eală.

Recuperaț i copacul fără a-i schimba structura.

Notă: O soluț ie care foloseș te O(n) spaț iu este destul de simplă. Ai putea concepe o
soluț ie cu spaț iu constant?

URL: [Link]

80
Recuperaț i arborele de căutare binar

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def __init__(self):
self.__prev = None
self.__node1 = None
self.__node2 = None

def recuperareArbore(self, radacina):

"""
tip rădăcină: NodArbore
:rtype: void Nu returna ț i nimic, modifica ț i rădăcina în loc
în loc.
"""
[Link](rădăcină)
temp = self.__node1.val
self.__node1.val = self.__node2.val
self.__node2.val = temp

def recoverTreeHelp(self, radacina):

dacă rădăcina == None:

return None

[Link]([Link]ânga)
dacă self.__prev != None:
dacă self.__prev.val > [Link]:
dacă self.__node1 == Niciunul:
self.__nod1 = self.__prev
self.__node2 = root
self.__prev = root
[Link]([Link])

81
Suma Cărării II

Calea suma II
Dat un arbore binar ș i o sumă, găsiț i toate căile din rădăcină până la frunză pentru care suma fiecărei căi

egal suma dată.

For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \
[ [5,4,11,2], [5,8,4,5] ]

URL:[Link]

# Defini ț ie pentru un nod al unui arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def sumaCalea(self, radacina, suma):
"""
:tip rădăcină: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
dacă rădăcină == None:

return []
altfel:
stack = []
paths = []

curent = rădăcină
[Link](current)
[Link]([[Link]])
[Link]([Link])
while stack != []:
pathsum = [Link]()
cale = [Link]()
curr = [Link]()

82
Suma Cărării II

dacă [Link] == None ș i [Link] == None:

dacă pathsum == sum:
[Link](path)
dacă [Link]:
rightstr = cale + [[Link]]
rightsum = pathsum + [Link]
[Link]([Link])
[Link](rightstr)
[Link](dreaptaSuma)
dacă [Link]:
leftstr = path + [[Link]]
leftsum = pathsum + [Link]
[Link]([Link])
[Link](leftstr)
[Link](leftsum)
returna ț i căile

83
Traversare pe niveluri binare II

Parcurgerea pe niveluri binare II

Dat fiind un arbore binar, returnează parcurgerea ordinii pe niveluri de jos în sus a valorilor nodurilor sale.

(adică, de la stânga la dreapta, nivel cu nivel de la frunză la rădăcină).

De exemplu: Având arborele binar [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 returnează-l

parcurgerea nivel cu nivel de jos în sus ca: [ [15,7], [9,20], [3] ]

URL:[Link]

Defini ț ia unui nod de arbore binar.

# clasa TreeNode:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

importa Coada
clasa Solu ț ie:
# @param {TreeNode} root
# @return {integer[][]}
def nivelOrdineJos(self, radacina):
dacă rădăcina == Niciunul:

return []
altfel:
q = [Link]()
[Link](root)
[Link]("#")
levelOrderTraversal = []
level = []
stack = []

în timp ce q.este_gol() == Fals:

nod = [Link]()
dacă nodul == "#":
dacă [Link]() == Fals:
[Link]("#")
[Link](nivel)

84
Parcurgerea nivelurilor binare II

level = []
altfel:
[Link]([Link])
dacă [Link]ânga:

[Link]([Link]âng)
dacă [Link]:
[Link]([Link])

cât timp stiva:

[Link]([Link]())

returna ț i traversarea pe nivel

85
Cel de-al K-lea cel mai mic element într-un BST

Cel de-al K-lea cel mai mic element într-un BST

Given a binary search tree, write a function kthSmallest to find the kth smallest
element în el.

Notă: Poț i presupune că k este întotdeauna valid, 1 ≤ k ≤ numărul total de elemente ale BST.

Urmaț i: Ce se întâmplă dacă BST-ul este modificat (operaț iuni de inserare/ș tergere) frecvent ș i dvs.

Trebuie să găseș ti frecvent al k-lea cel mai mic? Cum ai optimiza al k-lea cel mai mic?
rutina?

Indiciu:

Încercaț i să utilizaț i proprietatea unui BST. Ce s-ar întâmpla dacă aț i putea modifica nodul BST-ului?

structură? Complexitatea optimă a timpului de execuț ie este O(înălț imea BST).

URL:[Link]

86
Cel de-al K-lea cel mai mic element dintr-un BST

Defini ț ie pentru un nod de arbore binar.

# clasa ArboreNod (obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie(object):

def kthSmallest(self, radacina, k):
"""
:tip rădăcină: TreeNode
:tip k: int
:rtype: int
"""
dacă rădăcina == None:

return None
altfel:
stack = []
nod = rădăcină
count = 0
în timp ce stiva != [] sau nod != None:
dacă nod != Niciunul:
[Link](node)
nod = [Link]ânga
altfel:
inorder_node = [Link]()
count += 1
daca count == k:
return inorder_node.val
nod = inorder_node.dreapta
return None

87
Al k-lea cel mai mic element dintr-un BST

clasă Solu ț ie(object):

def kthSmallest(self, radacina, k):
"""
:tip rădăcină: NodArbore
:tip k: int
:rtype: int
"""
stack = []*k
în timp ce Adevărat:

în timp ce rădăcină:

[Link](root)
radacina = [Link]

root = [Link]()
dacă k == 1:
return [Link]
altfel:
k -= 1
root = [Link]

88
Construiț i un arbore binar din traversarea înordine ș i postordine

Construiț i un arbore binar din ordre ș i

Traversarea în postordonare

Dat fiind parcurgerea în ordine ș i parcurgerea în postordine a unui arbore, construieș te arborele binar.

Notă: Puteț i presupune că duplicatele nu există în arbore.

Defini ț ie pentru un nod de arbore binar.

# clasa NodArbore(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def construiesteArbore(self, inorder, postorder):
"""
:tip inorder: List[int]
:tip postordine: List[int]
:rtype: TreeNode
"""
return self.create_tree(inorder, 0, len(inorder) -1 , po
storder, 0, len(postorder) - 1)

def cauta_divindex(self, inorder, low_inorder, high_inorder

, val):
pentru i în intervalul (low_inorder, high_inorder + 1):

dacă inorder[i] == val:

returnează i

întoarce -1

def crea_arbore(self, inord, low_inord, high_inord, po

storder, low_postorder, high_postorder):
dacă (low_inorder > high_inorder) sau (low_postorder > high
_postorder):
return None

89
Construiț i un arbore binar din parcurgerea în ordine ș i parcurgerea postordine

root = TreeNode(postorder[high_postorder])

div_index = self.search_divindex(inorder, low_inorder, h

igh_inorder, [Link]

size_left_subtree = div_index - low_inorder

size_right_subtree = high_inorder - div_index

[Link] = self.create_tree(inorder, div_index + 1, hi

gh_inorder, postorder,
high_postorder - size_righ
t_subarbore, postordine_inalt - 1)

[Link] = self.create_tree(inorder, low_inorder, div_i

index - 1,
postordine
high_postorder - size_right
_subtree - size_left_subtree,
high_postorder - size_right
_subtree - 1)

returnează rădăcina

90
Vedere din partea dreaptă a arborelui binar

Vedere din dreapta a arborelui binar

Având un arbore binar, imaginează-ț i că stai pe partea dreaptă a acestuia, returnează

valorile nodurilor pe care le poț i vedea ordonate de sus în jos.

De exemplu: Având următorul arbore binar, 1 <--- / \ 2 3 <--- \ \ 5 4 <---Tu

ar trebui să returneze [1, 3, 4].

URL: [Link]

91
Vederea din dreapta a arborelui binar

# Defini ț ie pentru un nod de arbore binar.

# clasa NodArbore:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

importa coada
clasa Solu ț ie:
# @param {TreeNode} rădăcină
# @return {integer[]}
def vedereParteaDreapta(self, radacina):
dacă rădăcina == None:

return []
altfel:
q = [Link]()
[Link](root)
[Link]("#")
rightSideView = []
level = []
în timp ce [Link]() == Fals:
nod = [Link]()
dacă nodul == "#":
dacă [Link]() == Fals:
[Link]("#")
[Link](level[-1])
level = []
altfel:
[Link]([Link])
dacă [Link]ânga != None:
[Link]([Link])
dacă [Link] != None:
[Link]([Link])
returna ț i viziunea din partea dreaptă

92
Sumă Rădăcină la Numerele Frunze

Suma numerelor de la rădăcină la frunze

Având un arbore binar care conț ine cifre de la 0 la 9 numai, fiecare cale de la rădăcină la frunză ar putea

reprezintă un număr.

Un exemplu este calea rădăcină-frunză 1->2->3, care reprezintă numărul 123.

Găsiț i suma totală a tuturor numerelor de la rădăcină la frunză.

De exemplu,

/ \ 2 3 Calea de la rădăcină la frunză 1->2 reprezintă numărul 12. Calea de la rădăcină la frunză
1->3 reprezintă cifra 13.

Returnează suma = 12 + 13 = 25.

93
Suma numerelor de la rădăcină la frunze

# Defini ț ie pentru un nod de arbore binar.

# clasa NodArbore(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie(object):

def sumaNumere(self, radacina):
"""
:type root: TreeNode
:rtype: int
"""
dacă root == None:
return 0
altfel:
stack = []
paths = []
[Link](rădăcină)
[Link](str([Link]))
în timp ce stiva != []:
path = [Link]()
current = [Link]()
dacă [Link] == None ș i [Link] == None
e:
[Link](int(path))
dacă [Link]:
rightstr = path + str([Link])
[Link]([Link])
[Link](rightstr)
dacă [Link]:
leftstr = path + str([Link])
[Link]([Link]ânga)
[Link](leftstr)
return sum(paths)

94
Parcurgerea în ordinea zigzag a nivelurilor unui arbore binar

Traversarea în ordinea zigzag a nivelurilor copacului binar

Dat fiind un arbore binar, returnaț i traversarea în ordine zigzag a valorilor nodurilor sale. (adică,
de la stânga la dreapta, apoi de la dreapta la stânga pentru nivelul următor ș i alternează între ele.

For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its

zigzag level order traversal as: [ [3], [20,9], [15,7] ]

Defini ț ia pentru un nod de arbore binar.

# clasa TreeNode:
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

importa Coada
clasa Solu ț ie:
# @param {TreeNode} rădăcină
# @return {integer[][]}
def zigzagLevelOrder(self, radacina):
dacă rădăcina == None:

return []
altfel:
q = [Link]()
[Link](root)
[Link]("#")
levelOrderTraversal = []
level = []
levelNo = 0
în timp ce q.este_gol() == Fals:

nod = [Link]()

dacă nodul == "#":

dacă q.este_gol() == Fals:
[Link]("#")

if levelNo == 0 or levelNo % 2 == 0:
[Link](level)

95
Traversarea pe niveluri Zigal a Arborelui Binari

altfel:
[Link](level[::-1])
level = []
nivelNo += 1
altfel:
[Link]([Link])
dacă [Link]ânga:
[Link]([Link])
dacă [Link]:

[Link]([Link])

return nivelOrdineTraversare

96
Jaf de Case III

Spărgătorul de case III

Hoț ul ș i-a găsit din nou un nou loc pentru jafurile sale. Există doar unul
intrarea în această zonă, numită „rădăcină.” Pe lângă rădăcină, fiecare casă are una ș i
doar o casă cu un singur părinte. După un tur, hoț ul inteligent a realizat că "toate casele din această

locul formează un arbore binar". Va contacta automat poliț ia dacă două direct
casele interconectate au fost sparte în aceeaș i noapte.

Stabileș te suma maximă de bani pe care hoț ul o poate fura în această noapte fără
alertarea poliț iei.

Exemplul 1: 3 / \ 2 3 \ \ 3 1 Suma maximă de bani pe care hoț ul o poate fura = 3 + 3 +

1 = 7. Exemplu 2: 3 / \ 4 5 / \ \ 1 3 1 Suma maximă de bani pe care hoț ul o poate fura
= 4 + 5 = 9.

URL: [Link]

97
Furtiș ag III

Defini ț ia pentru un nod al unui arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def fura(self, radacina):
"""
:type root: TreeNode
:rtype: int
"""
dacă rădăcina == None:
returnează 0

altfel:
result = self.rob_max(root)
returnează max(result[0], result[1])

def fură_max(self, rădăcină):

dacă rădăcina == None:

return [0, 0]
altfel:
left_res = self.rob_max([Link])
right_res = self.rob_max([Link])
result = [0]*2
result[0] = [Link] + left_res[1] + right_res[1]
result[1] = max(left_res[0], left_res[1]) + max(righ
t_res[0], right_res[1])
întoarce rezultatul

98
Succesorul Inorder în BST

Succesorul în ordine în BST

Dând un arbore binar de căutare ș i un nod în el, găsiț i succesorul în ordine al acestuia.
nod în BST.

Notă: Dacă nodul dat nu are succesor în ordine în arbore, returnaț i null.

URL:[Link]

99
Succesorul în ordine în BST

# Defini ț ie pentru un nod al unui arbore binar.

# clasa NodArbore(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasa Solu ț ie(object):

def succesorInorder(self, radacina, p):
"""
:tip rădăcină: NodArbore
:tip p: NodArbore
:rtype: NodArbore
"""
successor = None

în timp ce root != None ș i [Link] != [Link]:

dacă [Link] > [Link]:
successor = root
root = [Link]
altfel:
root = [Link]

dacă rădăcina == None:

return None

dacă [Link] == None:

returna succesorul

rădăcină = rădăcină.dreapta

între timp, [Link] != None:

root = [Link]ânga
întoarce rădăcina

100
Secvenț a consecutivă cea mai lungă a copacului binar

Cel mai lung consecutiv din arborele binar

Secvenț ă
D given un arbore binar, găseș te lungimea celei mai lungi secvenț e consecutive de cale.

Calea se referă la orice succesiune de noduri de la un nod de început la orice nod în

rama de-a lungul conexiunilor părinte-copil. Cea mai lungă cale consecutivă trebuie să
să fie de la părinte la copil (nu poate fi invers).

De exemplu, 1 \ 3 / \ 2 4 \ 5 Cea mai lungă secvenț ă consecutivă este 3-4-5, aș a că

returnează 3. 2 \ 3 / 2
/ 1 Cea mai lungă secvenț ă consecutivă este 2-3, nu 3-2-1, aș a că se returnează 2.

# Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

din Queue import Queue

importa ț i sys
clasa Solu ț ie(object):
def ceaMaiLungaConsecutiva(self, radacina):
"""
:tip rădăcină: NodArbore
:rtype: int
"""
dacă rădăcina == None:
returnează 0
dacă [Link] == None ș i [Link]ânga == None:
returnează 1

altfel:
max_size = 1
size_q = Queue()
node_q = Queue()
node_q.put(root)

101
Secvenț ă consecutivă cea mai lungă în arbore binar

size_q.put(1)
în timp ce node_q.empty() == Fals:
curr_node = node_q.get()
curr_size = size_q.get()

dacă curr_node.stânga:
left_size = curr_size
dacă curr_node.val == curr_node.[Link] - 1:
left_size += 1
max_size = max(max_size, left_size)
altfel:
left_size = 1

node_q.put(curr_node.stanga)
size_q.put(left_size)

dacă curr_node.dreapta:
right_size = curr_size
dacă curr_node.val == curr_node.[Link] - 1:
right_size += 1
max_size = max(max_size, right_size)
altfel:
right_size = 1

node_q.put(curr_node.dreapta)
size_q.put(talia_dreaptă)

returna ț i max_size

102
Verificarea secvenț ei preordine în arborele binar de căutare

Verificaț i secvenț a de precomandă în căutarea binară

Copac
Dat fiind un tablou de numere, verifică dacă este parcursul corect în preordine
secvenț a unui arbore de căutare binar.

Puteț i presupune că fiecare număr din secvenț ă este unic.

Urmărire: Ai putea să o faci folosind doar complexitate spaț ială constantă?

URL:[Link]
copac

importa sistem
clasa Solu ț ie(object):
def verificaPreordine(self, preordine):
"""
:tip preordine: List[int]
:rtype: bool
"""
stack = []
root = -[Link]-1

pentru intrări în preordine:

dacă intrările < rădăcină:

returnează Fals

în timp ce stiva != [] ș i stiva[-1] < intrări:

root = [Link]()

[Link](entries)

întoarce Adevărat

103
Verificarea secvenț ei de preordonare în arborele binar de căutare

104
Arbore binar cu susul în jos

Copacul Binarn Cu Susul În Jos

Având un arbore binar în care toate nodurile din dreapta sunt fie noduri frunză cu un frate (o
nodule stâng care Împarte acelaș i nod părinte) sau gol, întoarce-l cu susul în jos ș i întoarce-l
într-un copac în care nodurile originale din dreapta s-au transformat în noduri frunză din stânga. Returnează
rădăcină nouă.

De exemplu: Dat un arbore binar {1,2,3,4,5}, 1 / \ 2 3 / \ 4 5 returnează rădăcina

binary tree [4,5,2,#,#,3,1]. 4 / \ 5 2 / \ 3 1

Defini ț ie pentru un nod de arbore binar.

# clasa TreeNode(obiect):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie (obiect):

def arboreBinariInversat(self, radacina):
"""
:tip rădăcină: TreeNode
:rtype: NodArbore
"""
p = rădăcină

parent = None
parent_right = None

în timp ce p:

left = [Link]
[Link] = dreapta_parintelui

parent_right = [Link]
[Link] = părinte
parent = p
p = stânga

returnează părintele

105
Arbore Binar Cu Susul în Jos

106
Numără Subarborii cu Valori Unice

Numără Subarborii Univalenț i

Dat fiind un arbore binar, număraț i numărul de subarbori uni-valoare.

Un subarbore de valoare unică înseamnă că toate nodurile subarborelui au aceeaș i valoare.

De exemplu: Având un arbore binar, 5 / \ 1 5 / \ \ 5 5 5 returnează 4.

URL:[Link]

107
Numără subarborii univalenț i

# Defini ț ia unui nod dintr-un arbore binar.

# clasa TreeNode(object):
# def __init__(self, x):
# [Link] = x
# [Link] = None
# [Link] = None

clasă Solu ț ie (obiect):

def __init__(self):
self.__count = 0

def numaraSubarboriUnivalenti(self, radacina):

"""
:tip rădăcină: NodArbore
:rtype: int
"""
self.count_univalue_subtrees(root)
return self.__count

def numara_subarbori_univalu(self, radacina):

dacă rădăcina == None:
returnează Adevărat

dacă [Link] == None ș i [Link] == None:

self.__count += 1
returnează Adevărat

stângă = self.count_univalue_subtrees([Link])
dreapta = self.count_univalue_subtrees([Link])

dacă (stânga ș i dreapta) ș i (rădă[Link]ânga == None sau rădă[Link]ânga.

val == [Link]) ș i ([Link] == None sau [Link] == ro

[Link]):
self.__count += 1
returnează Adevărat

altfel:
returnează False

108
Numărul de componente conectate într-un graf neorientat

Numărul de componente conectate într-un

Graf neorientat
Dat n noduri etichetate de la 0 la n - 1 ș i o listă de muchii neorientate (fiecare muchie este
o pereche de noduri), scrieț i o funcț ie pentru a găsi numărul de componente conectate în
o graf neorientat.

URL: [Link]
grafic-neorientat/

importă sistem
din coadă import Coadă

clasă Vârf:
def __init__(self, nod):
[Link] = nod
[Link] = {}
Seta ț i distan ț a la infinit pentru toate nodurile
[Link] = [Link]
Marca ț i toate nodurile ca nevizitate

[Link] = False
Marchează toate nodurile cu culoarea albă
[Link] = 'white'
Precursor
[Link] = None

def adaugaVecte(self, vecin, greutate=0):

[Link][neighbor] = weight

def ob ț ineConexiuni(self):
return [Link]()

def getVertexID(self):
return [Link]

def obtineGreutatea(self, vecin):

returnează [Link][vecin]

109
Numărul de componente conectate într-un graf neorientat

def setDistance(self, dist):

[Link] = dist

def obtineDistanta(self):
returnează [Link]

def setColor(self, culoare):

[Link] = color

def getCuloare(self):
returnează [Link]

def setPrevious(self, prev):

[Link] = prev

def setVizitat(self):
[Link] = True

def __str__(self):
return str([Link]) + ' adiacente: ' + str([[Link] pentru x în
[Link]])

clasa Graf:
def __init__(self):
[Link] = {}
[Link] = 0

def __iter__(self):
return iter([Link]())

def adaugaVertex(self, nod):

[Link] = [Link] + 1
newVertex = Vertex(node)
[Link][node] = newVertex
return newVertex

def obtineVarf(self, n):

dacă n în [Link]:
returnează [Link][n]

110
Numărul de componente conectate într-un graf neorientat

altfel:
întoarce Niciunul

def adaugaMuchie(self, din, la, cost=0):

dacă frm nu este în [Link]:
[Link](frm)
dacă nu se află în [Link]:
[Link](to)

[Link][frm].addNeighbor([Link]
[to], cost)
[Link][to].addNeighbor([Link][
frm], cost)

def obtineVarfuri(self):
return [Link]()

def setPrevious(self, current):

[Link] = current

def getPrevious(self, current):

returnează [Link]

clasa Solu ț ie(object):

def număraComponente(self, n, muchii):
"""
:tip n: int
:tip margin: Lista[List[int]]
:rtype: int
"""
dacă n == 1 ș i muchiile == []:
returnează 1

altfel:
G = Grafic()
pentru intrări în margini:
[Link](entrări[0], intrări[1], 1)
count = 0
pentru vârtex în G:
dacă [Link]() == "alb":
count += 1

111
Numărul de componente conectate într-un graf neorientat

[Link](vârf)

returnare număr

def bfs(self, varf):

[Link]("gri")
q = Coada()
[Link](vertex)
în timp ce [Link]() == Fals:
curr_node = [Link]()
pentru nbr în curr_node.getConnections():
dacă [Link]() == "alb":
[Link]("gri")
[Link](nr)
curr_node.setColor("negru")

dacă __name__ == '__main__':

n = 5
edges1 = [[0, 1], [1, 2], [3, 4]]
edges2 = [[0, 1], [1, 2], [2, 3], [3, 4]]

soln = Solu ț ie()

print([Link](n, edges1))
print([Link](n, edges2))

112
Programul cursului

Course Schedule
Există un număr total de n cursuri pe care trebuie să le urmezi, etichetate de la 0 la n - 1.

Unele cursuri pot avea cerinț e prealabile, de exemplu, pentru a urma cursul 0 trebuie să
începe mai întâi cursul 1, care este exprimat ca o pereche: [0,1]

Având în vedere numărul total de cursuri ș i o listă de perechi de cerinț e preliminare, este posibil pentru
tu să finalizezi toate cursurile?

For example:

Sunt un total de 2 cursuri de urmat. Pentru a urma cursul 1, ar trebui să ai

am terminat cursul 0. Aș adar, este posibil.

Există un total de 2 cursuri de luat. Pentru a lua cursul 1, ar trebui să

am terminat cursul 0, iar pentru a lua cursul 0 ar trebui să fi terminat ș i cursul
Deci, este imposibil.

Notă: Cerinț ele preliminare de intrare sunt un graf reprezentat printr-o listă de muchii, nu
matrice de adiacenț ă. Citeș te mai multe despre cum este reprezentat un graf.

URL: [Link]

clasa Vertex:

def __init__(self, cheie):

[Link] = key
[Link] = {}
[Link] = 0
[Link] = 0
[Link] = None
self.visit_time = 0
self.finish_time = 0
[Link] = "white"

def adauga_vecin(self, nbr, greutate=0):

[Link][nbr] = weight

113
Programul cursului

def obtine_vecini(self):
return [Link]()

def obtine_id(self):
return [Link]

def get_weight(self, nbr):

returnează [Link][nbr]

def get_indegree(self):
return [Link]

def set_indegree(self, indegree):

[Link] = indegree

def obtine_grad_extern(self):
return [Link]

def setare_grad_exterior(self, grad_exterior):

[Link] = outdegree

def get_predecessor(self):
returnează autoarea

def set_predecessor(self, pred):

[Link] = pred

def obtine_timp_de_visitare(self):

returnează self.visit_time

def setează_timp_de_visitat(self, timp_de_visitat):

self.visit_time = visit_time

def obtine_timp_final(self):
returnează timpul_final

def set_finish_time(self, finish_time):

self.finish_time = finish_time

def obtine_culoare(self):

114
Programul cursului

returnează [Link]

def set_color(self, culoare):

[Link] = color

def __str__(self):
return str([Link]) + ' conectat la: ' + str([[Link] pentru x
în [Link]])

clasa Grafic:

def __init__(self):
self.vertex_dict = {}
self.no_vertices = 0
self.no_edges = 0

def adauga_varf(self, cheia_varf);

new_vertex_obj = Vertex(vert_key)
self.vertex_dict[vert_key] = new_vertex_obj
self.no_vertices += 1

def obtine_vertex(self, cheie_vert):

dacă vert_key este în self.vertex_dict:
return self.vertex_dict[vert_key]
altfel:
returnează Nimic

def adauga_endl(self, de_la, la, greutate=1):

dacă fro nu este în self.vertex_dict:
self.add_vertex(fro)
from_vertex = self.get_vertex(fro)
altfel:
from_vertex = self.vertex_dict[fro]

dacă nu în self.vertex_dict:
self.adauga_varf(to)
to_vertex = self.get_vertex(to)

115
Programul cursului

altfel:
to_vertex = self.vertex_dict[to]

from_vertex.adauga_vecin(to_vertex, greutate)
from_vertex.set_outdegree(from_vertex.get_outdegree() +
1)
to_vertex.set_indegree(to_vertex.get_indegree() + 1)
self.no_edges += 1

def obtine_margini(self):
edges = []
pentru u în self.vertex_dict:
pentru v în self.vertex_dict[u].get_neighbors():
u_id = u
#print(v)
v_id = v.get_id()
[Link]((u_id, v_id, self.vertex_dict[u].ge
t_weight(v)))
returna ț i muchiile

def obtine_varfurile(self):
return self.vertex_dict

clasa DFS:

def __init__(self, graf):

[Link] = graph
self.has_cycle = False

def dfs(self):
pentru vârf în [Link].get_vertices():
dacă [Link].vertex_dict[vertex].get_color() == "alb"
ite
self.dfs_visit([Link].vertex_dict[vertex])

def dfs_visit(self, node):

node.set_color("gri")
pentru vert în nod.get_neighbors():
dacă vert.get_color() == "gri":

116
Programul cursului

self.has_cycle = True
dacă vert.get_color() == "alb":
vert.set_color("gri")
self.dfs_visit(vert)
node.set_color("negru")

clasă Solu ț ie(object):

def poateFinaliza(self, numarCursuri, cerintePrealabile):
"""
:tip numCursuri: int
:tip precondi ț ii: List[List[int]]
:rtype: bool
"""
dacă nu există cerin ț e preliminare:

întoarce Adevărat

altfel:
g = Graf()

pentru muchia în cerin ț e:

g.adauga_latura(edge[0], edge[1])

dfs_obj = DFS(g)
dfs_obj.dfs()
dacă dfs_obj.are_cicluri == Adevărat:
returnează Fals
altfel:
returnează Adevărat

dacă __name__ == '__main__':

soln1 = Solution()
print([Link](2, [[1,0]]))

soln2 = Solu ț ie()

print([Link](2, [[1,0],[0,1]]))

117
Graf arbore valid

Grafic arbore valid

Dând n noduri etichetate de la 0 la n - 1 ș i o listă de muchii neorientate (fiecare muchie este
o pereche de noduri), scrie o funcț ie pentru a verifica dacă aceste margini formează un valid
copac.

De exemplu:

Dat n = 5 ș i muchiile = [[0, 1], [0, 2], [0, 3], [1, 4]], returnează adevărat.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Indicaț ie:

Având n = 5 ș i muchii = [[0, 1], [1, 2], [3, 4]], ce ar trebui să returnezi? Este această situaț ie
o arbore valid? Conform definiț iei de arbore de pe Wikipedia: "un arbore este un"
grafic neorientat în care orice două vârfuri sunt conectate printr-un singur drum.
în alte cuvinte, orice graf conectat fără cicluri simple este un arbore.

URL:[Link]

import sys
clasă Vârf:
def __init__(self, nod):
[Link] = node
[Link] = {}
Seta ț i distan ț a la infinit pentru toate nodurile
[Link] = [Link]
Marchează toate nodurile ca nevizitate

[Link] = False
Marchează toate nodurile cu culoarea albă
[Link] = 'white'
Predecesor
[Link] = None

def adaugăVecin(self, vecin, greutate=0):

[Link][neighbor] = weight

def ob ț ineConexiuni(self):

118
Grafic Copac Valabil

return [Link]()

def obtineIDVertex(self):
return [Link]

def obtineGreutatea(self, vecin):

return [Link][vecin]

def setDistance(self, dist):

[Link] = dist

def obtineDistan ț a(self):

returnează [Link]

def setColor(self, culoare):

[Link] = color

def getColor(self):
returnează [Link]

def setPrevious(self, prev):

[Link] = prev

def setVisited(self):
[Link] = True

def __str__(self):
return str([Link]) + ' adiacent: ' + str([[Link] pentru x în
[Link]])

clasă Grafică:
def __init__(self):
[Link] = {}
[Link] = 0

def __iter__(self):
return iter([Link]())

def adaugăVârf(self, nod):

[Link] = [Link] + 1

119
Graf copac valid

newVertex = Vertex(nod)
[Link][node] = newVertex
returnează newVertex

def obtineVarf(self, n):

dacă n în [Link]:
return [Link][n]
altfel:
return None

def adaugaArc(self, de la, la, cost=0):

dacă frm nu este în [Link]:
[Link](frm)
dacă nu este în [Link]:
[Link](to)

[Link][frm].adaugaVecin([Link]
[to], cost)
[Link][to].addNeighbor([Link][
frm], cost)

def obtineVarfuri(self):
return [Link]()

def setPrevious(self, current):

[Link] = current

def obtineAnteriorul(self, curent):

returnează [Link]

clasă Solu ț ie:

def arboreValid(self, n, muchii):
"""
:tip n: int
:tip margini: Listă[Listă[int]]
:rtype: bool
"""
dacă n == 1 ș i len(edges) == 0:
returnează Adevărat

elif self.check_input(n, edges) == Falsă:

120
Graf valid arbore

returnează Fals
elif n == 0 ș i len(edges) > 0:
returnează Fals
elif n == 1 ș i len(edges) >= 1:
returnează Fals
altfel:
G = Grafic()
pentru intrări în margini:
[Link](entries[0], entries[1], 1)

results = []
pentru vârful în G:
dacă [Link]() == "alb":
[Link](self.check_validity(vertex))

dacă len(results) > 1:

returnează False
altfel:
returnează rezultatele[0]

def verifica_intrarea(self, n, muchii):

vertices = []
pentru intrări în margini:
[Link](entries[0])
[Link](entries[1])
dacă len(set(vârfuri)) != n:
return False
altfel:
returnează Adevărat

def verifica_valabilitatea(self, start):

stack = []
[Link]("gri")
[Link](start)
while stack != []:
curr_node = [Link]()
pentru nbr în curr_node.getConnections():
dacă [Link]() == "gri":
returnează Fals

121
Graf valid de arbore

dacă [Link]() == "alb":

[Link]("gri")
[Link](nbr)
curr_node.setColor("negru")
returnează Adevărat

122
Programul cursului 2

Programul cursului 2
Există un total de n cursuri pe care trebuie să le urmezi, etichetate de la 0 la n - 1.

Unele cursuri pot avea cerinț e prealabile, de exemplu pentru a urma cursul 0 trebuie să
mai întâi urmează cursul 1, care este exprimat ca o pereche: [0,1]

Având în vedere numărul total de cursuri ș i o listă de perechi de cerinț e, returnaț i

ordonarea cursurilor pe care ar trebui să le urmezi pentru a finaliza toate cursurile.

Este posibil să existe mai multe ordine corecte, trebuie doar să returnaț i unul dintre ele. Dacă este
imposibil de finalizat toate cursurile, returnaț i un array gol.

De exemplu:

Sunt un total de 2 cursuri de urmat. Pentru a urma cursul 1, ar trebui să ai

cursul 0 finalizat. Deci, ordinea corectă a cursurilor este [0,1]

Există un total de 4 cursuri de urmat. Pentru a urma cursul 3

ar trebui să fi terminat ambele cursuri 1 ș i 2. Ambele cursuri 1 ș i 2 ar trebui să fie
făcut după ce ai terminat cursul 0. Aș a că o ordine corectă a cursurilor este [0,1,2,3]. O altă
ordonarea corectă este [0,2,1,3].

URL:[Link]

din coadă importă Coada

importa sistemul

clasa Vertex:
def __init__(self, nod):
[Link] = nod
[Link] = {}
Setează distan ț a la infinit pentru toate nodurile
[Link] = [Link]
# Marchează toate nodurile ca nevizitate

[Link] = False
# Marcare toate nodurile cu alb
[Link] = 'white'
Predecesor

123
Programul cursului 2

[Link] = None
gradul de intrare al vârfului
[Link] = 0

def adaugaVecin(self, vecin, greutate=0):

[Link][neighbor] = weight

def obtineConexiuni(self):
return [Link]()

def obtineIDVertice(self):
return [Link]

def obtineGreutatea(self, vecin):

return [Link][vecin]

def setDistance(self, dist):

[Link] = dist

def getDistance(self):
returnează distan ț a

def setColor(self, culoare):

[Link] = culoare

def obtineCuloarea(self):

return [Link]

def setPrevious(self, prev):

[Link] = prev

def setVisited(self):
[Link] = True

def setIndegree(self, indegree):

[Link] = indegree

def obtineGradIntrare(self):
returnează [Link]

124
Programul cursului 2

def __str__(self):
return str([Link]) + ' adiacente: ' + str([[Link] for x in
[Link]])

clasa GrafDirec ț ionat:

def __init__(self):
[Link] = {}
[Link] = 0

def __iter__(self):
return iter([Link]())

def adaugaVertex(self, nod):

[Link] = [Link] + 1
newVertex = Vertex(nod)
[Link][node] = newVertex
returnează newVertex

def obtineVarf(self, n):

dacă n în [Link]:
return [Link][n]
altfel:
întoarce None

def adaugaMuchie(self, de, la, cost=0):

dacă frm nu este în [Link]:
[Link](frm)
dacă nu este în [Link]:
[Link](to)

[Link][frm].adaugaVecin([Link]
[către], cost)
[Link][to].setIndegree([Link][
to].getIndegree() + 1)

def obtineVarfuri(self):
return [Link]()

def setPrevious(self, current):

[Link] = curent

125
Programul cursului 2

def obtineAnterior(self, curent):

returnează [Link]

clasa Solu ț ie:

def __init__(self):
self.has_cycle = False

def găse ș teOrdinea(self, numărCursuri, cerin ț e):

"""
:tip numCursuri: int
:tip cerin ț e preliminare: Listă[Listă[int]]
:rtype: List[int]
"""
dacă cerin ț ele preliminare == [] ș i numărul cursurilor > 0:

return [intrări pentru intrări în interval(numCourses)]

elif cerin ț ele preliminare == [] ș i numărul cursurilor == 0:

return []
altfel:
G = GrafDirec ț ionat()
pentru intrările în cerin ț ele preliminare:

[Link]ăMuchie(entrări[1], entrări[0], 1)

return [Link](G)

def topsort(self, G):

dacă [Link]() == []:
return []
altfel:
topological_list = []
topological_queue = Queue()
nodes = [Link]()
pentru nod în G:
dacă [Link]() == 0:
topological_queue.put(node)

în timp ce topological_queue.empty() == Fals:

curr_node = topological_queue.get()
topological_list.append(curr_node.getVertexID())

126
Programul cursului 2

pentru nbr în curr_node.getConnections():

[Link]([Link]() - 1)
dacă [Link]() == 0:
topological_queue.put(nbr)

dacă len(topological_list) != len(nodes):

self.has_cycle = True

întoarce_listă_topologică

dacă __nume__ == '__principala__':

soln = Solu ț ie()

print([Link](4, [[1,0],[2,0],[3,1],[3,2]]))
print([Link](2, [[1,0]]))
print([Link](3, [[1,0]]))

127
Numărul de insule

Numărul de insule
Dând o hartă 2D dintr-o reț ea de '1' (teren) ș i '0' (apă), numără numărul de insule. Un
insula este înconjurată de apă ș i este formată prin conectarea terenurilor adiacente
orizontal sau vertical. Puteț i presupune că toate cele patru margini ale reț elei sunt toate
înconjurat de apă.

Exemplul 1:

11110 11010 11000 00000 Răspuns: 1

Exemplul 2:

11000 11000 00100 00011 Răspuns: 3

URL:[Link]

128
Numărul de insule

clasa Solu ț ie:

# @param {boolean[][]} grid o matrice booleană 2D
# @return {int} un întreg
def numIslands(self, grid):
dacă nu există grilă:

return 0

row = len(grid)
col = len(grid[0])
folosit = [[Fals pentru j în xrange(col)] pentru i în xrange(row)]
)]

count = 0
pentru i în xrange(row):
pentru j în xrange(col):
dacă grid[i][j] == '1' ș i nu a fost folosit[i][j]:

[Link](grid, used, row, col, i, j)

count += 1
numărul de returnare

def dfs(self, re ț ea, folosit, rând, coloană, x, y):

dacă grid[x][y] == '0' sau used[x][y]:
întoarce
used[x][y] = Adevărat

dacă x != 0:
[Link](grid, folosit, rand, col, x - 1, y)
dacă x != rând - 1:
[Link](grid, folosit, linie, col, x + 1, y)
dacă y != 0:
[Link](grid, folosit, rand, col, x, y - 1)
dacă y != col - 1:
[Link](grid, folosit, rând, col, x, y + 1)

129
Îmbinaț i K liste legate sortate

Fuzionaț i K liste legate sortate

Fuzionaț i k liste legate sortate ș i returnaț i-o ca o singură listă sortată. Analizaț i ș i descrieț i-l.
complexitate.

URL:[Link]

130
Mergi K liste legate sortate

import heapq
Defini ț ie pentru lista legată simplă.
clasa ListNode(obiect):
def __init__(self, x):
[Link] = x
[Link] = None

clasă Solu ț ie(object):

def combinăKListe(self, liste):
"""
:tip liste: List[ListNode]
:rtype: ListNode
"""
dacă listele == [] sau listele == None:
întoarce Niciunul

altfel:
pq = []
pentru i în intervalul(len(lists)):
dacă listele[i] != Niciuna:

item = (lists[i].val, i, lists[i])

[Link](pq, item)

dummy = ListNode(0)
p = dummy

cât timp pq != []:

heap_item = [Link](pq)
[Link] = heap_item[2]
p = [Link]ător
dacă heap_item[2].next != None:
item = (heap_item[2].[Link], heap_item[1],
heap_item[2].next
[Link](pq, item)

return [Link]

131
Cel de-al K-lea element cel mai mare dintr-un array

Cel de-al K-lea element cel mai mare dintr-un vector

Găseș te al k-lea cel mai mare element dintr-un array nesortat. Observaț i că este al k-lea cel mai mare

element în ordinea sortată, nu al k-lea element distinct.

De exemplu, dat fiind [3,2,1,5,6,4] ș i k = 2, returnaț i 5.

Notă: Puteț i presupune că k este întotdeauna valid, 1 ≤ k ≤ lungimea array-ului.

URL:[Link]

clasă Solu ț ie(objet):

def găse ș teKthCelMaiMare(self, nums, k):
"""
:tip nums: List[int]
:tip k: int
:rtype: int
"""
dacă nums == []:
returna ț i nums
altfel:
heap = []
pentru i în intervalul(0, k):

[Link](hep, (nums[i], i))

pentru j în intervalul(k, len(nums)):

root_element = [entries for entries in [Link]

allest(1, heap)][0]
index_root_element = [Link](root_element)
dacă nums[j] > root_element[0]:
heap[index_root_element] = (nums[j], j)
[Link](heap)

return [Link](heap)[0]

132
2 Suma II

2 Suma II
Dat fiind un tablou de numere întregi care este deja sortat în ordine crescătoare, găseș te două

numere astfel încât să se adune la o anumită sumă ț intă.

Funcț ia twoSum ar trebui să returneze indicii celor două numere astfel încât să se adune
până la ț intă, unde index1 trebuie să fie mai mic decât index2. Vă rugăm să reț ineț i că dumneavoastră

răspunsurile returnate (atât index1 cât ș i index2) nu sunt bazate pe zero.

Puteț i presupune că fiecare intrare ar avea exact o soluț ie.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

URL:[Link]

clasa Solu ț ie(object):

def twoSum(self, numbers, target):
"""
:tip numere: List[int]
:tip ț intă: int
:rtype: List[int]
"""
dacă len(numere) == 0:
return [-1]
altfel:
start = 0
sfâr ș it = len(numere) - 1
în timp ce start < end:
curr_sum = numbers[start] + numbers[end]
dacă curr_sum == target:
return [start+1, end+1]
elif curr_sum < ț intă:
start += 1
elif curr_sum > target:
sfâr ș it -= 1

return [-1]

133
2 Suma II

134
2 Suma III

2 Suma III
Proiectaț i ș i implementaț i o clasă TwoSum. Aceasta ar trebui să suporte următoarele

operations: add and find.

add - Add the number to an internal data structure. find - Find if there exists any
o pereche de numere a căror sumă este egală cu valoarea.

De exemplu, add(1); add(3); add(5); find(4) -> adevărat find(7) -> fals

URL:[Link]

importa colec ț ii

clasa TwoSum(object):

def __init__(self):
"""
initializa ț i structura de date aici
"""
self.__num_list = [Link](int)

def adaugă(self, număr):

"""
Adaugă numărul într-o structură de date internă.
:rtype: nimic
"""
self.__num_list[number] += 1

def găse ș te(self, valoare):

"""
Găse ș te dacă există o pereche de numere al căror sumă este egală
egale cu valoarea.
:type value: int
:rtype: bool
"""

135
2 Suma III

dacă len(self.__num_list) == 0:
returnează Fals
în altă ordine de idei:
pentru intrările din self.__num_list.keys():
ț intă = valoare - intrări
dacă ( ț inta este în self.__num_list) ș i (înregistrările != t

target sau self.__num_list[target] > 1):

returnează Adevărat

întoarce Fals

dacă __numele__ == "__principal__":

# Your TwoSum object will be instantiated and called as such

:
twoSum = TwoSum()
[Link](0)
[Link]ă(0)
print([Link](0))

136
Conț ine Duplicate

Conț ine duplicate

Dat fiind un array de întregi, află dacă array-ul conț ine duplicate. Funcț ia ta
ar trebui să returneze adevărat dacă orice valoare apare de cel puț in două ori în array, ș i ar trebui să
returnează fals dacă fiecare element este distinct.

URL:[Link]

clasă Solu ț ie (obiect):

def contineDubluri(self, nums):
"""
:tip nums: List[int]
:rtype: bool
"""
dacă nu nums:
returnează Fals
elif len(nums) == 1:
returnează Fals
altfel:
dup_dict = {}

pentru intrările în nums:

dacă există intrări în dup_dict:
întoarce Adevărat

altfel:
dup_dict[entries] = 1
întoarce Fals

137
Roteș te Array

Rotirea unui Array

Rotează un tablou de n elemente spre dreapta cu k paș i.

De exemplu, cu n = 7 ș i k = 3, array-ul [1,2,3,4,5,6,7] este rotit la

[5,6,7,1,2,3,4]

Notă: Încearcă să găseș ti cât mai multe soluț ii posibile, există cel puț in 3 diferite.
moduri de a rezolva această problemă.

URL: [Link]

138
Rotunjeș te tabloul

clasa Solu ț ie(object):

def roteste(self, nums, k):
"""
:tip nums: Lista[int]
:tip k: int
:rtype: void Nu returna ț i nimic, modifica ț i nums în loc
e în schimb.
"""
n = len(nums)
dacă n < 2 sau k == 0:
trece
altfel:
dacă k >= n:
k = k % n
a = n - k
[Link](nums, 0, a-1)
[Link](nums, a, n-1)
[Link](nums, 0, n-1)

def inversa(self, nums, start, end):

i = început
j = sfâr ș it

while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1

dacă __nume__ == "__principal__":

soln = Solution()
nums = [1,2,3,4,5,6,7]
[Link] ț ie(nums, 3)
printaț i(nums)

139
3 Suma mai mică

3 Suma Mai Mică

Given an array of n integers nums and a target, find the number of index triplets i,
j, k cu 0 <= i < j < k < n care satisfac condiț ia nums[i] + nums[j] + nums[k] <
ț intă.

De exemplu, având nums = [-2, 0, 1, 3] ș i target = 2.

Întoarce 2. Pentru că există două tripluri al căror sumă este mai mică decât 2:

[-2, 0, 1] [-2, 0, 3]

URL:[Link]

140
3 Suma mai mică

clasă Solu ț ie(object):

def treiSumaMaiMic(self, numere, tinta):
"""
:tip nums: List[int]
:tip ț intă: int
:rtype: int
"""
dacă len(nums) == 0 sau len(nums) == 2 sau len(nums) == 1:
return len([])
altfel:
triplet_list = []
sorted_nums = sorted(nums)
pentru i în intervalul(0, len(nums) - 2):
start = i + 1
sfâr ș it = lungimea(nums) - 1

în timp ce start < end:

curr_sum = sorted_nums[i] + sorted_nums[star
t] + sorted_nums[end]
dacă curr_sum == target:
finaliza ț i -= 1

elif suma_curentă < ț intă:

triplet = (sorted_nums[i], sorted_nums[s
tart], sorted_nums[end]
triplet_list.append(triplet)
start += 1
elif curr_sum > target:
finaliza -= 1

print(triplet_lista)
#return len([list(entries) for entries in set(triple
t_list)])
return len(triplet_list)

dacă __name__ == '__main__':

soln = Solu ț ie()
print([Link]([3,1,0,-2], 4))

141
3 Suma Cea Mai Aproape

3 Suma Celor Mai Aproape

Dat fiind un array S de n întregi, găsiț i trei întregi în S astfel încât suma să fie cea mai apropiată.

la un număr dat, ț intă. Returnaț i suma celor trei întregi. Puteț i presupune
că fiecare input ar avea exact o soluț ie.

De exemplu, având array-ul S = {-1 2 1 -4} ș i ț intele = 1.

Suma care este cea mai apropiată de ț intă este 2. (-1 + 2 + 1 = 2).

URL:[Link]

142
3 Suma cea mai apropiată

importa ț i sys
clasa Solu ț ie(object):
def treiSumeCelMaiAproape(self, numere, ț intă):
"""
:tip nums: List[int]
:tip ț intă: int
:rtype: int
"""
dacă len(nums) este în [0,1,2]:

return 0
altfel:
min_diff = [Link]
result = 0
sorted_nums = sortate(nums)
pentru i în intervalul(len(nums)):

start = i + 1
end = len(nums) - 1
în timp ce start < end:
curr_sum = sorted_nums[i] + sorted_nums[star
t] + sorted_nums[end]
diff = abs(curr_sum - target)
dacă diff == 0:
return curr_sum
dacă diff < min_diff:
min_diff = diff
result = curr_sum
dacă curr_sum <= ț intă:
start += 1
altfel:
sfâr ș it -= 1
întoarce rezultatul

dacă __name__ == "__main__":

soln = Solution()
print([Link]([-1, 2, 1, -4], 1))
print([Link]([-1, 2, 1, -4], 3))

143
3 Suma Celor Mai Aproape

144
3 Suma

3 Suma
D given un aranjament S de n întregi, există elemente a, b, c în S astfel încât a + b + c
= 0? Găsiț i toate tripletele unice din array care dau suma zero.

Notă: Setul de soluț ii nu trebuie să conț ină triplete duplicate.

De exemplu, având array-ul S = [-1, 0, 1, 2, -1, -4],

Un set de soluț ii este: [ [-1, 0, 1], [-1, -1, 2] ]

URL:[Link]

145
3 Sum

clasa Solu ț ie(object):

def treiSuma(self, nums):
"""
:tip nums: Lista[int]
:rtype: List[List[int]]
"""
dacă len(nums) == 0 sau len(nums) == 2 sau len(nums) == 1:
return []
altfel:
sum_zero_list = []
sorted_nums = sorted(nums)
pentru i în intervalul(0, len(nums) - 2):
start = i + 1
sfâr ș it = len(nums) - 1
în timp ce start < end:
curr_sum = sorted_nums[i] + sorted_nums[star
t] + sorted_nums[end]
dacă curr_sum == 0:
zero_triplet = (sorted_nums[i], sorted_n
ums[start], sorted_nums[end]
sum_zero_list.append(zero_triplet)
start += 1
end -= 1
elif curr_sum < 0:
start += 1
altfel dacă curr_sum > 0:
finalizare -= 1

return [list(entries) for entries in set(sum_zero_li

st)]

if __name__ == "__main__":
soln = Solu ț ie()
print([Link]([-1, 0, 1, 2, -1, -4]))

146
Două Sume

Două Sume
Dat fiind un array de întregi, returnează indicii celor două numere astfel încât să se adune
până la un obiectiv specific.

Puteț i presupune că fiecare input va avea exact o soluț ie.

Example: Given nums = [2, 7, 11, 15], target = 9,

Pentru că nums[0] + nums[1] = 2 + 7 = 9, returnează [0, 1].

URL:[Link]

clasă Solu ț ie(obiect):

def twoSum(self, nums, target):
"""
:tip nums: List[int]
:tip ț intă: int
:rtype: Lista[int]
"""
dict = {}
pentru i în intervalul(len(nums)):

x = nums[i]
dacă target-x în dic ț ionar:

return (dict[target-x], i)
dict[x] = i

147
Plus Unu

Plus Unu
Dat fiind un număr nenegativ reprezentat ca un ș ir de cifre, plus unu la
număr.

Cifrele sunt stocate astfel încât cifra cea mai semnificativă să fie la începutul listei.

URL:[Link]

clasă Solu ț ie(object):

def plusUnu(self, cifre):
"""
:tip cifre: List[int]
:rtype: List[int]
"""
dacă len(digits) <= 0:
return [0]
altfel:
carry = 1
i = len(digits)-1
running_sum = 0
new_digits = []
în timp ce i >= 0:

running_sum = digits[i] + carry

dacă suma_în_executare >= 10:

carry = 1
altfel:
carry = 0
new_digits.append(running_sum % 10)
i -= 1

dacă transportul == 1:

new_digits.append(1)
return new_digits[::-1]
altfel:
returna ț i new_digits[::-1]

148
Plus Unu

149
Cel mai bun moment pentru a cumpăra ș i a vinde acț iuni

Cea mai bună vreme pentru a cumpăra ș i a vinde acț iuni

Să zicem că ai un array pentru care elementul i este preț ul unei acț iuni date pe
ziua i.

Dacă ț i-ar fi permis să efectuezi cel mult o tranzacț ie (adică, să cumperi una ș i
vinde o acț iune a acț iunii), proiectează un algoritm pentru a găsi profitul maxim.

Exemplu 1: Intrare: [7, 1, 5, 3, 6, 4] Ieș ire: 5

diferenț a maximă = 6-1 = 5 (nu 7-1 = 6, deoarece preț ul de vânzare trebuie să fie mai mare decât
preț ul de cumpărare) Exemplu 2: Intrare: [7, 6, 4, 3, 1] Ieș ire: 0

În acest caz, nu se efectuează nicio tranzacț ie, adică profitul maxim = 0.

URL:Cel mai bun timp pentru a cumpăra ș i a vinde acț iuni

clasă Solu ț ie(obiect):

def maxProfit(self, preturi):
"""
:tip pre ț uri: List[int]
:rtype: int
"""
dacă len(pre ț uri) == 0:
returnează 0

altfel:
max_profit = 0
min_price = prices[0]
pentru i în intervalul(len(pre ț uri)):

profit = prices[i] - min_price

max_profit = max(profit, max_profit)
min_price = min(min_price, prices[i])

returnează max_profit

150
Distanț a cea mai scurtă între cuvinte

Distanț a cea mai scurtă între cuvinte

Având o listă de cuvinte ș i două cuvinte word1 ș i word2, returnează cea mai scurtă distanț ă
între aceste două cuvinte din listă.

De exemplu, presupuneț i că cuvintele = ["practică", "face", "perfect", "programare",

"makes"].

Având cuvântul1 = "programare", cuvântul2 = "practică", returnaț i 3. Având cuvântul1 = "face"

word2 = "coding", return 1.

Notă: Poț i presupune că cuvântul1 nu este egal cu cuvântul2, iar cuvântul1 ș i cuvântul2
sunt amândouă în listă.

URL:[Link]

151
Distanț a cea mai scurtă între cuvinte

import sys
clasă Solu ț ie(object):
def distantaCeaMaiScurta(self, cuvinte, cuvant1, cuvant2):
"""
:tip cuvinte: List[str]
:tip cuvânt1: str
:tip cuvânt2: str
:rtype: int
"""

word2_positions = []
word1_positions = []

pentru i în intervalul(len(cuvinte)):

dacă cuvântul1 == cuvinte[i]:

word1_positions.append(i)
dacă word2 == words[i]:
word2_positions.adauga(i)

min_dist = [Link]

pentru pos1 în word1_positions:

pentru pos2 în word2_positions:
dacă abs(pos1 - pos2) < min_dist:
min_dist = abs(pos1 - pos2)

return min_dist

152
Mută Zerourile

Mută zerourile
Având un array nums, scrie o funcț ie pentru a muta toate 0-urile la sfârș itul acestuia în timp ce

menț inând ordinea relativă a elementelor nenule.

De exemplu, având nums = [0, 1, 0, 3, 12], după ce ai apelat funcț ia ta, nums ar trebui să
fii [1, 3, 12, 0, 0].

Notă: Trebuie să faceț i asta în loc, fără a face o copie a array-ului. Minimizaț i
numărul total de operaț iuni.

URL:[Link]

clasa Solu ț ie(object):

def mutaZeroes(self, nums):
"""
:tip nums: Lista[int]
:rtype: void Nu returna ț i nimic, modifica ț i nums în loc
în schimb.
"""

i = 0
j = 0
while j < len(nums):
dacă nums[j] == 0:
j += 1
altfel:
nums[i] = nums[j]
i += 1
j += 1

în timp ce i < len(nums):

nums[i] = 0
i += 1

153
Conț ine Duplicatul II

Conț ine duplicate II

Dat fiind un array de întregi ș i un întreg k, determină dacă există două distincte
indici i ș i j în matrice astfel încât nums[i] = nums[j] ș i diferenț a dintre i
ș i j este cel mult k.

URL:[Link]

clasă Solu ț ie(object):

def contineDuplicateAproape(self, nums, k):
"""
:tip nums: Lista[int]
:tip k: int
:rtype: bool
"""
dacă nu există nums:

returnează Fals
elif len(nums) == 1:
returnează Fals
elif len(nums) == 2:
dacă nums[0] != nums[1]:
returnează Fals
altfel:
dacă nums[0] == nums[1] ș i k >= 1:
returnează adevărat

altfel:
întoarce False
altfel:
index_dict = {}
pentru i în intervalul(len(nums)):

dacă nums[i] în index_dict:

prev_index = index_dict[nums[i]]
dacă i - prev_index <= k:
returnează Adevărat

index_dict[nums[i]] = i
returnează Fals

154
Conț ine Duplicate II

155
Element majoritar

Elementul majoritar
Dată fiind o matrice de dimensiune n, găsiț i elementul majoritar. Elementul majoritar este
elementul care apare de mai mult de ⌊n/2⌋ ori.

Puteț i presupune că array-ul nu este gol ș i că elementul majoritar este întotdeauna.

există în array.

URL:[Link]

156
Element Majoritar

clasă Solu ț ie(object):

def elementMajoritar(self, nums):
"""
:tip nums: Lista[int]
:rtype: int
"""
candidate = self.get_candidate(nums)
candidate_count = 0
dacă candidatul != Niciunul:
pentru intrările din nums:
dacă intrările == candidat:
candidate_count += 1
dacă numărul_candida ț ilor >= len(nums)//2:
returna ț i candidatul
altfel:
return None
altfel:
nu returna nimic

def obtine_candidatul(self, nums):

count = 0
candidate = None
pentru intrări în nums:
dacă numărul == 0:
candidate = entries
count = 1
altele:
dacă candidatul == intrări:
count += 1
altfel:
count -= 1
dacă numărul este mai mare decât 0:

returnează candidatul
altfel:
return None

157
Element majoritar

158
Elimină duplicatele dintr-un array sortat

Eliminaț i duplicatele dintr-un array sortat

Dat un ș ir sortat, elimină duplicatele pe loc astfel încât fiecare element

apare doar o singură dată ș i returnează noua lungime.

Nu alocaț i spaț iu suplimentar pentru un alt tablou, trebuie să faceț i asta în loc.
memorie constantă.

De exemplu, dat fiind că inputul este un array nums = [1,1,2],

Funcț ia ta ar trebui să returneze lungimea = 2, cu primii doi elemente din nums fiind 1
ș i 2, respectiv. Nu contează ce laș i dincolo de noua lungime.

URL:[Link]

clasa Solu ț ie(object):

def eliminaDuplicate(self, nums):
"""
:tip nums: List[int]
:rtype: int
"""
dacă len(nums) < 2:
return len(nums)
altfel:
j = 0
i = 1
while i < len(nums):
dacă nums[j] == nums[i]:
i += 1
altfel:
j += 1
nums[j] = nums[i]
i += 1
returnează j+1

159
Suma Greutăț ii Listei Imbricate

Suma greutăț ii listei imbricate

Având o listă imbricată de întregi, returnaț i suma tuturor întregilor din listă cântărită de
adâncimea lor.

Fiecare element este fie un întreg, fie o listă - al cărei elemente pot fi de asemenea întregi
sau alte liste.

Exemplul 1: Dând lista [[1,1],2,[1,1]], returnează 10. (patru 1 în adâncimea 2, un 2 la

depth 1)

Exemplul 2: Dat fiind lista [1,[4,[6]]], returnează 27. (un 1 la adâncimea 1, un 4 la adâncimea 2,
ș i un 6 la adâncimea 3; 1 + 42 + 63 = 27)

URL:[Link]

# """
Aceasta este interfa ț a care permite crearea listelor imbricate.
Nu ar trebui să-l implementezi sau să speculezi despre implementarea sa.
ţion
# """
#clasă NestedInteger(object):
# def esteIntreg(self):
# """
# _returna ț i adevărat dacă acest NestedInteger con ț ine un singur întreg_
er, mai degrabă decât o listă imbricată.

# :rtype bool
# """
#
# def obtineIntegerself):
# """
# returna ț i singurul întreg pe care acest NestedInteger îl de ț ine
s, dacă con ț ine un singur întreg
# Return None if this NestedInteger holds a nested list
# :tip int
# """
#
# def getList(self):

160
Suma Greutăț ii Listei Imbicate

# """
# returnează lista imbricată pe care o de ț ine acest NestedInteger,
dacă con ț ine o listă imbricată
# Returna ț i None dacă acest NestedInteger con ț ine un singur întreg
r
# :rtype List[NestedInteger]
# """

clasă Solu ț ie(object):

def adâncimeSuma(self, listaNested):
"""
:tip listă Înglobată: Listă[NestedInteger]
:rtype: int
"""
return self.depthSum_helper(nestedList, 1)

def depthSum_helper(self, lista_nesfâr ș ită, adâncime):

dacă len(nested_list) == 0 sau nested_list == None:
returnează 0

altfel:
sum = 0
pentru intrări în lista_nesfâr ș ită:
dacă intră[Link]():
sum += [Link]()*adâncime
altfel:
sum += self.depthSum_helper([Link](
), adâncime + 1)

returnează suma

161
Suma ponderată a listei imbricate II

Suma Ponderată a Listei Nestorii II

Dată fiind o listă imersată de întregi, returnează suma tuturor întregilor din listă, ponderată de
adâncimea lor.

Fiecare element este fie un întreg, fie o listă - ale cărei elemente pot fi de asemenea întregi
sau alte liste.

Spre deosebire de întrebarea precedentă, unde greutatea creș te de la rădăcină la frunză,

Acum greutatea este definită de jos în sus. Adică, numerele întregi de la nivelul frunzelor au greutate.
1, iar numerele întregi de nivel rădăcină au cel mai mare coeficient.

Exemplul 1: Având lista [[1,1],2,[1,1]], returnează 8. (patru 1 la adâncimea 1, unul 2 la

depth 2)

Exemplu 2: Dată fiind lista [1,[4,[6]]], returnaț i 17. (un 1 la adâncimea 3, un 4 la adâncimea 2,
ș i un 6 la adâncimea 1; 13 + 42 + 6*1 = 17)

URL:[Link]

162
Elimină elementul

Elimină elementul
Dat un tablou ș i o valoare, eliminaț i toate instanț ele acestei valori în loc ș i returnaț i
noua lungime.

Nu alocaț i spaț iu suplimentar pentru un alt array, trebuie să faceț i asta în loc.
memorie constantă.

Ordinea elementelor poate fi schimbată. Nu contează ce laș i în afară.

noua lungime.

Example: Given input array nums = [3,2,2,3], val = 3

Funcț ia ta ar trebui să returneze lungimea = 2, cu primele două elemente din nums fiind 2.

URL:[Link]

clasa Solu ț ie(object):

def eliminaElement(self, nums, val):
"""
:tip nums: Lista[int]
:tip val: int
:rtype: int
"""
dacă val == []:
return 0
altfel:
i = 0
j = 0
în timp ce j < lungimea(nums):

dacă nums[j] == val:

j += 1
altfel:
nums[i] = nums[j]
i += 1
j += 1

return len(nums[0:i])

163
Eliminare element

164
Intersecț ia a Două Mici II

Intersecț ia a două arii II

Dată fiind două array-uri, scrie o funcț ie pentru a calcula intersecț ia lor.

Exemplu: Având nums1 = [1, 2, 2, 1], nums2 = [2, 2], returnaț i [2, 2].

Note: Each element in the result should appear as many times as it shows in both
arregi. Rezultatul poate fi în orice ordine. Continuare: Ce se întâmplă dacă array-ul dat este

deja sortat? Cum ai optimiza algoritmul tău? Ce dacă dimensiunea lui nums1 este
mic comparativ cu dimensiunea lui nums2? Care algoritm este mai bun? Ce dacă elementele de
nums2 sunt stocate pe disc, iar memoria este limitată astfel încât nu poț i încărca tot
elemente în memorie deodată?

URL:intersecț ia a două array-uri II

165
Intersecț ia a două array-uri II

clasă Solu ț ie(obiect):

def intersect(self, nums1, nums2):
"""
:tip nums1: Lista[int]
:tip nums2: List[int]
:rtype: List[int]
"""
sorted_nums1 = sortate(nums1)
sorted_nums2 = sortate(nums2)

i = 0
j = 0
intersect_list = []

în timp ce i < len(sorted_nums1) ș i j < len(sorted_nums2):

dacă sorted_nums1[i] < sorted_nums2[j]:
i += 1
elif sorted_nums2[j] < sorted_nums1[i]:
j += 1
altfel:
intersect_list.append(sorted_nums1[i])
i += 1
j += 1

return intersect_list

166
Fuzionarea unor array-uri sortate

Fuziune matrice sortate

Având două tablouri de întregi sortate nums1 ș i nums2, îmbina nums2 în nums1 ca
o matrice sortată.

Notă: Puteț i presupune că nums1 are suficient spaț iu (dimensiunea este mai mare sau
egal cu m + n) pentru a reț ine elemente suplimentare din nums2. Numărul de elemente
iniț ializat în nums1 ș i nums2 sunt m ș i n respectiv.

URL:[Link]

167
Îmbinaț i array-urile sortate

clasa Solu ț ie(object):

def combinare(self, nums1, m, nums2, n):
"""
:tip nums1: Lista[int]
:tip m: int
:tip nums2: List[int]
:tip n: int
:rtype: void Nu returna ț i nimic, modifica ț i nums1 în loc
ce în schimb.
"""
last1 = m - 1
last2 = n - 1
last = m + n - 1

în timp ce last1 >= 0 ș i last2 >= 0:

dacă nums1[last1] > nums2[last2]:
nums1[ultimul] = nums1[ultimul1]
last1 -= 1
last -= 1
altfel:
nums1[last] = nums2[last2]
last2 -= 1
last -= 1

în timp ce last2 >= 0:

nums1[last] = nums2[last2]
last -= 1
last2 -= 1

168
Inversarea vocalelor dintr-un ș ir

Inversarea vocalelor dintr-un ș ir

Scrie o funcț ie care ia un ș ir ca input ș i inversează doar vocalele.

ș ir.

Exemplu 1: Dând s = "hello", returnează "holle".

Exemplu 2: Dând s = "leetcode", returnaț i "leotcede".

Notă: Vocalele nu includ litera "y".

URL:[Link]

169
Inversează vocalele unui ș ir

clasa Solu ț ie(object):

def __init__(self):
self.__vowels = {"a" : True, "e" : True, "i" : True, "o"
: True, "u" : True, "A" : True, "E" : True, "I" : True, "O" : T
rue, "U" :Adevărat,

def inverseazaVocalele(self, s):

"""
:tip s: str
:rtype: str
"""
dacă s == None sau s == "" sau len(s) == 1:
returnează s

altfel:
i=0
j = len(s) - 1
s = list(s)

în timp ce i < j:
dacă s[i] nu este în auto.__vocale:
i += 1
continuă
dacă s[j] nu este în auto.__vocale:
j -= 1
continuare
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
return "".join(s)

170
Intersecț ia a două array-uri

Intersecț ia a două array-uri

Dată fiind două matrice, scrie o funcț ie pentru a calcula intersecț ia lor.

Exemplu: Dat nums1 = [1, 2, 2, 1], nums2 = [2, 2], returnaț i [2].

Note: Each element in the result must be unique. The result can be in any order.

URL: [Link]

clasa Solu ț ie (obiect):

def intersec ț ie(self, nums1, nums2):
"""
:tip nums1: List[int]
:tip nums2: Lista[int]
:rtype: List[int]
"""
nums1 = sortat(nums1)
nums2 = sortat(nums2)
intersection = {}
i = 0
j = 0
în timp ce i < len(nums1) ș i j < len(nums2):
dacă nums1[i] < nums2[j]:
i += 1
elif nums2[j] < nums1[i]:
j += 1
altfel:
intersec ț ie[nums1[i]] = nums1[i]
i += 1
j += 1

return [Link]()

171
Containerul cu cea mai multă apă

Containerul cu cea mai multă apă

Dând numere întregi nenegative a1, a2, ..., an, unde fiecare reprezintă un punct la
coordonate (i,ai). Se trag n linii verticale astfel încât cele două capete ale liniei i să fie la
(i,ai) ș i (i, 0). Găsiț i două linii, care împreună cu axa x formează un container, astfel încât
că recipientul conț ine cea mai multă apă.

Notă: Nu trebuie să înclinaț i recipientul ș i n este cel puț in 2.

URL:[Link]

clasă Solu ț ie(object):

def maxArie(self, inaltime):
"""
:tip înăl ț ime: List[int]
:rtype: int
"""
max_area = 0
i = 0
j = len(height) - 1
în timp ce i<j:

max_area = max(max_area, min(înăl ț imea[i], înăl ț imea[j])*(

j-i))
dacă înăl ț imea[i] < înăl ț imea[j]:

i += 1
alteci:
j -= 1

returnează aria_maximă

172
Produsul array-ului cu excepț ia sine

Având un tablou de n întregi unde n > 1,numere, returnează un arrayoutput atât de

aceeaie ș ire[i]este egal cu produsul tuturor elementelor
denumerecu excep ț ianums[i].

Rezolvă fără împărț ire ș i în O(n).

De exemplu, dat fiind[1,2,3,4], întoarce-te[24,12,8,6] .

Urmărire:
Ai putea să o rezolvi cu complexitate spaț ială constantă? (Notă: Array-ul de ieș ire
nu contează ca spaț iu suplimentar în scopul analizei complexităț ii spaț iale.)

URL:[Link]

clasa Solu ț ie (obiect):

def produsFaraSine(self, numere):
"""
:tip nums: Lista[int]
:rtype: List[int]
"""
before = [1]*len(nums)
after = [1]*len(nums)
product = [0]*len(nums)

pentru i în intervalul(1, len(nums)):

before[i] = before[i-1]*nums[i-1]

pentru i în intervalul(len(nums)-2, -1, -1):

after[i] = after[i+1]*nums[i+1]

pentru i în intervalul(0, len(nums)):

product[i] = before[i]*after[i]

returnează produsul

173
Capturarea apei de ploaie

Date fiind n numere întregi non-negative care reprezintă o hartă de elevare unde lăț imea de
fiecare bară este 1, calculează câtă apă este capabilă să reț ină după ploaie.

De exemplu,
Dat[0,1,0,2,1,0,1,3,2,1,2,1] , return6.

Harta de elevare de mai sus este reprezentată de array [0,1,0,2,1,0,1,3,2,1,2,1]. În aceasta

În acest caz, 6 unităț i de apă de ploaie (secț iunea albastră) sunt prinse. Mulț umesc, Marcos.
contributing this image!

URL:[Link]

174
Capturarea apei de ploaie

clasa Solu ț ie(object):

def capcana(self, inaltime):
"""
:tip înăl ț ime: List[int]
:rtype: int
"""
maxseenright = 0
maxseenright_arr = [0]*len(inaltime)
maxseenleft = 0
rainwater = 0

pentru i în intervalul(len(înăl ț ime) - 1, -1, -1):

dacă height[i] > maxseenright:

maxseenright_arr[i] = height[i]
maxseenright = height[i]
altfel:
maxseenright_arr[i] = maxseenright

pentru i în intervalul(0, len(height)):

rainwater = rainwater + max(min(maxseenright_arr[i],

maxseenleft) - înăl ț imea[i],0)
if height[i] > maxseenleft:
maxseenleft = height[i]

întoarcerea apei pluviale

175
Subarray Maxim

Găseș te subarray-ul contigu contând cel puț in un număr în cadrul unui array
care are suma cea mai mare.

De exemplu, având în vedere matricea[-2,1,-3,4,-1,2,1,-5,4] ,

subarray-ul contiguu[4,-1,2,1] are suma cea mai mare =6.

URL: [Link]

import sys
clasa Solu ț ie(obiect):
def maxSubArray(self, nums):
"""
:tip nums: List[int]
:rtype: int
"""
dacă nums == []:
return 0
elif len(nums) == 1:
returna ț i nums[0]
elif len(nums) == 2:
returnează max(nums[0], nums[1], nums[0]+nums[1])
altfel:
all_neg = True
pentru intrările din nums:
dacă intrările >= 0:
all_neg = False
dacă all_neg == Fals:
curr_sum = 0
max_sum = - [Link] - 1
pentru i în intervalul(len(nums)):

curr_sum += nums[i]
dacă curr_sum < 0:
curr_sum = 0
dacă curr_sum > max_sum:
max_sum = curr_sum
returnează max_sum
altfel:
returnează max(nums)

176
Subvector maxim

177
Cel mai bun timp pentru a cumpăra ș i vinde acț iuni II

Să spunem că ai un array pentru care elementul i este preț ul unei acț iuni date pe
zi

Proiectaț i un algoritm pentru a găsi profitul maxim. Puteț i finaliza cât mai multe
tranzacț ii după cum doriț i (adică, cumpăraț i o acț iune ș i vindeț i o acț iune a stocului de mai multe ori)

totuș i, nu puteț i desfăș ura mai multe tranzacț ii în acelaș i timp

(adică, trebuie să vindeț i acț iunile înainte de a cumpăra din nou).

URL: [Link]

clasă Solu ț ie(obiect):

def maxProfit(self, preturi):
"""
:tip pre ț uri: List[int]
:rtype: int
"""
dacă pre ț urile == []:
return 0
altfel:
profit = 0
pentru i în intervalul(1, len(prices)):

curr_profit = prices[i] - prices[i-1]

dacă curr_profit > 0:
profit += curr_profit
returna ț i profit

178
Găsiț i minimul într-un tablou sortat rotit

Presupunem că un array sortat este rotit la un anumit pivot necunoscut anterior.

(adică,0 1 2 4 5 6 7s-ar putea deveni4 5 6 7 0 1 2).

Găseș te elementul minim.

Puteț i presupune că nu există duplicate în matrice.

URL: [Link]

clasa Solu ț ie (obiect):

def găse ș teMin(self, nums):
"""
:tip nums: Lista[int]
:rtype: int
"""
start = 0
end = len(nums) - 1

în timp ce început < sfâr ș it:

mid = start + (end - start) // 2

dacă nums[mid] >= nums[end]:
start = mid + 1
altfel:
sfâr ș it = mijloc

returnează nums[start]

179
Triunghiul lui Pascal

Având un număr de rânduri, generaț i primele număr de rânduri ale triunghiului lui Pascal.

De exemplu, numRows dat = 5,

Întoarce-te

[
[1],
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
]

URL: [Link]

180
Triunghiul lui Pascal

clasă Solu ț ie(object):

def genereaza(self, numarRanduri):
"""
:tip numRows: int
:rtype: List[List[int]]
"""
dacă numRows <= 0:
return []

result = []
pre = []

[Link](1)
[Link](pre)

pentru i în intervalul (0, numRows-1):

curr = []
[Link](1)
pentru j în intervalul(0, len(pre)-1):

[Link](pre[j]+pre[j+1])
[Link](1)
[Link](curr)
pre = curr

return result

181
Triunghiul lui Pascal II

Dat un index k, returnaț i a k-a linie a triunghiului lui Pascal.

De exemplu, dat k = 3,
Întoarce-te [1,3,3,1].

Note:
Ai putea să-ț i optimizezi algoritmul pentru a folosi doar O(k) spaț iu suplimentar?

URL: [Link]

clasă Solu ț ie (obiect):

def obtineRand(self, indexRand):
"""
:type rowIndex: int
:rtype: List[int]
"""
dacă rowIndex < 0:
return []
elif rowIndex == 0:
return [1]
altfel:
pre = []
[Link](1)
pentru i în intervalul(1, rowIndex + 1):

curr = []
[Link](1)
pentru j în intervalul (0, len(pre) - 1):

[Link](pre[j]+pre[j+1])
[Link](1)
pre = curr

returna ț i pre

182
Summary Ranges

Având un tablou de întregi sortat fără duplicate, returnaț i rezumatul intervalelor sale.

De exemplu, dat fiind[0,1,2,4,5,7], întoarcere["0->2","4->5","7"].

URL: [Link]

clasa Solu ț ie(obiect):

def rezumatIntervale(self, nums):
"""
:tip nums: List[int]
:rtype: List[str]
"""
dacă nums == []:
întoarce nums
elif len(nums) == 1:
return [str(nums[0])]
altfel:
start = nums[0]
final = nums[0]
res = []
pentru i în intervalul (1, lungimea(nums)):

dacă nums[i] - nums[i-1] == 1:

sfâr ș it = nums[i]
altfel:
[Link](self.to_str(start, end))
start = end = nums[i]

[Link](self.to_str(start, end))

returnează res

def la_string(self, start, end):

dacă start == end:
return str(start)
altfel:
return str(start)+"->"+str(end)

183
Număr Lipsă

Având un tablou care conț ine numere distincte luate din0, 1, 2, ..., n, găsi
cel care lipseș te din matrice.

De exemplu,
Givennums= [0, 1, 3]întoarce2.

Notă:
Algoritmul tău ar trebui să ruleze cu o complexitate de timp liniară. Ai putea să-l implementezi?
folosind doar complexitate constantă a spaț iului suplimentar?

URL:[Link]

clasa Solu ț ie(object):

def numărLipsă(self, numere):
"""
:tip nums: List[int]
:rtype: int
"""
dacă nu există nums:

return None
altfel:
xor_prod = 0
xor_prod_index = 0

pentru i în intervalul (len(nums)+1):

xor_prod_index ^= i

pentru i în intervalul(len(nums)):

xor_prod ^= nums[i]

return xor_prod ^ xor_prod_index

184
Anagramă validă

Anagram valid
Având două ș iruri s ș i t, scrie o funcț ie pentru a determina dacă t este un anagramă a lui s.

De exemplu, s = "anagram", t = "nagaram", returnează adevărat. s = "ș obolan", t = "maș ină", returnează

fals.

Notă: Puteț i presupune că ș irul conț ine doar litere mici.

URL:[Link]

clasa Solu ț ie(object):

def esteAnagrama(self, s, t):
"""
:tip s: str
:tip t: str
:rtype: bool
"""
dacă len(s) != len(t):
returnează False
elif sorted(s) == sorted(t):
returnează Adevărat

altfel:
întoarce False

185
Palindrom Valabil

Palindrom valabil
Având un ș ir, determină dacă este un palindrom, având în vedere doar caracterele alfanumerice.
caractere ș i ignorând cazurile.

De exemplu, "Un bărbat, un plan, un canal: Panama" este un palindrom. "cursa o maș ină" este
nu este un palindrom.

Notă: Ai luat în considerare că ș irul ar putea fi gol? Aceasta este o întrebare bună
a întreba în timpul unui interviu.

În scopul acestei probleme, definim ș irul gol ca fiind un palindrom valabil.

URL:palindrom valid

importa ț i re
clasa Solu ț ie:
# @param {string} s
# @return {boolean}
def estePalindrom(self, s):
dacă len(s) == 0:
returnează Adevărat

altfel:
start = 0
s = [Link]()
newS = [Link](r"[^a-zA-Z0-9]","",s)
sfâr ș it = lungimea(newS) - 1

în timp ce start < end:

dacă newS[start] == newS[end]:
start = start + 1
sfâr ș it = sfâr ș it - 1

altfel:
returnează Fals
returnează True

186
Model de cuvinte

Model de cuvinte
Având un model ș i un ș ir de caractere str, verificaț i dacă str urmează acelaș i model.

Aici, urmează înseamnă o potrivire completă, astfel încât există o bijecț ie între o literă în
model ș i un cuvânt non-gol în str.

Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern =
"abba", str = "dog cat cat fish" should return false. pattern = "aaaa", str = "dog cat
câine pisică" ar trebui să returneze fals. model = "abba", str = "câine câine câine câine" ar trebui să

return false. Nota: Puteț i presupune că modelul conț ine doar litere mici.
str conț ine litere mici separate printr-un singur spaț iu.

URL:[Link]

187
Tiparul cuvintelor

clasă Solu ț ie(object):

def modelCuvinte(self, pattern, str):
"""
:tip model: str
:tip str: str
:rtype: bool
"""
dacă modelul == None sau str == None:
returnează False
altfel:
len_str = len([Link](" "))
len_pattern = len(pattern)
dacă len_str != len_pattern:
întoarce Fals
str = [Link](" ")
lookup = {}
pentru i în intervalul(0, len(model)):
s = str[i]
p = model[i]
dacă p în căutare:
dacă lookup[p] != s:
returnează Fals
altfel:
dacă s este în valorile lookup:
returnează Fals
lookup[p] = s
returnează Adevărat

dacă __nume__ == '__principal__':

pattern = "abba"
câine pisică pisică câine
soln = Solu ț ie()
print([Link](pattern, str))

188
Paranteze valide

Paranteze valide
Având un ș ir care conț ine doar caracterele '(', ')', '{', '}', '[' ș i ']', determină dacă
ș irul de intrare este valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]"
ș i "([)]" nu sunt.

URL:Paranteze valide

189
Paranteze valide

clasa Solu ț ie:

# @param {string} s
# @return {boolean}
def isValid(self, s):
dacă s == []:
întoarce False
altfel:
stack = []
balanced = True
index = 0
în timp ce index < len(s) ș i echilibrat:
simbol = s[index]
dacă simbolul este în "({["

[Link](symbol)
altfel:
dacă stiva == []:
balanced = False
altfel:
top = [Link]()
dacă nu se potrivesc([Link](top,symbol)):

balanced = False
index = index + 1

dacă este echilibrat ș i stiva == []:

returnează Adevărat

altfel:
returnează False

def se potrivesc(self, deschis, inchis):

openings = "({["
closings = ")}]"

return [Link](open) == [Link](close)

190
Ș iruri izomorfe

Ș iruri izomorfe
Având două ș iruri s ș i t, determină dacă sunt izomorfe.

Două ș iruri sunt izomorfe dacă caracterele din s pot fi înlocuite pentru a obț ine t.

Toate apariț iile unui caracter trebuie să fie înlocuite cu un alt caracter în timp ce
păstrând ordinea caracterelor. Nici doi caractere nu pot fi mapate la acelaș i
un caracter, dar un caracter poate corespunde cu sine.

For example, Given "egg", "add", return true.

Având "foo", "bar", returnează fals.

Dacă "hârtie", "titlu", returnează adevărat.

Notă: Poț i presupune că atât s, cât ș i t au aceeaș i lungime.

URL: [Link]

191
Ș iruri izomorfe

clasa Solu ț ie (obiect):

def esteIzomorf(self, s, t):
"""
:tip s: str
:tip t: str
:rtype: bool
"""
dacă s == None sau t == None:
returnează Fals
în cazul în care s == "" ș i t == "":

returnează True
altfel:
dacă len(s) != len(t):
returnează Fals

lookup = {}
pentru i în intervalul(0, len(s)):

c1 = s[i]
c2 = t[i]

dacă c1 este în căutare:

dacă lookup[c1] != c2:

returnează Fals
altfel:
dacă c2 este în valorile lookup:
returnează False
lookup[c1] = c2

întoarce Adevărat

192
Inversare ș ir

Inversare ș ir
Scrieț i o funcț ie care ia un ș ir ca intrare ș i returnează ș irul invers.

Exemplu: Dat s = "salut", returnează "tulas".

URL:[Link]

clasă Solu ț ie(object):

def reverseString(self, s):
"""
:tip s: str
:rtype: str
"""

current_str = [char for char in s]

i = 0
j = lungimea(s) - 1

în timp ce i < j:

temp = current_str[i]
current_str[i] = current_str[j]
current_str[j] = temp
j -= 1
i += 1

return "".join(current_str)

193
Suma a două întregi

Suma a două întregi

Calculaț i suma a două întregi a ș i b, dar nu aveț i voie să folosiț i
operator + ș i -.

Exemplu: Dând a = 1 ș i b = 2, returnează 3.

URL:[Link]

clasa Solu ț ie (obiect):

def getSum(self, a, b):
"""
:tip a: int
:tip b: int
:rtype: int
"""
dacă b == 0:
returna un
sum = a ^ b
carry = (a & b) << 1
returnează [Link](sumă, transport)

194
Număr singular

Număr unic
Dată fiind un tablou de întregi, fiecare element apare de două ori cu excepț ia unuia. Găseș te-l.
singur.

Notă: Algoritmul tău ar trebui să aibă o complexitate de timp liniară.

implementează-l fără a folosi memorie suplimentară?

URL:[Link]

clasa Solu ț ie(object):

def numarSingur(self, nums):
"""
:tip nums: List[int]
:rtype: int
"""
dacă len(nums) == 0:
return None
elif len(nums) == 1:
return nums[0]
altfel:
xor_prod = 0
pentru intrările din nums:

xor_prod ^= intrări

return xor_prod

195
Invertiț i Integerul

Inversare Integer
Inversează cifrele unui întreg.

Example1: x = 123, return 321 Example2: x = -123, return -321

click pentru a arăta spoilere.

Te-ai gândit la asta? Iată câteva întrebări bune de pus înainte de

programare. Puncte bonus pentru tine dacă ai gândit deja la asta!

Dacă cifra finală a întregului este 0, care ar trebui să fie ieș irea? Adică, cazuri precum 10,
100.

Ai observat că întregul inversat ar putea provoca o depăș ire? Presupune că inputul este un 32-
un întreg pe 32 de biț i, apoi inversarea lui 1000000003 provoacă o depăș ire. Cum ar trebui să o gestionezi

astfel de cazuri?

Pentru scopul acestei probleme, presupuneț i că funcț ia dumneavoastră returnează 0 atunci când
depăș irile de capacitate ale numărului întors.

URL:[Link]

import sys
clasă Solu ț ie(obiiect):
def inverse(self, x):
"""
:tip x: int
:tip: int
"""
if x < 0:
return -[Link](-x)

result = 0
în timp ce x:

result = result * 10 + x % 10
x /= 10
returnează rezultatul dacă rezultatul <= 0x7fffffff altfel 0

196
Inversarea unui întreg

197
Număr palindrom

Număr palindrom
Determină dacă un număr întreg este un palindrom. Fă asta fără spaț iu suplimentar.

clic pentru a arăta spoiler-ele.

Câteva sugestii: Ar putea numerele întâmplate negative să fie palindromuri? (de exemplu, -1)

Dacă te gândeș ti să converteș ti întregul în ș ir de caractere, notează restricț ia de utilizare

spaț iu suplimentar.

De asemenea, ai putea încerca să inversezi un număr întreg. Totuș i, dacă ai rezolvat problema
„Număr întors”, ș tii că numărul întors ar putea depăș i limita. Cum ai
gestionezi un astfel de caz?

Există o modalitate mai generică de a rezolva această problemă.

URL:[Link]

clasa Solu ț ie(object):

def estePalindrom(self, x):
"""
:tip x: int
:rtype: bool
"""
dacă x < 0:
întoarce Fals

rev = 0
copie = x
în timp ce copie != 0:

rev = rev * 10 + copy % 10

copy = copy/10
dacă rev == x:
returnează adevărat

altfel:
returna ț i False

198
Număr palindrom

199
Putere(x,n)

Pow(x,n)
Implementaț i pow(x, n).

clasa Solu ț ie (obiect):

def putereaMea(self, x, n):
"""
:tip x: float
:tip n: int
:rtype: flotant
"""
dacă n < 0:
return 1/[Link](x, -n)
altfel:
return [Link](x, n)

def putere(self, x, n):

dacă n == 0:
returnează 1

v = [Link](x, n//2)

dacă n % 2 == 0:
return v * v
altfel:
return v * v * x

200
Subseturi

Submulț imi
Dat fiind un set de întregi distincte, nums, returnaț i toate submulț imile posibile.

Observaț ie: Setul soluț iilor nu trebuie să conț ină subseturi duplicate.

De exemplu, dacă nums = [1,2,3], o soluț ie este:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

URL:[Link]

Solution1:

clasa Solu ț ie(object):

def submul ț imi(self, S):
def dfs(adâncime, început, lista_valori):
[Link](valuelist)
dacă adâncimea == lungimea(S): return

pentru i în intervalul(start, len(S)):

dfs(depth+1, i+1, valuelist+[S[i]])

[Link]()
res = []
dfs(0, 0, [])
return res

Solution2:

201
Submulț imi

clasă Solu ț ie (obiect):

def submultimi(self, numere):
"""
:tip nums: Lista[int]
:rtype: List[List[int]]
"""
n = 1 << len(nums)
result = []
pentru i în intervalul(0, n):

subset = [Link](i, nums)

[Link](submultime)

returna ț i rezultatul

def convert(self, i, nums):

k = i
index = 0
res = []
in timp ce k > 0:

dacă (k & 1) == 1:
[Link](nums[index])

k >>= 1
index += 1
returnează res

202
Subsetele II

Submulț imi II
Având o colecț ie de întregi care ar putea conț ine duplicate, nums, returnaț i toate
subseturi posibile.

Notă: Setul de soluț ii nu trebuie să conț ină submulț imi duplicate.

De exemplu, dacă nums = [1,2,2], o soluț ie este:

[ [2], [1], [1,2,2], [2,2], [1,2], [] ]

URL:[Link]

203
Submulț imi II

clasă Solu ț ie (obiect):

def subseturiCuDup(self, nums):
"""
:tip nums: List[int]
:rtype: List[List[int]]
"""
n = 1 << len(nums)
result = []
pentru i în intervalul(0, n):

subset = [Link](i, nums)

[Link](tupla(sorted(subset)))

result = set(result)
return [list(înregistrări) pentru înregistrări în rezultat]

def convert(self, i, nums):

k = i
index = 0
res = []
în timp ce k > 0:

dacă (k & 1) == 1:
[Link](nums[indice])

k >>= 1
index += 1
returnează res

204
Puterea Trei

Puterea Trei

205
Auto-Crossing

Autocruzare
Îț i este dat un tablou x de n numere pozitive. Începi de la punctul (0,0) ș i te miș ti
x[0] metri la nord, apoi x[1] metri la vest, x[2] metri la sud, x[3]
metri spre est ș i aș a mai departe. Cu alte cuvinte, după fiecare mutare, direcț ia ta
se schimbă în sens invers acelor de ceasornic.

Scrieț i un algoritm cu o singură trecere cu spaț iu suplimentar O(1) pentru a determina dacă drumul dvs.

se intersectează singură sau nu.

Exemplul 1: Dat x = [2, 1, 1, 2], ┌───┐ │ │ └───┼──> │

Returnaț i adevărat (auto-intersectare) Exemplul 2: Având x = [1, 2, 3, 4], ┌──────┐ │ │ │ │

└────────────>

Returnează fals (nu se intersectează singur) Exemplul 3: Dat x = [1, 1, 1, 1], ┌───┐ │ │
└───┼>

Returnează adevărat (autocrossare)

URL:[Link]

206
Autocrossare

clasa Solu ț ie (obiect):

def esteAutoTraversarea(self, x):
"""
:tip x: List[int]
:rtype: bool
"""
dacă x == None sau len(x) <= 3:
returnează Fals
altfel:
pentru i în intervalul(3, len(x)):

dacă (x[i-3] >= x[i-1]) ș i (x[i-2] <= x[i]):

return True
dacă (i >= 4) ș i (x[i-4] + x[i] >= x[i-2]) ș i (x
[i-3] == x[i-1]):
returnează adevărat

dacă (i>=5) ș i (x[i-5] <= x[i-3]) ș i (x[i-4] <=

x[i-2]) ș i (x[i-1] <= x[i-3]) ș i (x[i-1] >= x[i-3] - x[i-5]) a
nd (x[i] >= x[i-2] - x[i-4]) ș i (x[i] <= x[i-2]):
returnează Adevărat

întoarce False

207
Paint Fence

Vopseș te gardul

Există un gard cu n stâlpi, fiecare stâlp poate fi vopsit cu una dintre cele k culori.

Trebuie să vopseș ti toate stâlpii astfel încât să nu fie mai mult de două stâlpi de gard adjacenti.
au aceeaș i culoare.

Întoarce numărul total de moduri în care poț i vopsi gardul.

Notă: n ș i k sunt numere întregi non-negative.

URL:[Link]

clasa Solu ț ie (obiect):

def numWays(self, n, k):
"""
:tip n: int
:tip k: înt
:rtype: int
"""
dp = [0, k, k*k, 0]
dacă n <= 2:
return dp[n]
pentru i în intervalul(2, n):

dp[3] = (k-1)*(dp[1] + dp[2])

dp[1] = dp[2]
dp[2] = dp[3]

return dp[3]

208
Comutator de lămpi

Comutator de Becuri

Există n becuri care sunt iniț ial stinse. Mai întâi, aprinzi toate becurile. Apoi, stingi
opri fiecare a doua lampă. La a treia rundă, comuț i fiecare a treia lampă (pornind dacă
este oprit sau se opreș te dacă este pornit). Pentru a i-a rundă, schimbi starea fiecărei i lămpi. Pentru n-a
rotund, dai doar comutarea ultimei becuri. Găseș te câte becuri sunt aprinse după n runde.

Exemplu:

Dat n = 3.

La început, cele trei becuri sunt [stinse, stinse, stinse]. După prima rundă, cele trei becuri sunt [aprins,

on, on]. After second round, the three bulbs are [on, off, on]. After third round, the
trei becuri sunt [aprins, stins, stins].

Aș adar, ar trebui să returnezi 1, pentru că există doar o singură lampă aprinsă.

URL: [Link]

import matematică

clasa Solu ț ie (obiect):

def bulbSwitch(self, n):
"""
:tip n: int
:rtype: int
"""
return int([Link](n))

209
Jocul Nim

Jocul Nim
Joci următorul joc Nim cu prietenul tău: Există un teanc de
piatră pe masă, de fiecare dată când unul dintre voi îș i ia rândul să îndepărteze 1 până la 3 pietre. A

Cine îndepărtează ultima piatră va fi câș tigătorul. Vei face prima miș care pentru
îndepărtaț i pietrele.

Amândoi sunteț i foarte isteț i ș i aveț i strategii optime pentru joc.

funcț ie pentru a determina dacă poț i câș tiga jocul dat fiind numărul de pietre
în heap.

De exemplu, dacă sunt 4 pietre în grămadă, atunci nu vei câș tiga niciodată jocul:
indiferent dacă elimini 1, 2 sau 3 pietre, ultima piatră va fi întotdeauna eliminată de
prietenul tău.

Sfat:

Dacă sunt 5 pietre în grămadă, ai putea găsi o metodă de a îndepărta pietrele?

astfel încât să fii întotdeauna învingător?

URL:[Link]

clasă Solu ț ie(obiect):

def poateCâ ș tigaNim(self, n):
"""
:tip n: int
:rtype: bool
"""
întoarce n%4 != 0

210
Roteș te imaginea

Roteș te Imaginea

Vi se dă o matrice 2D de dimensiuni n x n care reprezintă o imagine.

Roteș te imaginea cu 90 de grade (în sensul acelor de ceasornic).

Urmărire: Poti face asta la faț a locului?

URL:[Link]

clasă Solu ț ie (obiect):

def roti(self, matrice):
"""
:tip matrice: Listă[Listă[int]]
:rtype: void Nu returna ț i nimic, modifica ț i matricea în pl.
AS ace în schimb.

"""
dacă matricea == None sau matricea == []:
trece
altfel:
n = len(matricei)
pentru strat în intervalul(0, n//2):

first = layer
ultimul = n - 1 - strat
pentru i în intervalul (primul, ultimul):

offset = i - prim
top = matrice[first][i]
matrix[first][i] = matrix[last - offset][fir
st]
matrix[last - offset][first] = matrix[last][
ultimul - offset]
matrix[last][last - offset] = matrix[i][last]
]
matrix[i][last] = sus

211
Setaț i matricea la zero

Setaț i matricea cu zerouri

Dată fiind o matrice de m x n, dacă un element este 0, setează întreaga sa linie ș i coloană la 0. Fă această operaț ie în

loc.

click pentru a arăta urmărirea.

Urmărire: Ai folosit spaț iu suplimentar? O soluț ie simplă folosind O(mn)

spaț iul este probabil o idee proastă. O îmbunătăț ire simplă foloseș te O(m + n) spaț iu, dar totuș i
nu este cea mai bună soluț ie. Ai putea să concepi o soluț ie cu spaț iu constant?

URL: [Link]

class Solution(object):
def setZeroes(self, matrice):
"""
:tip matrice: Lista[List[int]]
:rtype: void Nu returna ț i nimic, modifica ț i matricea pe loc
as în schimb.
"""
dacă matrice == None sau len(matrice) == 0:
trece
elif len(matricei) == 1 ș i len(matricei[0]) == 1:
trece
altfel:
rows_with_0 = [False]*len(matrix)
cols_with_0 = [False]*len(matrix[0])
pentru i în intervalul(len(matrice)):

for j in range(len(matrix[0])):
dacă matricea[i][j] == 0:
rows_with_0[i] = True
cols_with_0[j] = True

pentru i în intervalul(len(matricei)):

pentru j în intervalul(len(matrice[0])):

dacă rows_with_0[i] sau cols_with_0[j]:

matrix[i][j] = 0

212
Setaț i matricea la zero

Soluț ie cu spaț iu constant:

clasa Solu ț ie(object):

def setZeroes(self, matrice):
"""
:tip matrice: List[List[int]]
:rtype: void Nu returna ț i nimic, modifica ț i matricea în loc
as fin
"""
first_row = False
first_col = False

pentru j în interval(len(matrice[0])):
dacă matricea[0][j] == 0:
first_row = True

pentru i în intervalul(len(matrice)):

dacă matrice[i][0] == 0:
first_col = True

pentru i în intervalul(1, len(matrice)):

pentru j în intervalul(1, len(matrice[0])):

dacă matrice[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0

pentru i în intervalul(1, len(matrice)):

pentru j în range(1, len(matrice[0])):

dacă matrix[i][0] == 0 sau matrix[0][j] == 0:
matrice[i][j] = 0

dacă first_col:
pentru i în intervalul(len(matrice)):

matrice[i][0] = 0

dacă prima_linie:
pentru i în intervalul(len(matrix[0])):

matrix[0][i] = 0

213
Setaț i zerourile matricei

214
Căutare într-o matrice 2D

Cauta într-o matrice 2D

Scrieț i un algoritm eficient care caută o valoare într-o matrice m x n. Aceasta

matricea are următoarele proprietăț i:

Numerele întregi din fiecare rând sunt sortate de la stânga la dreapta. Primul număr întreg din fiecare rând este

mai mare decât ultimul întreg din rândul anterior. De exemplu,

Consideraț i următoarea matrice:

Dând ț inti = 3, returnează adevărat.

215
Caută într-o matrice 2D

clasa Solu ț ie (obiect):

def cautaMatrice(self, matrice, tinta):
"""
:tip matrice: List[List[int]]
:tip ț intă: int
:rtype: bool
"""
dacă matricea == []:
întoarce Fals
altfel:
no_rows = len(matrix)
no_cols = len(matrix[0])

ob ț ineț i primul element ș i ultimul element al m

atrix
compara ț i-l cu obiectivul
dacă ț inta < matrice[0][0] sau ț inta > matrice[nu_rânduri-
1][nu_coloane-1]:
returnează Fals

r = 0
c = număr_de_coloane - 1

în timp ce r < no_rows ș i c >= 0:

dacă target == matrice[r][c]:
returnează Adevărat

elif target > matrix[r][c]:

r += 1
elif target < matrice[r][c]:
c -= 1
returnează Fals

216
Căutarea într-o matrice 2D II

Căutare într-o matrice 2D II

Scrieț i un algoritm eficient care caută o valoare într-o matrice m x n. Aceasta

matricea are următoarele proprietăț i:

Numerele întregi din fiecare rând sunt sortate în ordine crescătoare de la stânga la dreapta. Numerele întregi din fiecare

coloanele sunt sortate în ordine crescătoare de sus în jos. De exemplu,

Consideraț i următoarea matrice:

[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23]]
Dat fiind că ț inta = 5, returnează adevărat.

Având ca ț intă = 20, returnează fals.

URL: [Link]

217
Caută o matrice 2D II

clasa Solu ț ie(object):

def searchMatrix(self, matrice, ț intă):
"""
:tip matrice: Listă[List[int]]
:tip ț intă: int
:rtype: bool
"""
dacă matricea == []:
întoarce Fals
altfel:
no_rows = len(matrix)
no_cols = len(matrix[0])

dacă ț inta < matrice[0][0] sau ț inta > matrice[nu_linii-

1][no_cols-1]:
returnează Fals
altfel:
r = 0
c = număr_coloane - 1

în timp ce r < numărul_liniilor ș i c >= 0:

dacă matricea[r][c] == ț intă:

returnează Adevărat

elif target > matrix[r][c]:

r += 1
elif target < matrix[r][c]:
c -= 1
returnează Fals

218
Matrice spirală

Matrice Spirală
Având o matrice cu m x n elemente (m rânduri, n coloane), returnaț i toate elementele ale
matrice în ordine spiralat.

De exemplu, având următoarea matrice:

[1,2,3,6,9,8,7,4,5]

URL:[Link]

clasă Solu ț ie(object):

def spiralaOrdine(self, matrice):
"""
:tip matrice: Listă[Listă[int]]
:rtype: List[int]
"""
dacă matricea == None sau matricea == []:
returna ț i matricea

altfel:
#număr de rânduri

m = len(matricei)
#numărul de coloane

n = len(matrice[0])
#rând de început
k = 0
#începând cu coloana
l = 0

matrice în ordine spirală

spiral = []

în timp ce k < m ș i l < n:

afi ș ează prima linie din rândurile rămase
pentru i în intervalul(l, n):

[Link](matrix[k][i])
k += 1

afi ș ează ultima coloană din coloanele rămase

219
Matrice Spirală

s
pentru i în intervalul(k, m):

[Link](matrix[i][n-1])
n-= 1

printa ț i ultima linie din rândurile rămase

dacă k < m:
pentru i în intervalul(n-1, l-1, -1):

[Link](matrice[m-1][i])

m -= 1

tipări ț i prima coloană din coloanele rămase

ns
dacă l < n:
pentru i în intervalul(m-1, k-1, -1):

[Link](matrice[i][l])

l += 1

returna ț i spirala

220
Matricea Spirală II

Matrice spirală II
Dat un număr întreg n, generează o matrice pătrată umplută cu elemente de la 1 la n2 în
ordine spiralată.

De exemplu, dat fiind n = 3,

Ar trebui să returnaț i următoarea matrice: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

URL:[Link]

clasă Solu ț ie(object):

def generateMatrix(self, n):
"""
:tip n: înt
:rtype: List[List[int]]
"""
dacă n == 0:
return []
în cazul în care n == 1:

[[1]]
altfel:
#numărul de rânduri

r = n
#numărul de coloane

c = n
#începutul rândului

k = 0
#începutul coloanei
l = 0

#alocare o matrice pătratică cu toate zerourile

matrix = [[0 for j in range(c)] for i in range(r)]
#numărător pentru elemente
count = 1

în timp ce k < r ș i l < c:

#umple ț i prima linie
pentru i în intervalul(l, c):

221
Matricea spirală II

matrix[k][i] = count
count += 1

k += 1

#umple ț i ultima coloană

pentru i în intervalul(k, r):

matrix[i][c-1] = count
count += 1

c -= 1

completează ultima linie

dacă k < r:
pentru i în intervalul(c-1, l-1, -1):

matrix[r-1][i] = count
count += 1
r -= 1

#umple prima coloană

dacă l < c:
pentru i în intervalul(r-1, k-1, -1):

matrix[i][l] = count
count += 1
l += 1

returna matricea

222
Design

223
Cache LRU

Cache LRU

Proiectaț i ș i implementaț i o structură de date pentru cache-ul cu cea mai puț in utilizată (LRU).

ar trebui să susț ină următoarele operaț iuni:ob ț ș iset.

ine

ob ț ine(key)- Obț ine valoarea (va fi întotdeauna pozitivă) a cheii dacă cheia există în
cache-ul, altfel returnaț i -1.
set(key, value) - Setează sau introdu valoarea dacă cheia nu este deja prezentă.
Când memoria cache a atins capacitatea sa, ar trebui să invalideze cel mai puț in folosit recent.
element înainte de inserarea unui nou element.

224
Cache LRU

clasă LRUCache(object):

def __init__(self, capacitate):

"""
:type capacity: int
"""
[Link] = capacity
[Link] = OrderedDict()

def get(self, cheie):

"""
:rtype: int
"""
dacă cheia este în [Link]:

value = [Link](key)
[Link][key] = valoare
valoare de returnat

altele:
returnează -1

def set(self, cheie, valoare):

"""
:type key: int
:tip valoare: int
:rtype: nimic
"""
dacă len([Link]) >= [Link] ș i cheia nu este în self.
cache:
[Link](last=False)
[Link][key] = value
altfel:
dacă cheia este în cache-ul meu:

[Link](key)
[Link][key] = value
altfel:
[Link][key] = value

225
Cache LRU

226