logo

TechCodeview

Uzziniet datu struktūras un algoritmus | DSA apmācība

Datu struktūras un algoritmi (DSA) attiecas uz datu organizēšanas un uzglabāšanas metožu izpēti un problēmu risināšanas procedūru (algoritmu) izstrādi, kas darbojas uz šīm datu struktūrām. DSA ir viena no svarīgākajām prasmēm, kas jāapgūst katram datorzinātņu studentam. Bieži tiek novērots, ka cilvēki, kuriem ir labas zināšanas par šīm tehnoloģijām, ir labāki programmētāji nekā citi, un tādējādi viņi intervijas ar gandrīz katru tehnoloģiju gigantu. Šis DSA apmācība mērķis ir palīdzēt jums ātri un viegli apgūt datu struktūras un algoritmus (DSA).



Satura rādītājs

  • Apgūstiet algoritmus
  • Uzziniet par sarežģījumiem
  • Praktizējiet problēmu apkrāpšanas lapas

    • DSA pilna veidlapa

    Termins DSA apzīmē Datu struktūras un algoritmi , Datorzinātņu kontekstā.

    Kas ir DSA?

    Datu struktūras un algoritmi (DSA) attiecas uz datu organizēšanas un uzglabāšanas metožu izpēti un problēmu risināšanas procedūru (algoritmu) izstrādi, kas darbojas uz šīm datu struktūrām.



    Kā iemācīties DSA?

    Pirmā un galvenā lieta ir visas procedūras sadalīšana mazos gabalos, kas jāveic secīgi. Visu DSA apguves procesu no jauna var iedalīt 5 daļās:

    1. Apgūstiet vismaz vienu programmēšanas valodu (šo mēs atstājam jūsu izvēlei.)
    2. Uzziniet datu struktūras
    3. Apgūstiet algoritmus
    4. Uzziniet par laika un telpas sarežģītību
    5. Prakses problēmas DSA
    Kā iemācīties DSA?

    Kā iemācīties DSA?

    Cerot, ka esat apguvis programmēšanas valodu pēc savas izvēles, ļaujiet mums veikt nākamo soli, lai apgūtu DMR šajā DSA pamācībā.



    Šeit ir datu struktūras un algoritma apguves ceļveža vissvarīgākais un gaidītākais posms — posms, kurā sākat mācīties par DMR. DSA tēma sastāv no divām daļām:

    • Datu struktūras
    • Algoritmi

    Lai gan tās ir divas dažādas lietas, tās ir ļoti savstarpēji saistītas, un ir ļoti svarīgi ievērot pareizo ceļu, lai tās apgūtu visefektīvāk. Ja jums ir neskaidrības par to, kuru mācīties vispirms, iesakām izpētīt mūsu detalizēto analīzi par šo tēmu: Šeit mēs esam sekojuši datu struktūras apguves plūsmai un pēc tam vissaistītākajiem un svarīgākajiem algoritmiem, ko izmanto šī datu struktūra.

    Uzziniet datu struktūras

    Datu struktūras ir būtiski komponenti, kas palīdz efektīvi organizēt un uzglabāt datus datora atmiņā. Tie nodrošina veidu, kā efektīvi pārvaldīt un manipulēt ar datiem, nodrošinot ātrāku piekļuvi, ievietošanu un dzēšanu. Kopējās datu struktūras ietver masīvi, saistītie saraksti, skursteņi, rindas, koki un diagrammas , katrs kalpo konkrētiem mērķiem, pamatojoties uz konkrētās problēmas prasībām. Izpratne par datu struktūrām ir būtiska, lai izstrādātu efektīvus algoritmus un optimizētu programmatūras veiktspēju.

    Masīvs ir lineāra datu struktūra, kas glabā viena un tā paša datu tipa elementu kolekciju. Elementiem tiek piešķirta blakus esošā atmiņa, kas nodrošina pastāvīgu piekļuvi. Katram elementam ir unikāls indeksa numurs.

    • Operācijas ar masīvu:
      • Šķērsošana : atkārtošana, izmantojot masīva elementus.
      • Ievietošana : elementa pievienošana masīvam ar noteiktu indeksu.
      • Dzēšana : elementa noņemšana no masīva noteiktā indeksā.
      • Meklēšana : elementa atrašana masīvā pēc tā vērtības vai indeksa.
    • Masīvu veidi :
      • Viendimensijas masīvs : vienkāršs masīvs ar vienu dimensiju.
      • Daudzdimensiju masīvs : masīvs ar vairākiem izmēriem, piemēram, matrica.
    • Masīva lietojumprogrammas :
      • Datu glabāšana secīgā veidā
      • Rindu, steku un citu datu struktūru ieviešana
      • Matricu un tabulu attēlošana
    • Saistītās tēmas par masīvu:
      • Masīvu apmācība
      • 50 populārākās masīvu kodēšanas problēmas intervijām
      • Prakses problēmas uz masīviem

    2. Stīga

    A virkne ir rakstzīmju secība, ko parasti izmanto teksta attēlošanai. To uzskata par datu tipu, kas ļauj manipulēt un apstrādāt teksta datus datorprogrammās.

    • Darbības ar virkni :
      • Savienošana : divu virkņu savienošana kopā.
      • Salīdzinājums : Divu stīgu salīdzināšana leksikogrāfiski.
      • Apakšvirkne ieguve : apakšvirknes izvilkšana no virknes.
      • Meklēt : tiek meklēta apakšvirkne virknē.
      • Modifikācija : rakstzīmju maiņa vai aizstāšana virknē.
    • Stīgu pielietojumi :
      • Teksta apstrāde
      • Rakstu saskaņošana
      • Datu validācija
      • Datu bāzes pārvaldība
    • Saistītās ziņas:
      • Stīgu apmācība
      • 50 populārākās virkņu kodēšanas problēmas intervijām
      • Praktizējiet problēmas ar stīgu

    3. Saistītie saraksti

    A saistītais saraksts ir lineāra datu struktūra, kas glabā datus mezglos, kas ir savienoti ar rādītājiem. Atšķirībā no masīviem saistītie saraksti netiek glabāti blakus esošās atmiņas vietās.

    • Saistītā saraksta īpašības:
      • Dinamisks : saistīto sarakstu izmērus var viegli mainīt, pievienojot vai noņemot mezglus.
      • Nepieguļošs : mezgli tiek saglabāti nejaušās atmiņas vietās un savienoti ar rādītājiem.
      • Secīgā piekļuve : mezgliem var piekļūt tikai secīgi, sākot no saraksta sākuma.
    • Darbības saistītajā sarakstā:
      • Radīšana : jauna saistītā saraksta izveide vai jauna mezgla pievienošana esošam sarakstam.
      • Šķērsošana : atkārtojiet sarakstu un piekļūstiet katram mezglam.
      • Ievietošana : jauna mezgla pievienošana noteiktā saraksta vietā.
      • Dzēšana : mezgla noņemšana no saraksta.
      • Meklēt : Mezgla atrašana ar noteiktu vērtību sarakstā.
    • Saistīto sarakstu veidi :
      • Atsevišķi saistītais saraksts : katrs mezgls norāda uz nākamo mezglu sarakstā.
      • Divkārši saistīts saraksts : katrs mezgls norāda gan uz nākamo, gan uz iepriekšējo saraksta mezglu.
      • Apļveida saistīto saraksts : Pēdējais mezgls norāda atpakaļ uz pirmo mezglu, veidojot apļveida cilpu.
    • Saistītā saraksta lietojumprogrammas :
      • Saistītie saraksti tiek izmantoti dažādās lietojumprogrammās, tostarp:
      • Rindu un steku ieviešana
      • Grafiku un koku attēlošana
      • Sakārtoto datu uzturēšana
      • Atmiņas pārvaldība
    • Saistītās tēmas:
      • Saistītā saraksta apmācība
      • 50 populārākās problēmas interviju saistītajā sarakstā
      • Praktizējiet problēmas saistītajos sarakstos

    4. Matrica/Režģis

    A matrica ir divdimensiju elementu masīvs, kas sakārtots rindās un kolonnās. Tas tiek attēlots kā taisnstūrveida režģis ar katru elementu rindas un kolonnas krustpunktā.

    • Galvenie jēdzieni:
      • Rindas : horizontālas elementu līnijas matricā.
      • Kolonnas : vertikālas elementu līnijas matricā.
      • Izmēri : rindu un kolonnu skaits matricā (piemēram, 3 × 4 matricai ir 3 rindas un 4 kolonnas).
      • Elements Piekļuve : elementiem var piekļūt, izmantojot rindu un kolonnu indeksus (piemēram, M[2][3] attiecas uz elementu 2. rindā, 3. kolonnā).
    • Matrix/Grid pielietojumi :
      • Attēlu apstrāde
      • Datu analīze
      • Optimizācijas problēmas
    • Saistītās ziņas:
      • Matricas/režģa apmācība
      • 50 populārākās problēmas intervijām matricā/režģī
      • Prakses problēmas matricā/režģī

    5. Kaudze

    Kaudze ir lineāra datu struktūra, kas atbilst noteiktai secībai, kādā tiek veiktas darbības. Pasūtījums var būt LIFO (pēdējais iekšā pirmais) vai FILO (First In Last Out) . LIFO nozīmē, ka elements, kas ievietots pēdējais, iznāk pirmais un RINDA nozīmē, ka elements, kas ievietots pirmais, iznāk pēdējais.

    • Darbība uz Stack :
      • Spiediet : pievieno elementu kaudzes augšpusē
      • Pop : noņem un atgriež elementu kaudzes augšpusē
      • Palūrēt : atgriež elementu kaudzes augšpusē, to nenoņemot
      • Izmērs : atgriež elementu skaitu kaudzē
      • Ir tukšs : pārbauda, ​​vai kaudze ir tukša
    • Stack lietojumprogrammas :
      • Funkciju izsaukumi
      • Izteiksmes novērtējums
      • Atkāpšanās
      • Atsaukt/atcelt darbības
    • Saistītās tēmas par Stack:
      • Stack apmācība
      • 50 populārākās problēmas interviju komplektā
      • Praktizējiet problēmas vietnē Stack

    6. Rinda

    A Rinda Datu struktūra ir pamatjēdziens datorzinātnēs, ko izmanto datu glabāšanai un pārvaldībai noteiktā secībā. Tas izriet no principa Pirmais iekšā, pirmais ārā ( FIFO ), kur pirmais rindai pievienotais elements ir pirmais, kas tiek noņemts

    • Darbība rindā :
      • Rindā : pievieno elementu rindas aizmugurē
      • Attiecīgi : noņem elementu no rindas priekšpuses
      • Palūrēt : izgūst priekšējo elementu, to nenoņemot
      • Ir tukšs : pārbauda, ​​vai rinda ir tukša
      • Ir pilns : pārbauda, ​​vai rinda ir pilna
    • Rindas veids :
      • Apļveida rinda : pēdējais elements savienojas ar pirmo elementu
      • Divu galu rinda (atkāpšanās) : Darbības var veikt no abiem galiem
      • Prioritātes rinda : elementi ir sakārtoti, pamatojoties uz prioritāti
    • Rindas lietojumprogrammas :
      • Darba plānošana
      • Ziņojumu rinda
      • Simulācijas modelēšana
      • Datu buferizācija
    • Saistītās tēmas:
      • Rindas apmācība
      • 50 populārākās problēmas interviju rindā
      • Praktizējiet problēmas rindā

    7. Kaudze

    A Kaudze ir pilnīga binārā koka datu struktūra, kas apmierina kaudzes īpašību: katram mezglam tā atkritumu vērtība ir mazāka vai vienāda ar tā vērtību. Lai īstenotu, parasti izmanto kaudzes prioritārās rindas , kur mazākais (vai lielākais) elements vienmēr atrodas koka saknē.

    • Kaudzes darbības :
      • Ievietot : pievieno kaudzītei jaunu elementu, vienlaikus saglabājot kaudzes īpašības.
      • Extract-Max/Extract-Min : noņem saknes elementu un pārstrukturē kaudzi.
      • Palielināšanas/samazināšanas taustiņš : atjaunina mezgla vērtību un pārstrukturē kaudzi.
    • Kaudzes veidi :
      • Max-Heap : saknes mezglam ir maksimālā vērtība starp bērniem.
      • Min-Heap : saknes mezglam ir minimālā vērtība starp bērniem.
    • Heap pielietojumi :
      • Prioritārās rindas
      • Šķirošana
      • Grafiku algoritmi (piemēram, Dijkstra algoritms)
    • Saistītās ziņas:
      • Kaudzes apmācība
      • 50 populārākās interviju problēmas vietnē Heap
      • Prakses problēmas uz Heap

    8. Hash

    Jaukšana ir paņēmiens, kas ģenerē fiksēta izmēra izvadi (jaucējvērtību) no mainīga lieluma ievades, izmantojot matemātiskas formulas, ko sauc hash funkcijas . Jaukšanu izmanto, lai noteiktu indeksu vai vietu vienuma glabāšanai datu struktūrā, kas ļauj efektīvi izgūt un ievietot.

    • Galvenie jēdzieni:
      • Jaucējfunkcija : matemātiska funkcija, kas kartē ievadi ar jaucējvērtību.
      • Hash tabula : datu struktūra, kurā tiek glabāti atslēgu un vērtību pāri, kur atslēga ir jaucējvērtība, bet vērtība ir faktiskie dati.
      • Sadursme : ja divas dažādas atslēgas rada vienādu jaucējvērtību.
    • Jaucējfunkciju veidi :
      • Sadalīšanas metode : dala ievadi ar konstanti un izmanto atlikumu kā jaucējvērtību.
      • Vidus laukums Metode: kvadrātveida ievade un ņem vidējos ciparus kā jaucējvērtību.
      • Salocīšanas metode : sadala ievadi vienāda lieluma blokos un saskaita tos kopā, lai iegūtu jaucējvērtību.
      • Reizināšanas metode : reizina ievadi ar konstanti un kā jaukšanas vērtību izmanto daļēju daļu.
    • Sadursmju risināšanas metodes :
      • Atsevišķa ķēde (atvērta jaukšana) : saglabā sadursmes elementus saistītā sarakstā ar atbilstošo jaucējvērtību.
      • Atvērta adresēšana (slēgta jaukšana) : izmanto dažādas stratēģijas, lai atrastu alternatīvu vietu sadursmes elementiem hash tabulā.
    • Jaukšanas lietojumprogrammas :
      • Efektīva datu glabāšana un izguve datu bāzēs un failu sistēmās.
      • Paroļu un ciparparakstu pārbaude.
      • Pieprasījumu izplatīšana vairākos serveros.
      • Drošu jaucēju ģenerēšana datu integritātei un autentifikācijai.
    • Saistītās ziņas:
      • Hash apmācība
      • Prakses problēmas saistībā ar jaukšanu

    9. Koks

    A koks ir nelineāra hierarhiska datu struktūra, kas sastāv no mezgliem, kas savienoti ar malām, ar augšējo mezglu, ko sauc par sakni, un mezgliem ar pakārtotiem mezgliem. To izmanto datorzinātnēs, lai efektīvi organizētu datus.

    izvēlieties no vairākām SQL tabulām
    • Koka šķērsošana : Koku šķērsošanas metodes tiek izmantotas, lai apmeklētu un apstrādātu mezglus koka datu struktūrā. Trīs izplatītākās pārvietošanās metodes ir:
      • Kārtībā : Apmeklējiet kreiso apakškoku, pašreizējo mezglu, pēc tam labo apakškoku.
      • Iepriekšpasūtījums : Apmeklējiet pašreizējo mezglu, kreiso apakškoku, pēc tam labo apakškoku.
      • Pēc pasūtījuma : Apmeklējiet kreiso apakškoku, labo apakškoku un pēc tam pašreizējo mezglu.
    • Koku klasifikācija:
      • Klasifikācijas no Koki attiecas uz koku grupēšanu, pamatojoties uz noteiktiem raksturlielumiem vai kritērijiem. Tas var ietvert koku klasificēšanu kategorijās, pamatojoties uz to līdzsvara koeficientu, mezglu pakāpi, secības īpašībām utt. Tālāk ir sniegta dažas svarīgas Tree klasifikācijas.
    Klasifikācija Apraksts

    Tips

    Apraksts

    Pēc grāda

    Kokus var klasificēt, pamatojoties uz maksimālo bērnu skaitu, kas var būt katram mezglam.

    Binārais koks

    Katram mezglam ir ne vairāk kā divi bērni.

    Trīskāršais koks

    Katram mezglam ir ne vairāk kā trīs bērni.

    N-ary Tree

    Katram mezglam ir ne vairāk kā N bērni.

    Pasūtot

    Koki var klasificēt, pamatojoties uz mezglu un apakškoku secību

    Binārais meklēšanas koks (BST)

    Kreisais bērns

    Kaudze

    Specializēts binārais koks ar kaudzes īpašumu.

    Pēc bilances

    Kokus var klasificēt atkarībā no tā, cik labi tie ir līdzsvaroti.

    Līdzsvarots koks

    Apakškoku augstumi atšķiras ne vairāk kā par vienu. Piemēri ir AVL koki un sarkanmelnie koki.

    Nesabalansēts koks

    Apakškoku augstums var ievērojami atšķirties, ietekmējot tādu darbību veiktspēju kā meklēšana un ievietošana.
    • Koku pielietojumi:
      • Failu sistēmas
      • Datu bāzes
      • XML dokumenti
      • Mākslīgais intelekts
    • Saistītās ziņas:
      • Koku apmācība
      • 50 populārākās koku kodēšanas problēmas
      • Praktizējiet problēmas uz koka

    10. Grafiks

    A Grafiks ir nelineāra datu struktūra, kas sastāv no ierobežotas virsotņu (vai mezglu) kopas un malu kopas, kas savieno mezglu pāri.

    Apgūstiet algoritmus

    Kad esat notīrījis jēdzienus Datu struktūras , tagad ir pienācis laiks sākt savu ceļojumu cauri Algoritmi . Pamatojoties uz rakstura un lietojuma veidu, algoritmi ir sagrupēti vairākās kategorijās, kā parādīts tālāk.

    1. Meklēšanas algoritms

    Meklēšanas algoritmi tiek izmantoti, lai atrastu konkrētus datus lielākā datu kopā. Tas palīdz atrast mērķa vērtību datos. Ir dažādi meklēšanas algoritmu veidi, katram ir sava pieeja un efektivitāte.

    • Visizplatītākie meklēšanas algoritmi:
      • Lineārā meklēšana : iteratīva meklēšana no viena gala līdz otram.
      • Binārā meklēšana : sadali un pārvaldi meklēšana sakārtotā masīvā, katrā iterācijā meklēšanas vietu samazinot uz pusi.
      • Trīskāršā meklēšana : sadaliet un pārvaldiet meklēšanu sakārtotā masīvā, sadalot meklēšanas telpu trīs daļās katrā iterācijā.
    • Citi meklēšanas algoritmi:
      • Pārlēkt meklēšanu
      • Interpolācijas meklēšana
      • Eksponenciālā meklēšana
    • Saistītās tēmas:
      • Praktizējiet meklēšanas algoritma problēmas

    2. Šķirošanas algoritms

    Šķirošanas algoritmi tiek izmantoti, lai sakārtotu saraksta elementus noteiktā secībā, piemēram, ciparu vai alfabētiskā secībā. Tas sistemātiski organizē vienumus, atvieglojot konkrētu elementu meklēšanu un piekļuvi tiem.

    Ir daudz dažādu šķirošanas algoritmu veidu. Daži plaši izmantoti algoritmi ir:

    Šķirošanas algoritms Apraksts
    Burbuļu kārtošana Iteratīvi salīdzina blakus esošos elementus un apmaina tos, ja tie nav kārtībā. Lielākais elements ar katru piegājienu tiek burbuļots līdz saraksta beigām.
    Atlase Kārtot Atrod minimālo elementu saraksta nešķirotajā daļā un apmaina to ar pirmo elementu. Atkārto šo procesu, līdz viss saraksts ir sakārtots.
    Ievietošanas kārtošana Veido sakārtoto sarakstu pa vienam elementam, ievietojot katru nešķiroto elementu pareizajā pozīcijā kārtotajā daļā.
    Ātrā kārtošana Sadaliet un pārvaldiet algoritms, kas atlasa rakursta elementu, sadala sarakstu divos apakšsarakstos, pamatojoties uz rakursu, un rekursīvi piemēro to pašu procesu apakšsarakstiem.
    Sapludināt Kārtot Vēl viens sadalīšanas un iekarošanas algoritms, kas rekursīvi sadala sarakstu mazākos apakšsaraklos, sakārto tos un pēc tam atkal apvieno, lai iegūtu sakārtoto sarakstu.

    Saistītās tēmas:

    • Kārtošanas algoritma apmācība
    • Populārākie interviju jautājumi un problēmas
    • Praktizējiet kārtošanas algoritma problēmas

    3. Skaldi un valdi algoritms

    Sadali un iekaro algoritmi izmanto rekursīvu stratēģiju, lai atrisinātu problēmas, sadalot tās mazākās apakšproblēmās, atrisinot šīs apakšproblēmas un apvienojot risinājumus, lai iegūtu galīgo risinājumu.

    Darbības:

    1. Sadaliet : sadaliet problēmu mazākās, neatkarīgās apakšproblēmās.
    2. Iekarot : Rekursīvi atrisiniet katru apakšproblēmu.
    3. Apvienot : Apvienojiet apakšuzdevumu risinājumus, lai iegūtu galīgo risinājumu.

    Piemēri:

    • Sapludināt kārtot: sadala masīvu divās daļās, sakārto katru pusi rekursīvi un sapludina sakārtotās puses.
    • Ātrā kārtošana: atlasa pagrieziena elementu, sadala masīvu divās apakšmasīvās, pamatojoties uz šarnīra punktu, un rekursīvi kārto katru apakšmasu.
    • Binārā meklēšana: atkārtoti sadala meklēšanas laukumu uz pusēm, līdz tiek atrasts mērķa elements vai meklēšanas vieta ir izsmelta.

    Saistītie raksti:

    • Skaldi un valdi apmācība
    • Praktizējiet problēmas sadaliet un valdiet algoritmā

    4. Mantkārīgie algoritmi

    Kā norāda nosaukums, šis algoritms veido risinājumu pa vienam un izvēlas nākamo daļu, kas dod visredzamāko un tūlītējāko labumu, t.i., kas ir optimālākā izvēle tajā brīdī. Tātad problēmas, kurās lokāli optimālā izvēle rada arī globālus risinājumus, vislabāk atbilst Greedy.

    Dažas svarīgas mantkārīgo algoritmu problēmas ir:

    Algoritms Apraksts
    Daļēja mugursoma Atrodiet to priekšmetu maksimālo kopējo vērtību, ko var ievietot mugursomā, ļaujot priekšmetus iekļaut daļēji.
    Dijkstras algoritms Atrod īsāko ceļu no avota virsotnes uz visām pārējām virsotnēm svērtā grafikā.
    Kruskala algoritms Atrod svērtā grafika minimālo aptverošo koku.
    Hafmena kodēšana Izveido optimālu prefiksa kodu simbolu kopai, samazinot kopējo kodēšanas garumu.

    Saistītie raksti:

    • Mantkārīgā algoritma apmācība
    • Praktizējiet problēmas, izmantojot Greedy algoritmu

    5. Rekursija

    Rekursija ir programmēšanas tehnika, kurā funkcija sevi izsauc savas definīcijas ietvaros. To parasti izmanto, lai atrisinātu problēmas, kuras var sadalīt mazākos vienas un tās pašas problēmas gadījumos. Piemēram: Hanojas torņi (TOH) , Faktoriskais aprēķins un Fibonači secība utt.

    Soļi :

    • Pamatlieta : definējiet nosacījumu, kas aptur rekursīvos zvanus un nodrošina risinājumu.
    • Rekursīvs gadījums : definējiet darbības, lai sadalītu problēmu mazākos gadījumos un veiktu rekursīvus zvanus.
    • Atgriezties : atgrieziet risinājumu no rekursīvajiem zvaniem un apvienojiet tos, lai atrisinātu sākotnējo problēmu.

    Fakts, kas padara Recursion par vienu no visbiežāk izmantotajiem algoritmiem, ir tas, ka tas veido pamatu daudziem citiem algoritmiem, piemēram, Koku šķērsošana , Grafiku šķērsošanas , Dali un uzvar algoritmi un Atkāpšanās algoritmi .

    Saistītās tēmas:

    • Rekursijas apmācība
    • Rekursīvās funkcijas
    • Astes rekursija
    • 50 populārākās problēmas saistībā ar intervijas rekursijas algoritmu
    • Praktizējiet problēmas ar rekursijas algoritmu

    6. Atkāpšanās algoritms

    Kā minēts iepriekš, Atkāpšanās Algoritms ir atvasināts no Recursion algoritma, ar iespēju atgriezties, ja rekursīvs risinājums neizdodas, t.i., ja risinājums neizdodas, programma izseko līdz brīdim, kad tas neizdevās, un izmanto citu risinājumu. Tātad būtībā tas izmēģina visus iespējamos risinājumus un atrod pareizo.

    Dažas svarīgas un visizplatītākās atkāpšanās algoritmu problēmas, kas jums jāatrisina, pirms turpināt, ir:

    Problēma Apraksts
    Bruņinieka tūres problēma Atrodiet bruņinieka gājienu secību uz šaha dēļa, lai tas apmeklētu katru laukumu tieši vienu reizi.
    Žurka labirintā Ceļa atrašana no sākuma pozīcijas līdz izejai labirintā ar šķēršļiem, kas attēloti kā sienas.
    N-Queen problēma N dāmu novietošana uz N × N šaha galda tā, lai divas dāmas neuzbruktu viena otrai.
    Apakškopas summas problēma Nosakot, vai eksistē dotās kopas apakškopa ar noteiktu summu.
    Sudoku 9 × 9 režģa mīklas atrisināšana ar cipariem no 1 līdz 9 tā, lai katrā rindā, kolonnā un 3 × 3 apakšrežģī būtu visi cipari bez atkārtošanās.

    Saistīts raksts:

    • Atkāpšanās apmācība
    • Praktizējiet problēmas, izmantojot atkāpšanās algoritmu

    7. Dinamiskā programmēšana

    Dinamiskā programmēšana ir metode, ko izmanto matemātikā un datorzinātnēs, lai atrisinātu sarežģītas problēmas, sadalot tās vienkāršākos apakšproblēmās. Atrisinot katru apakšproblēmu tikai vienu reizi un saglabājot rezultātus, tas ļauj izvairīties no liekiem aprēķiniem, tādējādi radot efektīvākus risinājumus plašam problēmu lokam.

    Galvenie jēdzieni:

    • Optimāla apakšstruktūra : Problēmas optimālo risinājumu var konstruēt no optimālajiem risinājumiem līdz tās apakšproblēmām.
    • Apakšproblēmas, kas pārklājas : Apakšproblēmas bieži atkārtojas lielākā problēmā, kā rezultātā tiek veikti lieki aprēķini.
    • Memoizācija / Tabulēšana : apakšproblēmu risinājumu glabāšana, lai izvairītos no pārrēķināšanas.

    Dažas svarīgas un visizplatītākās dinamiskās programmēšanas algoritmu problēmas, kas jums jāatrisina, pirms turpināt, ir:

    Problēma Apraksts
    Fibonači secība Fibonači skaitļu ģenerēšana, izmantojot dinamisko programmēšanu, lai izvairītos no liekiem aprēķiniem.
    Garākā kopējā secība Divām sekvencēm kopīgās garākās apakšsecības atrašana.
    Visilgākā pieaugošā secība Dotās secības garākās apakšsecības atrašana, kurā elementi ir sakārtoti augošā secībā.
    0/1 mugursomas problēma Maksimālās vērtības noteikšana, ko var iegūt, izvēloties preces ar norādīto svaru un vērtībām, vienlaikus nepārsniedzot noteikto svara ierobežojumu.
    Stieņa griešanas problēma Peļņas maksimizēšana, sagriežot noteikta garuma stieni gabalos un pārdodot tos par norādītajām cenām.
    Monētu maiņas problēma Noteikt veidus, kā veikt izmaiņas par noteiktu summu, izmantojot noteiktu monētu nominālvērtību kopu.
    Rediģēt attālumu Atrodiet minimālo darbību skaitu (ievietošana, dzēšana, aizstāšana), kas nepieciešams vienas virknes pārvēršanai citā.
    Apakškopas summas problēma Nosakot, vai pastāv noteiktas kopas apakškopa ar noteiktu summu.
    Garākā palindromiskā secība Dotās secības garākās apakšsecības atrašana, kas ir palindroms.
    Maksimālā Subarray summa Blakus esošā apakšmasīva atrašana ar lielāko summu noteiktā viendimensijas masīvā.
    Sadalījuma vienāda apakškopas summa Nosakot, vai ir iespējams sadalīt doto kopu divās apakškopās ar vienādu summu.
    Minimālo izmaksu ceļš Minimālo izmaksu ceļa atrašana no noteiktā režģa augšējā kreisā stūra līdz apakšējam labajam stūrim.
    Maksimālā produkta apakšgrupa Blakus esošā apakšmasīva atrašana ar lielāko reizinājumu noteiktā viendimensijas masīvā.

    Saistītie raksti:

    • Tabulēšana pret memoizāciju
    • Kā atrisināt dinamiskās programmēšanas problēmu?
    • Dinamiskās programmēšanas apmācība
    • 50 populārākās dinamiskās programmēšanas kodēšanas problēmas intervijām
    • Praktizējiet problēmas dinamiskās programmēšanas algoritmā

    8. Grafiku algoritmi :

    Grafu algoritmi datu struktūrās un algoritmos (DSA) ir paņēmienu un metožu kopums, ko izmanto, lai atrisinātu problēmas, kas saistītas ar grafiem, kas ir mezglu un malu kolekcija. Šie algoritmi ir paredzēti dažādu operāciju veikšanai ar grafikiem, piemēram meklēt, šķērsot, atrast īsāko ceļu , un nosakot savienojamība . Tie ir būtiski, lai atrisinātu dažādas reālas problēmas, tostarp tīkla maršrutēšanu, sociālo tīklu analīzi un resursu piešķiršanu.

    Temats

    Tēmas apraksts

    		 Algoritms Algoritma apraksts
    Grafika šķērsošana

    Paņēmieni visu grafa virsotņu apmeklēšanai.

    		 Dziļuma pirmā meklēšana (DFS) Izpētiet, cik vien iespējams, pa katru atzaru pirms atkāpšanās.
    Pirmā meklēšana (BFS) Izpēta kaimiņu virsotnes, pirms pāriet uz nākamo virsotņu līmeni.

    Minimālie koki

    Minimālie koki ir mazākie koki, kas savieno visus grafa mezglus, neveidojot ciklus, ko panāk, pievienojot īsākās iespējamās malas.

    Kruskala algoritms

    Tas atrod savienotā svērtā grafika minimālo aptverošo koku. Tas pievieno mazāko svara malu, kas neveido ciklu.

    Prima algoritms

    rdbms normalizācija

    Tas arī atrod minimālo aptverošo koku savienotam svērtajam grafikam. Tas pievieno mazāko svara malu, kas savieno divus kokus.
    Topoloģiskā šķirošana

    Topoloģiskā kārtošana ir lineāra virsotņu sakārtošana virzītā acikliskā grafā (DAG) tā, ka katrai virzītai malai no virsotnes u līdz virsotnei v u secībā ir pirms v.

    		 Kāna algoritms Kāna algoritms atrod virzīta acikliskā grafika (DAG) topoloģisko secību.
    Uz DFS balstīts algoritms Uz DFS balstīts algoritms izmanto dziļuma meklēšanu, lai veiktu topoloģisko kārtošanu virzītā acikliskā grafikā (DAG).

    Īsākais ceļš

    Īsākais ceļš grafā ir ceļš starp divām grafa virsotnēm, kurām ir minimālā svaru summa gar malām, salīdzinot ar visiem pārējiem ceļiem starp tām pašām divām virsotnēm.

    Dijkstras algoritms

    Mantkārīgs algoritms, lai atrastu īsāko ceļu starp visiem mezgliem O(E * V logV) laikā.

    Floida-Varšala algoritms

    Atrod īsāko ceļu starp visiem mezglu pāriem O(V^3) laikā.

    Bellman Ford algoritms

    Atrod īsāko ceļu no viena avota O(V * E) laikā.

    Džonsona algoritms

    Atrod īsākos ceļus starp visiem virsotņu pāriem O(V^2 logV + V * E) laikā.

    Cieši saistīti komponenti

    Virzīta grafa stingri savienots komponents (SCC) ir maksimāla virsotņu kopa, kurā ir ceļš no katras kopas virsotnes uz katru otro kopas virsotni.

    Kosaraju algoritms

    Kosaraju algoritms ir divu pakāpju algoritms, kas efektīvi atrod virzīta grafika cieši saistītus komponentus (SCC).

    Tarjana algoritms

    Tarjana algoritms ir vēl viens efektīvs algoritms SCC atrašanai virzītā grafikā

    Saistītās tēmas:

    • Grafika apmācība
    • 50 populārākās grafiku kodēšanas problēmas intervijām
    • Grafu algoritmu prakses problēma

    9 . Rakstu meklēšana

    Rakstu meklēšana ir DSA pamatpaņēmiens, ko izmanto, lai atrastu konkrēta raksta gadījumus noteiktā tekstā.

    Tālāk ir sniegti daži standarta modeļu meklēšanas algoritmi.

    Algoritms Apraksts Laika sarežģītība
    Brutālu spēku Tas salīdzina modeli ar katru teksta apakšvirkni O(mn)
    Knuts-Mors-Prets Tas izmanto iepriekš aprēķinātu atteices funkciju, lai izlaistu nevajadzīgus salīdzinājumus O(m + n)
    Bojers-Mūrs Tas salīdzina modeli no labās uz kreiso pusi, izlaižot rakstzīmes, pamatojoties uz pēdējo neatbilstību O(mn)
    Rabins-Karps Tas izmanto jaukšanu, lai ātri pārbaudītu iespējamās atbilstības O(m + n)

    Saistītās tēmas:

    • Rakstu meklēšanas apmācība
    • Prakses problēma ieslēgta Rakstu meklēšana

    10 . Matemātiskie algoritmi

    Matemātiskie algoritmi ir algoritmu klase, kas atrisina ar matemātiskiem jēdzieniem saistītas problēmas. Tos plaši izmanto dažādās jomās, tostarp datorgrafikā, skaitliskā analīzē, optimizācijā un kriptogrāfijā.

    Algoritms Apraksts
    GCD un LCM Atrodiet divu skaitļu lielāko kopīgo dalītāju un mazāko kopējo daudzkārtni.
    Galvenā faktorizācija Sadaliet skaitli tā primārajos faktoros.
    Fibonači skaitļi Izveidojiet Fibonači secību, kur katrs skaitlis ir divu iepriekšējo skaitļu summa.
    Katalonijas numuri Saskaitiet derīgo izteiksmju skaitu ar noteiktu iekavu pāru skaitu.
    Moduļu aritmētika Veiciet aritmētiskās darbības ar skaitļiem, kas modulē noteiktu vērtību.
    Eilera Totienta funkcija Saskaitiet to pozitīvo veselo skaitļu skaitu, kas ir mazāki par doto skaitli, kas ir relatīvi pirmskaitļi.
    nCr aprēķini Aprēķiniet binomiālo koeficientu, kas atspoguļo veidu skaitu, kā izvēlēties r elementus no n elementu kopas.
    Pirmskaitļi un pirmskaitļi Nosakiet, vai dots skaitlis ir pirmskaitļi, un efektīvi atrodiet pirmskaitļus.
    Sietu algoritmi Atrodiet visus pirmskaitļus līdz noteiktai robežai.

    Saistītās tēmas:

    • Matemātiskā algoritma prakses uzdevums

    11. Ģeometriskie algoritmi

    Ģeometriskie algoritmi ir algoritmu klase, kas atrisina ar ģeometriju saistītas problēmas. Ģeometriskie algoritmi ir būtiski, lai atrisinātu dažādas datorzinātnes problēmas, piemēram:

    Algoritms Apraksts
    Izliekts korpuss Atrod mazāko izliekto daudzstūri, kas satur punktu kopu.
    Tuvākais punktu pāris Atrod divus punktus kopā, kas atrodas vistuvāk viens otram.
    Līnijas krustojums Nosaka, vai divas taisnes krustojas, un, ja tā, atrod krustošanās punktu.
    Punkts daudzstūrī Nosaka, vai dotais punkts atrodas daudzstūra iekšpusē vai ārpus tā.

    Saistītās tēmas:

    • Ģeometrisko algoritmu prakses uzdevums

    12. Bitu algoritmi

    Bitu algoritmi ir algoritmi, kas darbojas ar atsevišķiem skaitļu bitiem. Šie algoritmi manipulē ar skaitļu bināro attēlojumu, lai veiktu tādus uzdevumus kā bitu manipulācijas, bitu loģiskās darbības (UN, VAI, XOR), pārslēdzošie biti , un iestatījumu vai noteiktu bitu notīrīšana numura ietvaros. Parasti tiek izmantoti bitu algoritmi zema līmeņa programmēšanas, kriptogrāfijas un optimizācijas uzdevumi kur nepieciešama efektīva manipulācija ar atsevišķiem bitiem.

    Temats Apraksts
    Bitu maiņa Pārbīda bitus pa kreisi vai pa labi par noteiktu pozīciju skaitu.
    Pārbīde pa kreisi (<<) Pārbīda bitus pa kreisi, efektīvi reizinot skaitli ar 2.
    Labā maiņa (>>) Pārbīda bitus pa labi, faktiski dalot skaitli ar 2.
    Izvilkt bitus Masku izmantošana konkrētu bitu iegūšanai no vesela skaitļa.
    Iestatīšanas biti Masku izmantošana, lai noteiktus bitus iestatītu uz 1 veselā skaitlī.
    Tīrīšanas biti Masku izmantošana, lai noteiktus bitus iestatītu uz 0 veselā skaitļā.
    Pārslēgšanas biti Izmantojot XOR (^), lai pārslēgtu noteiktus bitus veselā skaitļā.
    Skaitīšana Komplekta biti Iestatīto bitu skaita (1s) skaitīšana veselā skaitlī.

    Saistītās tēmas:

    • Bitu algoritmu apmācība
    • Praktiskās problēmas ar bitu algoritmiem

    13. Randomizēti algoritmi

    Randomizēti algoritmi ir algoritmi, kas problēmu risināšanai izmanto nejaušību. Viņi izmanto nejaušu ievadi, lai sasniegtu savus mērķus, bieži vien radot vienkāršākus vai efektīvākus risinājumus.

    Randomizēto algoritmu veidi:

    • Lasvegasa : vienmēr rada pareizu rezultātu, bet darbības laiks ir nejaušs.
    • Montekarlo : var radīt nepareizu rezultātu ar nelielu varbūtību, taču darbības laiks parasti ir ātrāks.

    Svarīgi algoritmi, kuros tiek izmantoti nejaušināšanas algoritmi:

    Algoritms Apraksts
    QuickSort Randomizēts šķirošanas algoritms ar vidējo gadījuma laika sarežģītību O(n log n).
    Izlaist sarakstu Randomizēta datu struktūra, kas nodrošina ātras meklēšanas un ievietošanas darbības.
    Bloom filtrs Varbūtības datu struktūra efektīvai kopas dalības pārbaudei.

    14. Atzarojuma un saistīšanas algoritms

    The Atzarojuma un saistīšanas algoritms ir metode, ko izmanto kombinatoriskās optimizācijas uzdevumos, lai sistemātiski meklētu labāko risinājumu. Tas darbojas, sadalot problēmu mazākās apakšproblēmās vai atzaros un pēc tam likvidējot noteiktas atzaras, pamatojoties uz optimālā risinājuma robežām. Šis process turpinās, līdz tiek atrasts labākais risinājums vai ir izpētītas visas filiāles.

    Standarta problēmas zaru un saistīšanas algoritmā:

    Unikāla problēma Apraksts
    0/1 Mugursoma, izmantojot atzarojumu un saiti Nozares ieviešanas detaļas un saistītā pieeja 0/1 mugursoma problēmas risināšanai.
    0/1 Mugursoma, izmantojot zemāko izmaksu atzaru un ierobežojumu 0/1 mugursomas problēmas atrisināšana, izmantojot viszemāko izmaksu atzaru un saistīšanas paņēmienu.
    8 mīkla Problēma, izmantojot atzarojumu un saiti Pielietojums filiāle un pienākums atrisināt 8 puzzle problēma, populārs bīdāmās puzzle spēle.
    N Queen Problēma, izmantojot atzarojumu un saiti Izmantojot atzaru un pienākums atrast risinājumus N Queens problēmai, kas ir klasiska šaha problēma.

    Saistītās tēmas:

    • Atzaru un saistošo algoritmu apmācība

    Uzziniet par sarežģījumiem

    Datu struktūrās un algoritmos (DSA) galvenais mērķis ir efektīvi un produktīvi atrisināt problēmas. Lai noteiktu programmas efektivitāti, mēs aplūkojam divu veidu sarežģītības:

    1. Laika sarežģītība : tas mums norāda, cik daudz laika nepieciešams mūsu koda palaišanai.
    2. Kosmosa sarežģītība : Tas norāda, cik daudz atmiņas patērē mūsu kods.

    Asimptotiskais apzīmējums :

    Lai salīdzinātu algoritmu efektivitāti, mēs izmantojam asimptotisko apzīmējumu, matemātisko rīku, kas novērtē laiks balstoties uz ievades lielums nepalaižot kodu. Tas koncentrējas uz programmas pamatoperāciju skaitu.

    pievienoties mysql atjauninājumam
    Apzīmējums Apraksts
    Big-O (Ο) Apraksta sliktākā gadījuma scenāriju, nodrošinot algoritma augšējo laika robežu.
    Omega (Ω) Apraksta labāko scenāriju, piedāvājot zemāku algoritma laika ierobežojumu.
    Teta (θ) Atspoguļo algoritma algoritma vidējo sarežģītību.

    Koda analīzei visbiežāk izmantotais apzīmējums ir Lielais O apzīmējums , kas nodrošina darbības laika vai atmiņas lietojuma augšējo ierobežojumu attiecībā uz ievades lielumu.

    Saistītās tēmas:

    Praktizējiet problēmu apkrāpšanas lapas:

    Problēmu saraksti no tālāk norādītajiem rakstiem:

    • DSA ceļvedis, Sandeep Jain
    • SDE LAPA — pilnīga SDE sagatavošanas rokasgrāmata
    • techcodeview.com galvenā lapa — visu apkrāptu lapu saraksts