Ασκήσεις αλγορίθμων: δύο δείκτες, στοίβες και κυλιόμενα παράθυρα — DedSec Project

Ασκήσεις αλγορίθμων: δύο δείκτες, στοίβες και κυλιόμενα παράθυρα Δύο δείκτες Reference implementation (Python 3) Μηχανισμός Σε αύξουσα ταξινομημένη λίστα ένας δείκτης ξεκινά από τη…

Δύο δείκτες

Reference implementation (Python 3)

def pair_sum(values, target):
    i, j = 0, len(values) - 1
    while i < j:
        total = values[i] + values[j]
        if total == target: return (values[i], values[j])
        if total < target: i += 1
        else: j -= 1
    return None
assert pair_sum([1, 2, 4, 6, 8], 10) == (2, 8)

Μηχανισμός

Σε αύξουσα ταξινομημένη λίστα ένας δείκτης ξεκινά από τη μικρότερη και ένας από τη μεγαλύτερη τιμή. Αν το άθροισμα είναι μικρό, αυξάνουμε τον αριστερό δείκτη· αν είναι μεγάλο, μειώνουμε τον δεξιό. Όταν συναντηθούν σταματάμε: δεν πρέπει να χρησιμοποιηθεί δύο φορές το ίδιο στοιχείο.

Κόστος

Σε κάθε βήμα μειώνεται το διάστημα, άρα O(n) χρόνος και O(1) πρόσθετη μνήμη. Τα μη ταξινομημένα δεδομένα χρειάζονται πρώτα sorting, που κοστίζει O(n log n), ίσως και επιπλέον μνήμη. Η δοσμένη υλοποίηση επιστρέφει τιμές, όχι αρχικούς δείκτες.

Πειράματα

[1,2,4,6,8] και στόχος 10 δίνουν (2,8). Παρακολούθησε τις μετακινήσεις.
[1,3,5] και στόχος 10 δίνουν None, επειδή το μοναδικό 5 δεν μπορεί να χρησιμοποιηθεί δύο φορές.
[5,5] και στόχος 10 δίνουν (5,5): δύο διαφορετικές θέσεις με ίδια τιμή.
[-5,-1,2,8] και στόχος 3 δίνουν (-5,8). Τα αρνητικά δεν χαλάνε τη μέθοδο σε σωστή sorted λίστα.
Χρησιμοποίησε σκόπιμα unsorted input και εξήγησε γιατί η μονότονη μετακίνηση δεν είναι πλέον έγκυρη.

Πρόσθετη άσκηση

Φτιάξε έκδοση που επιστρέφει θέσεις και, όπου γίνεται sorting, διατηρεί τον αρχικό δείκτη. Σύγκρινε με απλή λύση O(n²) σε μικρά δεδομένα. Αν υπάρχουν πολλά έγκυρα ζευγάρια, έλεγξε ύπαρξη σωστής λύσης και όχι ένα μοναδικό επιλεγμένο ζευγάρι.

Ισορροπημένες παρενθέσεις

Reference implementation (Python 3)

def balanced(text):
    stack, pairs = [], {')': '(', ']': '[', '}': '{'}
    for char in text:
        if char in '([{': stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]: return False
    return not stack
assert balanced('([])') and not balanced('([)]')

Βασική ιδιότητα

