LeetCode 2801 (Σκληρό, Επίπεδο Αποδοχής 14,5%).

Διαίσθηση

Το πρόβλημα απαιτεί την εύρεση του αριθμού των βηματικών αριθμών σε ένα δεδομένο εύρος [χαμηλό, υψηλό], όπου ένας βηματικός αριθμός είναι ένας ακέραιος έτσι ώστε όλα τα διπλανά ψηφία του να έχουν απόλυτη διαφορά ακριβώς 1. Για να μετρήσουμε αποτελεσματικά αυτούς τους βηματικούς αριθμούς, μπορούμε να χρησιμοποιήσουμε μια δυναμική προγραμματιστική προσέγγιση.

Πλησιάζω

Η λύση Swift χρησιμοποιεί δυναμικό προγραμματισμό για την επίλυση του προβλήματος. Η συνάρτηση rec υπολογίζει αναδρομικά το πλήθος των βηματικών αριθμών με βάση ορισμένες συνθήκες. Ο πίνακας dp χρησιμοποιείται για την αποθήκευση των αποτελεσμάτων που έχουν υπολογιστεί προηγουμένως, γεγονός που βοηθά στην αποφυγή περιττών υπολογισμών και βελτιώνει την απόδοση.

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

Στη συνάρτηση countSteppingNumbers, καλούμε rec δύο φορές για το εύρος εισόδου [χαμηλό, υψηλό] και στη συνέχεια αφαιρούμε το πλήθος για χαμηλό από το πλήθος για υψηλό. Επιπλέον, εάν το ίδιο το χαμηλό είναι ένας αριθμός βήματος, προσθέτουμε 1 στο αποτέλεσμα.

Κωδικός (Swift)

Η λύση χειρίζεται αποτελεσματικά μεγάλες εισόδους και επιστρέφει το πλήθος των βηματικών αριθμών modulo 10⁹ + 7, όπως απαιτείται από τη δήλωση προβλήματος.

class Solution {

    let mod = 1_000_000_007

    var dp: [[[[Int]]]] = Array(
        repeating: Array(
            repeating: Array(repeating: Array(repeating: -1, count: 2), count: 10), count: 2),
        count: 101)

    func rec(_ s1: [Character], _ ind: Int, _ smaller: Bool, _ last: Int, _ start: Bool) -> Int {
        if ind == s1.count {
            return 1
        }

        if dp[ind][smaller ? 1 : 0][last][start ? 1 : 0] != -1 {
            return dp[ind][smaller ? 1 : 0][last][start ? 1 : 0]
        }

        var ans = 0

        if start || abs(last - 0) == 1 {
            ans = (ans + rec(s1, ind + 1, smaller || (s1[ind] != "0"), 0, start)) % mod
        }

        if smaller {
            for i in 1...9 {
                if abs(last - i) == 1 || start {
                    ans = (ans + rec(s1, ind + 1, smaller, i, false)) % mod
                }
            }
        } else {
            let diff = Int(String(s1[ind]))!
            if diff > 0 {
                for i in 1..<diff {
                    if abs(last - i) == 1 || start {
                        ans = (ans + rec(s1, ind + 1, true, i, false)) % mod
                    }
                }
            }
            if s1[ind] != "0" {
                if abs(last - diff) == 1 || start {
                    ans = (ans + rec(s1, ind + 1, false, diff, false)) % mod
                }
            }
        }
        dp[ind][smaller ? 1 : 0][last][start ? 1 : 0] = ans
        return ans
    }

    func check(_ s: String) -> Bool {
        let sChars = Array(s)
        for i in 0..<(sChars.count - 1) {
            if abs(Int(String(sChars[i]))! - Int(String(sChars[i + 1]))!) != 1 {
                return false
            }
        }
        return true
    }

    func countSteppingNumbers(_ low: String, _ high: String) -> Int {
        let x = rec(Array(high), 0, false, 0, true)
        dp = Array(
            repeating: Array(
                repeating: Array(repeating: Array(repeating: -1, count: 2), count: 10), count: 2),
            count: 101)
        let y = rec(Array(low), 0, false, 0, true)

        let z = check(low)

        return (x - y + (z ? 1 : 0) + mod) % mod
    }
}

Πηγές: Github

Επαφές
Εστιάζω ξεκάθαρα στο time-to-market και δεν δίνω προτεραιότητα στο τεχνικό χρέος. Και έλαβα μέρος στη δραστηριότητα Pre-Sale/RFX ως System Architect, σε προσπάθειες αξιολόγησης για κινητά (iOS-Swift, Android-Kotlin), Frontend (React-TypeScript) και Backend (NodeJS-.NET-PHP-Kafka-SQL -NoSQL). Και σχημάτισα επίσης το έργο της Προπώλησης ως CTO από την ευκαιρία στην πρόταση μέσω μεταφοράς γνώσης στην επιτυχή παράδοση.

🛩️ #startups #management #cto #swift #typescript #database
📧 Email: [email protected]
👋 LinkedIn: https://linkedin.com/in/sergeyleschev/
👋 LeetCode: https://leetcode.com/sergeyleschev/
👋 Twitter: https://twitter.com/sergeyleschev
👋 Github: https://github .com/sergeyleschev
🌎 Ιστότοπος: https://sergeyleschev.github.io
🌎 Reddit: https://reddit.com/user/sergeyleschev
🌎 Quora: https://quora.com/sergey-leschev
🌎 Μέσο: https://medium.com/@sergeyleschev
🖨️ Μοτίβα σχεδίασης PDF: Λήψη