Teknologian jakaminen

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

Sisällysluettelo

Aihe 1: Pisin yhteinen etuliite

Kysymys 2: Pisin palindromimerkkijono

Aihe 3: Binäärisumma

Kysymys 4: merkkijonojen kertominen

---

Aihe yksi:pisin yhteinen etuliite

Kirjoita funktio löytääksesi pisin yhteinen etuliite merkkijonojoukosta

Jos yhteistä etuliitettä ei ole, palauttaa tyhjän merkkijonon""

Esimerkki 1:

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

Esimerkki 2:

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

vihje:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]Sisältää vain pieniä englanninkielisiä kirjaimia

---

Ratkaisu 1: Parivertailu

Ensimmäinen ratkaisu on parivertailu. Vertaa ensin kahden ensimmäisen merkkijonon yhteistä etuliitettä kolmanteen merkkijonoon, ja niin edelleen

koodi näytetään alla:

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

---

Ratkaisu 2: Yhtenäinen vertailu

Yhtenäinen vertailu tarkoittaa kaikkien merkkijonojen saman sijainnin vertaamista kerralla sen määrittämiseksi, ovatko paikat samat, kunnes eri merkit ilmestyvät.

Tässä on rajojen ulkopuolella oleva tilanne.

koodi näytetään alla:

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

---

Aihe 2:pisin palindromimerkkijono

Anna merkkijonos, nosta ylössPisin palindromi-osamerkkijono

Esimerkki 1:

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

Esimerkki 2:

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

---

Tavallinen raa'an voiman laskenta-algoritmi asettaa kaksi osoitinta, yksi i ja yksi j, korjaa i ja siirtää j:tä taaksepäin Joka kerta kun j:tä siirretään, on tarpeen määrittää, onko merkkijono i:n ja j:n välillä palindromimerkkijono. j on siirretty. Ja päätettäessä, onko i:n ja j:n välillä palindromiosamerkkijono, aikamonimutkaisuus tässä on O(N^2), ja koska ulkopuolella on sisäkkäinen i-kerros, jota käytetään koko merkkijonon läpi kulkemiseen. koko väkivaltainen luettelointiaika Monimutkaisuus on erittäin korkea, saavuttaen O(N^3). Katsotaanpa optimoitua keskustan laajennusalgoritmia:

Ratkaisu: Keskitä laajennusalgoritmi

Keskuksen laajennusalgoritmi on:

①Korjaa keskipiste
②Aloita keskipisteestä ja laajenna molemmille puolille (sekä parittomat että parilliset pituudet on otettava huomioon)

Toisin sanoen keskipiste i kiinnitetään joka kerta, ja joka kerta, kun sitä laajennetaan i:n vasemmalle ja oikealle puolelle sen määrittämiseksi, onko se palindromimerkkijono. Tämän i:n läpi kulkevan algoritmin aikamonimutkaisuus on O(N), ja sisäkkäinen suunta on i:n vasemmalle ja oikealle Laajennuksena myös aikakompleksisuus on O(N), joten se on lopulta O(N^2), mikä on paljon optimoitumpi kuin edellä mainittu väkivaltainen ratkaisu. .

Huomioittava on keskialueen laajennusalgoritmin toinen piste. Parittomat ja parilliset luvut siirtävät vasenta ja oikeaa osoittimia i-asemasta vasemmalle ja oikealle, kun taas parilliset luvut vaativat. vasen ollaksesi i-asennossa ja oikea olla kohdassa i + 1. ja sitten liikkua vasemmalle ja oikealle

On huomattava, että koodin pituus on oikea - vasen - 1, koska jos nykyinen vasen ja oikea osoittavat samaan elementtiin, sinun on vaihdettava vasen--, oikea++, jos ne eivät ole samat, poistu silmukasta , joten vasemmalla ja oikealla on enemmän kuin palindromimerkkijonoja. Se on siirtynyt yhden sijainnin, joten pituus lasketaan oikealta - vasemmalta - 1. Katso lisätietoja alla olevasta kuvasta.