Διαβάζουμε χαρακτήρα προς χαρακτήρα. Για άνοιγμα (, [ ή { βάζουμε το σύμβολο στη στοίβα. Για κλείσιμο πρέπει να ταιριάζει ο τελευταίος μη κλεισμένος οριοθέτης. Αποτυχία σημαίνει κενή στοίβα ή διαφορετικός τύπος. Στο τέλος επιτυχία υπάρχει μόνο αν η στοίβα άδειασε.

Περιορισμοί και κόστος

Η υλοποίηση αγνοεί μη bracket χαρακτήρες. Ελέγχει nesting, όχι πλήρη γραμματική γλώσσας: ακόμη και παρενθέσεις μέσα σε string μετράνε. Επεξεργάζεται κάθε χαρακτήρα μία φορά: O(n) χρόνος και στη χειρότερη περίπτωση O(n) μνήμη στη στοίβα.

Δοκιμές

'([])' είναι έγκυρο, αλλά '([)]' αποτυγχάνει επειδή ο τύπος του πρώτου κλεισίματος διαφέρει από το top.
'(()' αποτυγχάνει στο τέλος, αφού απομένει άνοιγμα.
')(' αποτυγχάνει από τον πρώτο χαρακτήρα λόγω κενής στοίβας.
'[{}]' επιτυγχάνει, ενώ '[{]' αποτυγχάνει λόγω αταίριαστης αγκύλης.
'text(a[b])' επιτυγχάνει επειδή επιλέξαμε να αγνοούμε γράμματα. Για linting πραγματικού κώδικα πρέπει πρώτα να αναγνωρίσουμε strings και comments.

Επόμενη υλοποίηση

Αντί για απλό bool επέστρεψε θέση και αιτία του πρώτου λάθους ή τις θέσεις των ανοιγμάτων που έμειναν. Δοκίμασε 10000 ένθετους οριοθέτες και εξήγησε γιατί η ρητή στοίβα αποφεύγει τα recursion limits ενός αναδρομικού parser.

Κυλιόμενο παράθυρο

Python 3 reference program

def max_window_sum(values, k):
    if k <= 0 or k > len(values): raise ValueError('invalid window')
    current = sum(values[:k]); best = current
    for right in range(k, len(values)):
        current += values[right] - values[right-k]
        best = max(best, current)
    return best
assert max_window_sum([1,3,2,5,1],2) == 7

Αναδρομική σχέση

Δύο διαδοχικά παράθυρα μήκους k διαφέρουν σε ακριβώς δύο στοιχεία: αφαιρείται το αριστερό και προστίθεται το καινούριο δεξιά. Η ενημέρωση είναι current + values[right] - values[right-k]. Μετά το αρχικό άθροισμα k τιμών, κάθε μετακίνηση είναι O(1), άρα συνολικός χρόνος O(n).

Προσοχή στην πραγματική μνήμη

Ο κώδικας αρχίζει με sum(values[:k]). Το slicing Python list δημιουργεί αντίγραφο k αναφορών. Παρά την ενημέρωση σταθερού χρόνου, απαιτεί προσωρινό O(k) χώρο. Για O(1) πρόσθετη μνήμη χρησιμοποίησε αρχικό άθροισμα μέσω generator χωρίς slice.

Δοκιμές

Για [1,3,2,5,1] και k=2 τα αθροίσματα είναι 4,5,7,6, επομένως αποτέλεσμα 7.
Με k=1 επιστρέφεται η μέγιστη μεμονωμένη τιμή.
Με k=μήκος λίστας υπάρχει μόνο ένα παράθυρο, το ολικό άθροισμα.
Με k=0, αρνητικό k ή k μεγαλύτερο του μήκους πρέπει να προκύπτει ValueError.
Για αρνητικά [-5,-2,-7] και k=2, η μέγιστη τιμή είναι -7. Αν αρχικοποιήσεις best=0 θα έχεις λάθος αποτέλεσμα.

Πέρα από σταθερό k

Σε variable-size παράθυρο με όριο αθροίσματος, η μονοτονία του κλασικού two-pointers συνήθως απαιτεί μη αρνητικές τιμές. Με αρνητικά δεδομένα χρειάζεται διαφορετικός αλγόριθμος ή σαφής απόδειξη. Σύγκρινε την υλοποίηση με αργή αναφορά που ελέγχει όλα τα παράθυρα.

04 two pointers — έλεγχος ορίων

Η μέθοδος δύο δεικτών απαιτεί ταξινομημένα δεδομένα: όταν το άθροισμα είναι μικρό αυξάνεις τον αριστερό, όταν είναι μεγάλο μειώνεις τον δεξιό. Χωρίς ταξινόμηση μπορεί να χαθεί σωστό ζεύγος.

Έλεγξε [1,1] με στόχο 2 (δύο διαφορετικές θέσεις), [5] με στόχο 10 (κανένα ζεύγος) και [-4,-1,2,8] με στόχο 4.

05 stack matching — έλεγχος ορίων

Η στοίβα απαιτεί να κλείνει πρώτο το τελευταίο ανοιγμένο σύμβολο. Το κλείσιμο πρέπει να ταιριάζει με το τελευταίο ανοιχτό· απλή καταμέτρηση δεν ξεχωρίζει ([)] από ([]).

Το κενό κείμενο είναι ισορροπημένο. Το '}' αποτυγχάνει αμέσως, ενώ το '(((' αποτυγχάνει στο τέλος. Ο συγκεκριμένος parser αγνοεί μη-παρενθετικούς χαρακτήρες.

08 sliding window — έλεγχος ορίων

Σε παράθυρο σταθερού μεγέθους αφαίρεσε την τιμή στη θέση right-k και πρόσθεσε τη νέα στη θέση right. Έτσι το current παραμένει άθροισμα ακριβώς k διαδοχικών τιμών. Λειτουργεί και με αρνητικά.

Για k=1 επιστρέφεται η μεγαλύτερη τιμή, για k=len(values) το συνολικό άθροισμα. k=0 ή k μεγαλύτερο από την είσοδο απορρίπτεται.