Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Πίνακας περιεχομένων

Θέμα 1: Το μεγαλύτερο κοινό πρόθεμα

Ερώτηση 2: Η μεγαλύτερη υποσυμβολοσειρά παλίνδρομου

Θέμα 3: Δυαδικό άθροισμα

Ερώτηση 4: Πολλαπλασιασμός χορδών

---

Θέμα πρώτο:μεγαλύτερο κοινό πρόθεμα

Γράψτε μια συνάρτηση για να βρείτε το μεγαλύτερο κοινό πρόθεμα σε έναν πίνακα συμβολοσειρών

Εάν δεν υπάρχει κοινό πρόθεμα, επιστρέφει μια κενή συμβολοσειρά""

Παράδειγμα 1:

输入：strs = ["flower","flow","flight"]
输出："fl"

Παράδειγμα 2:

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

ίχνος:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]Αποτελείται μόνο από πεζά αγγλικά γράμματα

---

Λύση 1: Σύγκριση κατά ζεύγη

Η πρώτη λύση είναι η στρατηγική σύγκρισης κατά ζεύγη Πρώτα συγκρίνετε τις δύο πρώτες συμβολοσειρές, συγκρίνετε το κοινό πρόθεμα των δύο πρώτων συμβολοσειρών για να λάβετε το κοινό πρόθεμα των τριών πρώτων συμβολοσειρών

ο κώδικας εμφανίζεται ως εξής:

