Condivisione della tecnologia

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

Sommario

Argomento 1: Il prefisso comune più lungo

Domanda 2: la sottostringa palindroma più lunga

Argomento 3: Somma binaria

Domanda 4: Moltiplicare le stringhe

---

Argomento uno:prefisso comune più lungo

Scrivi una funzione per trovare il prefisso comune più lungo in un array di stringhe

Se non esiste un prefisso comune, restituisce una stringa vuota""

Esempio 1:

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

Esempio 2:

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

suggerimento:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]È composto solo da lettere inglesi minuscole

---

Soluzione 1: confronto a coppie

La prima soluzione è la strategia di confronto a coppie. Confrontare prima le prime due stringhe. Dopo il confronto, confrontare il prefisso comune delle prime due stringhe con la terza stringa per ottenere il prefisso comune delle prime tre stringhe e così via

codice mostrato come di seguito:

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;
    }
};

---

Soluzione 2: confronto unificato

Confronto unificato significa confrontare la stessa posizione di tutte le stringhe contemporaneamente per determinare se le posizioni sono le stesse finché non compaiono caratteri diversi.

Ci sarà una situazione fuori limite qui. Se c'è una situazione fuori limite, significa che una determinata stringa è terminata e quindi il confronto può essere terminato.

codice mostrato come di seguito:

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];
    }
};

---

Argomento 2:sottostringa palindroma più lunga

Dammi una cordas,uscire fuorisLa sottostringa palindromo più lunga in

Esempio 1:

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

Esempio 2:

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

---

L'algoritmo ordinario di enumerazione della forza bruta imposta due puntatori, uno i e uno j, fissa i e sposta j indietro. Ogni volta che j viene spostato, è necessario determinare se la stringa tra i e j è una sottostringa palindroma. j viene spostato. E a giudicare se esiste una sottostringa palindroma tra i e j, la complessità temporale qui è O(N^2), e poiché c'è uno strato di i nidificato all'esterno, che viene utilizzato per attraversare l'intera stringa, il intero tempo di enumerazione violenta La complessità è molto elevata, raggiungendo O(N^3). Diamo un'occhiata all'algoritmo di espansione centrale ottimizzato:

Soluzione: algoritmo di espansione centrale

L'algoritmo di espansione del centro è:

①Fissare un punto centrale
②Inizia dal punto centrale ed espandi su entrambi i lati (è necessario considerare sia la lunghezza pari che quella dispari)

Vale a dire, ogni volta viene fissato un punto centrale i, e ogni volta viene espanso a sinistra e a destra di i per determinare se si tratta di una stringa palindroma. La complessità temporale di questo algoritmo che attraversa i è O(N),. e la direzione annidata è a sinistra e a destra di i. Per estensione, anche la complessità temporale è O(N), quindi alla fine è O(N^2), che è molto più ottimizzata della soluzione violenta menzionata sopra. .

Ciò che deve essere notato è il secondo punto dell'algoritmo di espansione centrale che deve essere considerato. I numeri pari e dispari spostano i puntatori sinistro e destro dalla posizione i a sinistra e a destra, mentre i numeri pari lo richiedono. sinistra per essere nella posizione i e destra per essere nella posizione i + 1., quindi spostarsi a sinistra e a destra

Va notato che la lunghezza nel codice è right - left - 1, perché se gli attuali left e right puntano allo stesso elemento, è necessario modificare left--, right++ Se non sono la stessa cosa, uscire dal ciclo , quindi ci sono più stringhe sinistra e destra rispetto alle stringhe palindrome. Si è spostata di una posizione, quindi la lunghezza viene calcolata da destra - sinistra - 1. Per i dettagli vedere la figura seguente:

Come mostrato nella figura sopra, sinistra e destra puntano al punto corrente per uscire dal ciclo, quindi la lunghezza della sottostringa palindroma aa è:
destra - sinistra - 1 = 3 - 0 - 1 = 2

---

codice mostrato come di seguito:

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);
    }
};

---

Argomento tre:Somma binaria

Fornisci due stringhe binarieaEb, restituendo la somma come stringa binaria.

Esempio 1:

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

Esempio 2:

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

---

Questa domanda riguarda il calcolo dell'addizione ad alta precisione, l'esecuzione di un'operazione di simulazione e la simulazione del processo di calcolo verticale.

È necessario impostare due puntatori, cur1 e cur2, in modo che puntino rispettivamente a due stringhe, quindi impostare una variabile t per rappresentare il carry.

codice mostrato come di seguito:

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;
    }
};

---

Argomento quattro:Moltiplicazione di stringhe

Dati due numeri interi non negativi rappresentati come stringhenum1Enum2,ritornonum1Enum2Anche il prodotto di , il loro prodotto, è espresso in forma di stringa.

Avviso:Non è possibile utilizzare nessuna delle librerie BigInteger integrate o convertire direttamente l'input in un numero intero.

Esempio 1:

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

Esempio 2:

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

---

Soluzione 1: simulare operazioni verticali

In matematica, è la forma verticale della colonna della moltiplicazione. Questo è il metodo più semplice a cui pensare.

Come segue:

Possiamo capirlo poiché ogni cifra del seguente 456 viene moltiplicata per la precedente 123 e quindi sommata si ottengono tre dettagli:

①La moltiplicazione di ordine superiore deve essere riempita con 0, perché un bit è sbagliato quando si sommano 738 e 615, che può essere inteso come 738 + 6150
②Processo che precede 0, può verificarsi una situazione di 123 × 0, nel qual caso la risposta è 000 e deve essere risolta.
③Prestare attenzione all'ordine dei risultati del calcolo, perché il calcolo viene eseguito in ordine inverso e la moltiplicazione viene calcolata dall'ultima cifra.

Ma questo metodo non è facile da scrivere codice. Dobbiamo usarlo per ottimizzarlo.

Soluzione due: ottimizza la soluzione uno

Moltiplica e aggiungi senza riporto e il riporto verrà elaborato nell'ultimo passaggio:

Cioè, non importa quanto viene moltiplicato, non ci sarà alcun riporto e il riporto verrà eseguito dopo l'addizione finale.

Allo stesso modo, quando si avvia il calcolo, invertire prima l'ordine Poiché la moltiplicazione può essere di due cifre, non è possibile utilizzare la rappresentazione di stringa, è invece possibile utilizzare un array per memorizzare

Poiché l'ordine è invertito, il pedice corrispondente a 123 è 2,1,0 e anche il pedice corrispondente a 456 è 2,1,0

Esiste una regola molto utile: i numeri con indice i e j vengono moltiplicati e il risultato viene posizionato nella i + jesima posizione dell'array.

① Definisci un array tmp con una lunghezza di m + n - 1 (m e n corrispondono alle lunghezze di due numeri moltiplicati)
Gli indici dei due numeri da moltiplicare sono rispettivamente i e j e il risultato calcolato viene posizionato nella i + jesima posizione dell'array.
②Dopo l'aggiunta finale, è necessario elaborare il riporto
③Elaborazione iniziale 0

codice mostrato come di seguito:

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;
    }
};

---

Questo pone fine alle domande relative alle stringhe