Kuten yllä olevasta kuvasta näkyy, vasen ja oikea osoittavat nykyiseen pisteeseen poistuaksesi silmukasta, joten palindromi-alijonon aa pituus on:
oikea - vasen - 1 = 3 - 0 - 1 = 2

---

koodi näytetään alla:

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

---

Aihe kolme:Binäärisumma

Anna kaksi binäärimerkkijonoaajab, palauttavat summansa binäärimerkkijonona.

Esimerkki 1:

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

Esimerkki 2:

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

---

Tämä kysymys koskee suuren tarkkuuden laskemista, simulointioperaation suorittamista ja pystysuoran laskennan simulointia.

Sinun on asetettava kaksi osoitinta, cur1 ja cur2, osoittamaan vastaavasti kahteen merkkijonoon, ja asetettava sitten muuttuja t edustamaan siirtoa.

koodi näytetään alla:

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

---

Aihe neljä:Merkkijonojen kertolasku

Annettu kaksi ei-negatiivista kokonaislukua, jotka esitetään merkkijonoinanum1janum2,palatanum1janum2Tuotteen , heidän tuotteensa ilmaistaan ​​myös merkkijonomuodossa.

Ilmoitus:Et voi käyttää mitään sisäänrakennettuja BigInteger-kirjastoja tai muuntaa syötettä suoraan kokonaisluvuksi.

Esimerkki 1:

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

Esimerkki 2:

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

---

Ratkaisu 1: Simuloi pystysuorat toiminnot

Matematiikassa se on kertolasarakkeen pystymuoto. Tämä on helpoin tapa ajatella.

Seuraavasti:

Ymmärrämme sen siten, että jokainen seuraavan 456:n numero kerrotaan yllä olevalla 123:lla ja lisätään sitten kolme yksityiskohtaa:

①Korkeamman asteen kertolasku on täytettävä 0:lla, koska yksi bitti on väärin lisättäessä 738 ja 615, jotka voidaan ymmärtää 738 + 6150
②Prosessin alku 0, tilanne on 123 × 0, jolloin vastaus on 000 ja se on käsiteltävä.
③ Kiinnitä huomiota laskentatulosten järjestykseen, koska laskenta suoritetaan käänteisessä järjestyksessä ja kertolasku lasketaan viimeisestä numerosta.

Mutta tämä menetelmä ei ole helppo kirjoittaa koodia. Meidän on käytettävä tätä menetelmää sen optimoimiseksi.

Ratkaisu kaksi: Optimoi Ratkaisu Yksi

Kerro ja lisää ilman siirtoa, ja siirto käsitellään viimeisessä vaiheessa:

Eli riippumatta siitä, kuinka paljon kerrotaan, siirtoa ei tule, ja siirto suoritetaan viimeisen lisäyksen jälkeen.

Samoin, kun aloitat laskennan, käännä järjestys, koska kertolasku voi olla kaksinumeroinen, merkkijonoesitystä ei voi käyttää sen sijaan

Koska järjestys on käänteinen, 123:a vastaava alaindeksi on 2,1,0 ja 456 vastaava alaindeksi on myös 2,1,0

On olemassa erittäin hyödyllinen sääntö: i:llä ja j:llä merkityt luvut kerrotaan, ja tulos sattuu olemaan taulukon i + j:nneksi.

① Määrittele taulukko tmp, jonka pituus on m + n - 1 (m ja n vastaavat kahden kerrotun luvun pituuksia)
Kahden kerrottavan luvun alaindeksit ovat i ja j, vastaavasti, ja laskettu tulos sijoitetaan taulukon i + j:nnelle paikalle.
② Viimeisen lisäyksen jälkeen kanto on käsiteltävä
③ Käsitellään alku0

koodi näytetään alla:

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

---

Tämä lopettaa merkkijonoon liittyvät kysymykset