class Solution 
{
public:
    string findCommon(string& s1, string& s2)
    {
        int i = 0;
        //i有可能会出现越界的情况，所以i小于s1s2长度时再循环判断
        while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
 
    string longestCommonPrefix(vector<string>& strs) 
    {
        int n = strs.size();
        //same字符串就是存储最长公共前缀的字符串
        string same = strs[0];
        for(int i = 1; i < n; i++)
            same = findCommon(same, strs[i]);
        return same;
    }
};

---

Λύση 2: Ενιαία σύγκριση

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

Θα υπάρχει μια κατάσταση εκτός ορίων εδώ.

ο κώδικας εμφανίζεται ως εξής:

class Solution 
{
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        int i = 0;
        //以第一个字符串为基准，与其他所有字符串做比较
        for(i = 0; i < strs[0].size(); i++)
        {
            //ch表示第一个字符串当前循环到的字符
            char ch = strs[0][i];
            //循环strs中其余的字符串，其余字符串的i位置字符与ch做比较
            for(int j = 1; j < strs.size(); j++)
            {  
                //如果i大于当前字符串的长度，说明当前字符串已经没有元素了
                if(i > strs[j].size() || strs[j][i] != ch)
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

---

Θέμα 2:μακρύτερη υποχορδή παλίνδρομου

Σου δώσε μια χορδήs,εμφανιζομαιsΗ μεγαλύτερη υποχορδή παλίνδρομου σε

Παράδειγμα 1:

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

Παράδειγμα 2:

输入：s = "cbbd"
输出："bb"

---

Ο συνηθισμένος αλγόριθμος απαρίθμησης ωμής δύναμης ορίζει δύο δείκτες, έναν i και έναν j, καθορίζει το i και μετακινεί το j προς τα πίσω. Το j μετακινείται και κρίνοντας αν υπάρχει μια υποσυμβολοσειρά παλίνδρομου μεταξύ του i και του j, η χρονική πολυπλοκότητα εδώ είναι O(N^2) και επειδή υπάρχει ένα στρώμα του i φωλιασμένο έξω, το οποίο χρησιμοποιείται για να διασχίσει ολόκληρη τη συμβολοσειρά. ολόκληρος ο χρόνος βίαιης απαρίθμησης Η πολυπλοκότητα είναι πολύ υψηλή, φτάνοντας στο O(N^3).

Λύση: Αλγόριθμος επέκτασης κέντρου

Ο αλγόριθμος επέκτασης του κέντρου είναι:

①Στερεώστε ένα κεντρικό σημείο
②Ξεκινήστε από το κεντρικό σημείο και επεκτείνετε και στις δύο πλευρές (πρέπει να ληφθούν υπόψη και τα μονά και τα ζυγά μήκη)

Δηλαδή, ένα κεντρικό σημείο i καθορίζεται κάθε φορά, και κάθε φορά που επεκτείνεται στα αριστερά και στα δεξιά του i για να καθοριστεί εάν είναι μια συμβολοσειρά παλίνδρομου Η χρονική πολυπλοκότητα αυτού του αλγορίθμου που διασχίζει το i είναι O(N). και η ένθετη κατεύθυνση είναι αριστερά και δεξιά του i Κατ' επέκταση, η χρονική πολυπλοκότητα είναι επίσης O(N), άρα τελικά είναι O(N^2), η οποία είναι πολύ πιο βελτιστοποιημένη από τη βίαιη λύση που αναφέρθηκε παραπάνω. .

Αυτό που πρέπει να σημειωθεί είναι το δεύτερο σημείο του αλγορίθμου επέκτασης του κέντρου Οι περιττοί και ζυγοί αριθμοί μετακινούν τον αριστερό και τον δεξιό δείκτη από τη θέση i προς τα αριστερά και προς τα δεξιά, ενώ οι ζυγοί αριθμοί απαιτούν. αριστερά για να βρίσκεστε στη θέση i και δεξιά για να είστε στη θέση i + 1. και μετά μετακινηθείτε αριστερά και δεξιά

Θα πρέπει να σημειωθεί ότι το μήκος στον κώδικα είναι δεξιά - αριστερά - 1, γιατί αν το τρέχον αριστερά και δεξιά δείχνουν στο ίδιο στοιχείο, πρέπει να αλλάξετε αριστερά--, δεξιά++, αν δεν είναι τα ίδια, βγείτε από το βρόχο , άρα υπάρχουν περισσότερες αριστερές και δεξιές χορδές από παλίνδρομο Έχει μετακινηθεί μία θέση, οπότε το μήκος υπολογίζεται από δεξιά - αριστερά - 1. Δείτε το παρακάτω σχήμα για λεπτομέρειες:

Όπως φαίνεται στο παραπάνω σχήμα, αριστερά και δεξιά δείχνουν στο τρέχον σημείο για έξοδο από τον βρόχο, οπότε το μήκος της υποσυμβολοσειράς παλίνδρομου aa είναι:
δεξιά - αριστερά - 1 = 3 - 0 - 1 = 2

---

ο κώδικας εμφανίζεται ως εξής:

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        if(s.size() == 1) return s;
        int n = s.size(), begin = 0, size = 0;
        for(int i = 0; i < n; i++)
        {
            //先做奇数长度的扩展
            int left = i, right = i;
            //left和right符合条件，且指向元素相等再进入循环
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            //如果长度更大，更新begin与size
            if((right - left - 1) > size)
            {
                size = right - left - 1;
                begin = left + 1;
            }
            //再做偶数长度的扩展
            left = i, right = i + 1;
            //left和right符合条件，且指向元素相等再进入循环
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            //如果长度更大，更新begin与size
            if((right - left - 1) > size)
            {
                size = right - left - 1;
                begin = left + 1;
            }            
        }
        return s.substr(begin, size);
    }
};

---

Θέμα τρίτο:Δυαδικό άθροισμα

Σας δίνουμε δύο δυαδικές συμβολοσειρέςaκαιb, επιστρέφοντας το άθροισμά τους ως δυαδική συμβολοσειρά.

Παράδειγμα 1:

输入:a = "11", b = "1"
输出："100"

Παράδειγμα 2:

输入：a = "1010", b = "1011"
输出："10101"

---

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

Πρέπει να ορίσετε δύο δείκτες, cur1 και cur2, να δείχνουν σε δύο συμβολοσειρές αντίστοιχα, και στη συνέχεια να ορίσετε μια μεταβλητή t για να αντιπροσωπεύει τη μεταφορά.

ο κώδικας εμφανίζεται ως εξής:

class Solution 
{
public:
    string addBinary(string a, string b) 
    {
        //t表示相加后的进位
        int t = 0;
        string ret;
        int cur1 = a.size()-1, cur2 = b.size()-1;
        //cur1或cur2 >= 0表示字符串没遍历完，t>0表示还剩一个进位
        while(cur1 >= 0 || cur2 >= 0 || t)
        {
            if(cur1 >= 0) t += a[cur1--] - '0';  
            if(cur2 >= 0) t += b[cur2--] - '0';
            ret += to_string(t % 2);
            t /= 2;
        }
        //从后向前加的，刚好反过来了，需要逆置
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

---

Θέμα τέταρτο:Πολλαπλασιασμός χορδών

Δίνονται δύο μη αρνητικοί ακέραιοι αριθμοί που αντιπροσωπεύονται ως συμβολοσειρέςnum1καιnum2,ΕΠΙΣΤΡΟΦΗnum1καιnum2Το γινόμενο του , το προϊόν τους εκφράζεται και σε μορφή συμβολοσειράς.

Ειδοποίηση:Δεν μπορείτε να χρησιμοποιήσετε καμία από τις ενσωματωμένες βιβλιοθήκες BigInteger ή να μετατρέψετε απευθείας την είσοδο σε ακέραιο.

Παράδειγμα 1:

输入: num1 = "2", num2 = "3"
输出: "6"

Παράδειγμα 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

---

Λύση 1: Προσομοίωση κάθετων λειτουργιών

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

Ως εξής:

Μπορούμε να το καταλάβουμε καθώς, κάθε ψηφίο του παρακάτω 456 πολλαπλασιάζεται με το παραπάνω 123 και στη συνέχεια προστίθεται, υπάρχουν τρεις λεπτομέρειες:

① Ο πολλαπλασιασμός υψηλής τάξης πρέπει να συμπληρωθεί με 0, επειδή ένα bit είναι λάθος κατά την προσθήκη 738 και 615, που μπορεί να γίνει κατανοητό ως 738 + 6150
②Προηγούμενη διαδικασία 0, μπορεί να προκύψει μια κατάσταση 123 × 0, οπότε η απάντηση είναι 000 και πρέπει να υποβληθεί σε επεξεργασία.
③Δώστε προσοχή στη σειρά των αποτελεσμάτων υπολογισμού, γιατί ο υπολογισμός γίνεται με αντίστροφη σειρά και ο πολλαπλασιασμός υπολογίζεται από το τελευταίο ψηφίο.

Αλλά αυτή η μέθοδος δεν είναι εύκολη στη σύνταξη κώδικα Πρέπει να χρησιμοποιήσουμε αυτήν τη μέθοδο για να τον βελτιστοποιήσουμε.

Λύση δεύτερη: Βελτιστοποιήστε τη Λύση 1

Πολλαπλασιάστε και προσθέστε χωρίς μεταφορά και η επεξεργασία πραγματοποιείται στο τελευταίο βήμα:

Δηλαδή, όσο κι αν πολλαπλασιαστεί, δεν θα υπάρχει μεταφορά, και η μεταφορά θα γίνει μετά την τελική πρόσθεση.

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

Εφόσον η σειρά αντιστρέφεται, ο δείκτης που αντιστοιχεί στο 123 είναι 2,1,0 και ο δείκτης που αντιστοιχεί στο 456 είναι επίσης 2,1,0

Υπάρχει ένας πολύ χρήσιμος κανόνας: οι αριθμοί που εγγράφονται με i και j πολλαπλασιάζονται και το αποτέλεσμα τυχαίνει να τοποθετείται στη θέση i + j του πίνακα.

① Ορίστε έναν πίνακα tmp με μήκος m + n - 1 (τα m και n αντιστοιχούν στα μήκη δύο πολλαπλασιαζόμενων αριθμών)
Οι δείκτες των δύο αριθμών που πολλαπλασιάζονται είναι i και j αντίστοιχα, και το υπολογισμένο αποτέλεσμα τοποθετείται στη θέση i + j του πίνακα.
②Μετά την τελική προσθήκη, η μεταφορά πρέπει να υποβληθεί σε επεξεργασία
③ Προηγούμενο 0 επεξεργασίας

ο κώδικας εμφανίζεται ως εξής:

class Solution 
{
public:
    string multiply(string num1, string num2) 
    {
        //先逆序两个字符串
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //定义一个数组tmp
        int m = num1.size(), n = num2.size();
        vector<int> tmp(m + n - 1);
        //无进位相乘然后相加
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
        //处理进位
        string ret;
        int t = 0, cur = 0;
        while(cur < m + n - 1 || t != 0)
        {
            if(cur < m + n - 1) t += tmp[cur++];
            ret += to_string(t % 10);
            t /= 10;
        }
        if(t) ret += to_string(t);
        //处理前置0
        while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
        reverse(ret.begin(), ret.end());
 
        return ret;
    }
};

---

Αυτό τελειώνει τις ερωτήσεις που σχετίζονται με τη συμβολοσειρά