Technologieaustausch

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

Inhaltsverzeichnis

Thema 1: Das längste gemeinsame Präfix

Frage 2: Der längste Palindrom-Teilstring

Thema 3: Binärsumme

Frage 4: Strings multiplizieren

---

Thema eins:längstes gemeinsames Präfix

Schreiben Sie eine Funktion, um das längste gemeinsame Präfix in einem Array von Zeichenfolgen zu finden

Wenn kein gemeinsames Präfix vorhanden ist, wird eine leere Zeichenfolge zurückgegeben""

Beispiel 1:

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

Beispiel 2:

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

Hinweis:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]Besteht nur aus englischen Kleinbuchstaben

---

Lösung 1: Paarweiser Vergleich

Die erste Lösung ist die paarweise Vergleichsstrategie. Vergleichen Sie nach dem Vergleich das gemeinsame Präfix der ersten beiden Zeichenfolgen, um das gemeinsame Präfix der ersten drei Zeichenfolgen zu erhalten

Code wie folgt anzeigen:

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

---

Lösung 2: Einheitlicher Vergleich

Beim einheitlichen Vergleich wird die gleiche Position aller Zeichenfolgen gleichzeitig verglichen, um festzustellen, ob die Positionen gleich sind, bis unterschiedliche Zeichen angezeigt werden.

Hier liegt eine Situation außerhalb der Grenzen vor. Wenn eine Situation außerhalb der Grenzen vorliegt, bedeutet dies, dass eine bestimmte Zeichenfolge beendet ist und der Vergleich dann beendet werden kann.

Code wie folgt anzeigen:

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

---

Thema 2:längster Palindrom-Teilstring

Gib dir eine Schnurs,auftauchensDer längste Palindrom-Teilstring in

Beispiel 1:

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

Beispiel 2:

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

---

Ein gewöhnlicher Brute-Force-Aufzählungsalgorithmus setzt zwei Zeiger, einen i und einen j, fixiert i und bewegt j nach hinten. Jedes Mal, wenn j verschoben wird, muss festgestellt werden, ob die Zeichenfolge zwischen i und j zu diesem Zeitpunkt eine Palindrom-Teilzeichenfolge ist. j wird verschoben. Und wenn man bedenkt, ob es einen Palindrom-Teilstring zwischen i und j gibt, beträgt die Zeitkomplexität hier O(N^2), und da es eine Schicht von i gibt, die außerhalb verschachtelt ist, wird sie zum Durchlaufen der gesamten Zeichenfolge verwendet Die gesamte gewalttätige Aufzählungszeit ist sehr hoch und erreicht O(N^3). Schauen wir uns den optimierten Zentrumserweiterungsalgorithmus an:

Lösung: Zentrumserweiterungsalgorithmus

Der Zentrumserweiterungsalgorithmus ist:

①Fixieren Sie einen Mittelpunkt
②Beginnen Sie im Mittelpunkt und dehnen Sie sich nach beiden Seiten aus (sowohl ungerade als auch gerade Längen müssen berücksichtigt werden).

Das heißt, jedes Mal wird ein zentraler Punkt i festgelegt und jedes Mal nach links und rechts von i erweitert, um zu bestimmen, ob es sich um eine Palindrom-Zeichenfolge handelt. Die zeitliche Komplexität dieses Algorithmus beim Durchlaufen von i beträgt O (N). und die verschachtelte Richtung ist links und rechts von i. Im weiteren Sinne ist die Zeitkomplexität auch O(N), also am Ende O(N^2), was viel optimierter ist als die oben erwähnte gewalttätige Lösung .

Zu beachten ist der zweite Punkt des Mittelerweiterungsalgorithmus. Ungerade und gerade Zahlen müssen berücksichtigt werden, da die ungeraden Zahlen den linken und rechten Zeiger von der i-Position nach links und rechts bewegen, während die geraden Zahlen dies erfordern nach links, um an der i-Position zu sein, und nach rechts, um an der i + 1-Position zu sein, und dann nach links und rechts bewegen

Es ist zu beachten, dass die Länge im Code rechts - links - 1 ist, denn wenn die aktuelle linke und rechte Seite auf dasselbe Element zeigen, müssen Sie left--, right++ ändern. Wenn sie nicht gleich sind, verlassen Sie die Schleife Es gibt also mehr linke und rechte Zeichenfolgen als Palindrom-Zeichenfolgen. Es wurde um eine Position verschoben, daher wird die Länge von rechts - links - 1 berechnet. Einzelheiten finden Sie in der folgenden Abbildung:

Wie in der Abbildung oben gezeigt, zeigen links und rechts auf den aktuellen Punkt, um die Schleife zu verlassen. Die Länge der Palindrom-Teilzeichenfolge aa beträgt also:
rechts - links - 1 = 3 - 0 - 1 = 2

---

Code wie folgt anzeigen:

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

---

Thema drei:Binäre Summe

Geben Sie zwei Binärzeichenfolgen anaUndbund gibt ihre Summe als Binärzeichenfolge zurück.

Beispiel 1:

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

Beispiel 2:

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

---

Bei dieser Frage geht es um die Berechnung einer hochpräzisen Addition, die Durchführung einer Simulationsoperation und die Simulation des Prozesses der vertikalen Berechnung.

Sie müssen zwei Zeiger, cur1 und cur2, so festlegen, dass sie jeweils auf zwei Zeichenfolgen zeigen, und dann eine Variable t festlegen, um den Übertrag darzustellen.

Code wie folgt anzeigen:

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

---

Thema vier:String-Multiplikation

Gegeben sind zwei nicht negative ganze Zahlen, die als Zeichenfolgen dargestellt werdennum1Undnum2,zurückkehrennum1Undnum2Das Produkt von wird auch in Stringform ausgedrückt.

Beachten:Sie können keine der integrierten BigInteger-Bibliotheken verwenden oder die Eingabe direkt in eine Ganzzahl konvertieren.

Beispiel 1:

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

Beispiel 2:

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

---

Lösung 1: Vertikale Operationen simulieren

In der Mathematik ist es die vertikale Form der Multiplikationsspalte. Dies ist die einfachste Methode, die man sich vorstellen kann.

Wie folgt:

Wir können es so verstehen, dass jede Ziffer der folgenden 456 mit der obigen 123 multipliziert und dann addiert wird, es gibt drei Details:

①Die Multiplikation höherer Ordnung muss mit 0 gefüllt werden, weil beim Addieren von 738 und 615 ein Bit falsch ist, was als 738 + 6150 verstanden werden kann
②Prozess führt 0, kann eine Situation von 123 × 0 auftreten. In diesem Fall lautet die Antwort 000 und muss verarbeitet werden.
③Achten Sie auf die Reihenfolge der Berechnungsergebnisse, da die Berechnung in umgekehrter Reihenfolge erfolgt und die Multiplikation ab der letzten Ziffer berechnet wird.

Diese Methode ist jedoch nicht einfach, Code zu schreiben. Wir müssen diese Methode verwenden, um ihn zu optimieren.

Lösung Zwei: Optimieren Sie Lösung Eins

Multiplizieren und addieren Sie ohne Übertrag, und der Übertrag wird im letzten Schritt verarbeitet:

Das heißt, egal wie viel multipliziert wird, es wird keinen Übertrag geben und der Übertrag wird nach der letzten Addition ausgeführt.

Wenn Sie mit der Berechnung beginnen, kehren Sie ebenfalls die Reihenfolge um. Da die Multiplikation zweistellig sein kann, kann keine Zeichenfolgendarstellung verwendet werden. Stattdessen kann ein Array zum Speichern verwendet werden

Da die Reihenfolge umgekehrt ist, ist der Index, der 123 entspricht, 2,1,0, und der Index, der 456 entspricht, ist ebenfalls 2,1,0

Es gibt eine sehr nützliche Regel: Die durch i und j tiefgestellten Zahlen werden multipliziert und das Ergebnis wird zufällig an der i + j-ten Position des Arrays platziert.

① Definieren Sie ein Array tmp mit einer Länge von m + n - 1 (m und n entsprechen den Längen zweier multiplizierter Zahlen).
Die Indizes der beiden zu multiplizierenden Zahlen sind i bzw. j, und das berechnete Ergebnis wird an der i + j-ten Position des Arrays platziert.
②Nach der letzten Addition muss der Übertrag verarbeitet werden
③Verarbeitung der führenden 0

Code wie folgt anzeigen:

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

---

Damit sind die stringbezogenen Fragen beendet