Ποιοι αλγόριθμοι πρέπει να γνωρίζω για να γίνω καλός προγραμματιστής;


Απάντηση 1:

ΕΠΙΚΑΙΡΟΠΟΙΗΜΕΝΟ.

21 Σεπτεμβρίου, 2016. Ενημερώθηκε η θεωρία των γραφημάτων και οι ενότητες δυναμικού προγραμματισμού.

Ο κατάλογος των αλγορίθμων για την επίτευξη του Top 100 είναι κάτω από:

  • Αλγόριθμοι ταξινόμησης
  1. SBI (επιλογή, φούσκα, εισαγωγή) Συγχώνευση sortHeap sort (μάθετε αυτό αργότερα όταν καταλαβαίνετε γραφήματα / δέντρα) Γρήγορη ταξινόμηση (κυρίως hoare's partition scheme) Χρησιμοποιήστε το γρήγορο ταξινόμηση παντού, λειτούργησε καλά για όλους τους αλγόριθμους.
  • Αλγόριθμοι αναζήτησης
  1. Γραμμικός συνδυασμός χαμηλός δεσμός
  • Αναζήτηση στη συμβολοσειρά
  1. (T) KMPBoyer MooreΆλλοι υπάρχουν, αλλά απλά πηγαίνουν μέσα τουςΌλοι καταλαβαίνουν το πρότυπο P για να ψάξουν περισσότερο, σε μια συμβολοσειρά T (κείμενο), οπότε είναι εύκολο να παραλείψετε κάποιες συγκρίσεις που έχουν ήδη γίνει. Το παράθυρο Suffix - απλά οι δείκτες των ταξινομημένων επιθημάτων μιας συμβολοσειράς - αυτό είναι πολύ σημαντικό, εξοικονομώντας πολύ χρόνο εκτέλεσης, έτσι ώστε οι δοκιμές σας να περάσουν εύκολα. LCP array - Η πρώτη είσοδος είναι απροσδιόριστη, άλλες καταχωρήσεις είναι τα μακρύτερα κοινά μήκη προθέματος (1ος και 0ος δείκτης του πίνακα Suffix μιας συμβολοσειράς κ.ο.κ.)
  • Απληστος
  1. Πάρτε το πρώτο ένστικτο, τώρα για ό, τι είναι καλύτερο, πάρτε το (αλγόριθμος Dijkstra είναι καλό παράδειγμα, αλλά θα έρθει στη Θεωρία των Γραφημάτων)
  • Θεωρία γραφημάτων - Δέντρο
  1. BFSDFSPαποσυμπιέστε - κόμβος, αριστερά, στη συνέχεια δεξιάΠροσθήκη - αριστερά, δεξιά στη συνέχεια κόμβοςΚάση - αριστερά, κόμβος και στη συνέχεια δεξιάΔυδικό δέντρο - μέγιστο 2 κόμβοιΔυνατότηταΔημοφιλία Δέντρο - max 2 κόμβοι, αριστερά
  • Θεωρία γραφημάτων - Γράφημα
  1. Ο πίνακας Adjacency - πίνακας συστοιχιών (με διαφορετικό μήκος) - εξοικονομεί μεγάλη μνήμη - (χρησιμοποιεί ο καθένας) BFSDFSPαπό παραγγελία - κόμβος, αριστερά, τότε το σωστό αλγόριθμο - N δύναμη N είναι τώρα N εξουσία 3Belman Ford - ((ξέχασε!)) Kruskal και Prim - να διασχίσουν όλους τους κόμβους από το γράφημα μια φορά, δηλαδή το ελάχιστο spanning Tree Tree Tree - αυτό μπορεί να έρθει σε οποιαδήποτε ερώτηση και είναι δύσκολο να ξεκινήσουμε, αλλά σιγά-σιγά παίρνουμε την ιδέα. Πολλά ερωτήματα είναι το κλειδί εδώ, έτσι προεπεξεργαζόμαστε με διαφορετικό τρόπο Όλα τα στοιχεία N array (n-1) (επίπεδο?) παραπάνω έχουν 2 περιλήψεις παιδικών κόμβων καθώς ανεβαίνουμε στη ρίζα. Μπορούμε να ενημερώσουμε 1 στοιχείο συστοιχίας, κόμβο φύλλων, τότε διαδίδουμε το info up. μπορούμε να αναβαθμίσουμε μια σειρά στοιχείωνΠαραφέρουμε τις πληροφορίες ξανά, αμέσως ή lazily.Queries θα είναι γρήγορη: ποιο είναι το μέγιστο ή το άθροισμα για διαφορετικές (LR) σειρές; Hamiltonian μονοπάτι & κύκλος, επίσης graphEuler διαδρομή & κύκλο, επίσης γράφημα
  • Δυναμικός προγραμματισμός
  1. ΜΗΝ πάρετε το πρώτο ένστικτο, ό, τι και αν φαίνεται καλύτερα. μπορεί να μην είναι το καλύτερο όταν θεωρείται πλήρες πρόβλημα.Περίληψη υποβάθρουRecursion + ΥπενθύμισηDP + Υπενθύμιση always2D Memoization3D MemoizationΜάθετε τους διάφορους τύπους: MaximizationMinimizationΑριθμός τρόπων. Γενικά, το Modulus (%) έχει κάποιο πρωταρχικό αριθμό, όπως το% (10 power 9 + 7) Τροποποιήστε το πρόβλημα, για να φτάσετε σε ένα από τα παραπάνω. Είναι δύσκολο, επειδή ένα πρόβλημα DP μπορεί να περιλαμβάνει άλλα πράγματα όπως τα μαθηματικά, problemsthis σημαίνει κατανόηση του προβλήματος παίρνει πολύ χρόνο μετά είναι σαφές τι να κάνουμε, ένα από τα παραπάνω DP μπορεί να εφαρμοστεί.Δείτε ένα σχετικό βίντεο για την DP στο youtube για το πρόβλημα που λύνετε: Έψαξα στο youtube, δεν υπάρχει ενιαία σύνδεση βίντεο , αλλά εξετάστε τα κορυφαία 5 αποτελέσματαΗ κατανόηση της υπάρχουσας λύσης θα σας βοηθήσει να κάνετε μια σωστή λύση για το υπάρχον πρόβλημα που λειτούργησε για περίπου 70 +% για μένα.
  • Μικρή χειραγώγηση
  1. (BIT) / δέντρο Fenwick - Ένα άλλο όμορφο δέντρο (στην πραγματικότητα πίνακας) - είναι ένα πολύ όμορφο δέντρο (στην πραγματικότητα πίνακας) Αποθηκεύστε μόνο την τιμή της αριστερής υποκατηγορίας (αθροιστικά) σε έναν κόμβο - Εύκολη τροποποίηση, κλπ.

Πίσω στο: