Partage de technologie

Algorithme : lié aux chaînes

2024-07-12

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

Table des matières

Sujet 1 : Le préfixe commun le plus long

Question 2 : la sous-chaîne palindrome la plus longue

Thème 3 : Somme binaire

Question 4 : Multiplier des chaînes

Premier sujet :préfixe commun le plus long

Écrivez une fonction pour trouver le préfixe commun le plus long dans un tableau de chaînes

Si aucun préfixe commun n'existe, renvoie une chaîne vide""

Exemple 1:

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

Exemple 2 :

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

indice:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Se compose uniquement de lettres anglaises minuscules

Solution 1 : comparaison par paires

La première solution est la stratégie de comparaison par paire.Comparez d'abord les deux premières chaînes.Après la comparaison, comparez le préfixe commun des deux premières chaînes avec la troisième chaîne pour obtenir le préfixe commun des trois premières chaînes, et ainsi de suite.

le code s'affiche comme ci-dessous :

  1. class Solution 
  2. {
  3. public:
  4.     string findCommon(string& s1, string& s2)
  5.     {
  6.         int i = 0;
  7.         //i有可能会出现越界的情况，所以i小于s1s2长度时再循环判断
  8.         while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
  9.             i++;
  10.         return s1.substr(0, i);
  11.     }
  12.  
  13.     string longestCommonPrefix(vector<string>& strs) 
  14.     {
  15.         int n = strs.size();
  16.         //same字符串就是存储最长公共前缀的字符串
  17.         string same = strs[0];
  18.         for(int i = 1; i < n; i++)
  19.             same = findCommon(same, strs[i]);
  20.         return same;
  21.     }
  22. };

Solution 2 : comparaison unifiée

La comparaison unifiée consiste à comparer la même position de toutes les chaînes en même temps pour déterminer si les positions sont les mêmes jusqu'à ce que des caractères différents apparaissent.

Il y aura une situation hors limites ici. S'il y a une situation hors limites, cela signifie qu'une certaine chaîne est terminée, et la comparaison peut alors être terminée.

le code s'affiche comme ci-dessous :

  1. class Solution 
  2. {
  3. public:
  4.     string longestCommonPrefix(vector<string>& strs) 
  5.     {
  6.         int i = 0;
  7.         //以第一个字符串为基准，与其他所有字符串做比较
  8.         for(i = 0; i < strs[0].size(); i++)
  9.         {
  10.             //ch表示第一个字符串当前循环到的字符
  11.             char ch = strs[0][i];
  12.             //循环strs中其余的字符串，其余字符串的i位置字符与ch做比较
  13.             for(int j = 1; j < strs.size(); j++)
  14.             {  
  15.                 //如果i大于当前字符串的长度，说明当前字符串已经没有元素了
  16.                 if(i > strs[j].size() || strs[j][i] != ch)
  17.                     return strs[0].substr(0, i);
  18.             }
  19.         }
  20.         return strs[0];
  21.     }
  22. };

Thème 2 :sous-chaîne palindrome la plus longue

Donnez-vous une chaînes,venezsLa sous-chaîne palindrome la plus longue de

Exemple 1:

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

Exemple 2 :

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

L'algorithme d'énumération par force brute ordinaire définit deux pointeurs, un i et un j, corrige i et déplace j vers l'arrière. Chaque fois que j est déplacé, il est nécessaire de déterminer si la chaîne entre i et j est une sous-chaîne palindrome. j est déplacé. Et à en juger s'il existe une sous-chaîne palindrome entre i et j, la complexité temporelle est ici O (N ^ 2), et comme il y a une couche de i imbriquée à l'extérieur, qui est utilisée pour parcourir toute la chaîne, la tout le temps d'énumération violente La complexité est très élevée, atteignant O(N^3). Regardons l'algorithme d'expansion centrale optimisé :

Solution : Algorithme d’expansion centrale

L’algorithme d’expansion du centre est :

①Fixer un point central
②Commencez par le point central et étendez-vous des deux côtés (les longueurs paires et impaires doivent être prises en compte)

C'est-à-dire qu'un point central i est fixé à chaque fois, et à chaque fois il est étendu à gauche et à droite de i pour déterminer s'il s'agit d'une chaîne palindrome. La complexité temporelle de cet algorithme traversant i est O(N), et la direction imbriquée est à gauche et à droite de i. Par extension, la complexité temporelle est également O(N), donc au final c'est O(N^2), ce qui est bien plus optimisé que la solution violente mentionnée ci-dessus. .

Ce qu'il faut noter, c'est le deuxième point de l'algorithme d'expansion centrale. Les nombres impairs et pairs doivent être pris en compte, car les nombres impairs déplacent les pointeurs gauche et droit de la position i vers la gauche et la droite, tandis que les nombres pairs l'exigent. gauche pour être en position i et droite pour être en position i + 1., puis déplacez-vous vers la gauche et la droite

Il convient de noter que la longueur dans le code est droite - gauche - 1, car si la gauche et la droite actuelles pointent vers le même élément, vous devez changer left--, right++. Si elles ne sont pas identiques, quittez la boucle. , il y a donc plus de chaînes gauche et droite que de palindrome. Il s'est déplacé d'une position, donc la longueur est calculée de droite à gauche - 1. Voir la figure ci-dessous pour plus de détails :

Comme le montre la figure ci-dessus, la gauche et la droite pointent vers le point actuel pour quitter la boucle, donc la longueur de la sous-chaîne palindrome aa est :
droite - gauche - 1 = 3 - 0 - 1 = 2

le code s'affiche comme ci-dessous :

  1. class Solution 
  2. {
  3. public:
  4.     string longestPalindrome(string s) 
  5.     {
  6.         if(s.size() == 1) return s;
  7.         int n = s.size(), begin = 0, size = 0;
  8.         for(int i = 0; i < n; i++)
  9.         {
  10.             //先做奇数长度的扩展
  11.             int left = i, right = i;
  12.             //left和right符合条件，且指向元素相等再进入循环
  13.             while(left >= 0 && right < n && s[left] == s[right])
  14.             {
  15.                 --left;
  16.                 ++right;
  17.             }
  18.             //如果长度更大，更新begin与size
  19.             if((right - left - 1) > size)
  20.             {
  21.                 size = right - left - 1;
  22.                 begin = left + 1;
  23.             }
  24.             //再做偶数长度的扩展
  25.             left = i, right = i + 1;
  26.             //left和right符合条件，且指向元素相等再进入循环
  27.             while(left >= 0 && right < n && s[left] == s[right])
  28.             {
  29.                 --left;
  30.                 ++right;
  31.             }
  32.             //如果长度更大，更新begin与size
  33.             if((right - left - 1) > size)
  34.             {
  35.                 size = right - left - 1;
  36.                 begin = left + 1;
  37.             }            
  38.         }
  39.         return s.substr(begin, size);
  40.     }
  41. };

Troisième sujet :Somme binaire

Donnez-vous deux chaînes binairesaetb, renvoyant leur somme sous forme de chaîne binaire.

Exemple 1:

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

Exemple 2 :

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

Cette question concerne le calcul d'une addition de haute précision, la réalisation d'une opération de simulation et la simulation du processus de calcul vertical.

Vous devez définir deux pointeurs, cur1 et cur2, pour pointer respectivement vers deux chaînes, puis définir une variable t pour représenter le report.

le code s'affiche comme ci-dessous :

  1. class Solution 
  2. {
  3. public:
  4.     string addBinary(string a, string b) 
  5.     {
  6.         //t表示相加后的进位
  7.         int t = 0;
  8.         string ret;
  9.         int cur1 = a.size()-1, cur2 = b.size()-1;
  10.         //cur1或cur2 >= 0表示字符串没遍历完，t>0表示还剩一个进位
  11.         while(cur1 >= 0 || cur2 >= 0 || t)
  12.         {
  13.             if(cur1 >= 0) t += a[cur1--] - '0';  
  14.             if(cur2 >= 0) t += b[cur2--] - '0';
  15.             ret += to_string(t % 2);
  16.             t /= 2;
  17.         }
  18.         //从后向前加的，刚好反过来了，需要逆置
  19.         reverse(ret.begin(), ret.end());
  20.         return ret;
  21.     }
  22. };

Thème quatre :Multiplication de chaînes

Étant donné deux entiers non négatifs représentés sous forme de chaînesnum1etnum2,retournum1etnum2Le produit de , leur produit est également exprimé sous forme de chaîne.

Avis:Vous ne pouvez utiliser aucune des bibliothèques BigInteger intégrées ni convertir directement l'entrée en entier.

Exemple 1:

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

Exemple 2 :

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

Solution 1 : Simuler les opérations verticales

En mathématiques, c'est la forme verticale de la colonne de multiplication. C'est la méthode la plus simple à laquelle penser.

Comme suit:

Nous pouvons le comprendre car chaque chiffre des 456 suivants est multiplié par le 123 ci-dessus, puis ajouté, il y a trois détails :

①La multiplication d'ordre supérieur doit être remplie par 0, car un bit est faux lors de l'ajout de 738 et 615, ce qui peut être compris comme 738 + 6150
②Processus menant à 0, une situation de 123 × 0 peut se produire, auquel cas la réponse est 000 et doit être traitée.
③Faites attention à l'ordre des résultats du calcul, car le calcul est effectué dans l'ordre inverse et la multiplication est calculée à partir du dernier chiffre.

Mais cette méthode n'est pas facile pour écrire du code. Nous devons utiliser cette méthode pour l'optimiser.

Solution 2 : optimiser la solution 1

Multipliez et ajoutez sans report, et le report est traité à la dernière étape :

Autrement dit, quel que soit le montant multiplié, il n'y aura pas de report et le report sera effectué après l'addition finale.

De même, lorsque vous démarrez le calcul, inversez d'abord l'ordre. Puisque la multiplication peut être à deux chiffres, la représentation sous forme de chaîne ne peut pas être utilisée. Au lieu de cela, un tableau peut être utilisé pour stocker.

Puisque l'ordre est inversé, l'indice correspondant à 123 est 2,1,0, et l'indice correspondant à 456 est également 2,1,0

Il existe une règle très utile : les nombres indicés par i et j sont multipliés et le résultat se trouve être placé à la position i + j du tableau.

① Définir un tableau tmp d'une longueur de m + n - 1 (m et n correspondent aux longueurs de deux nombres multipliés)
Les indices des deux nombres multipliés sont respectivement i et j, et le résultat calculé est placé à la position i + j du tableau.
②Après l'ajout final, le report doit être traité
③Traitement menant 0

le code s'affiche comme ci-dessous :

  1. class Solution 
  2. {
  3. public:
  4.     string multiply(string num1, string num2) 
  5.     {
  6.         //先逆序两个字符串
  7.         reverse(num1.begin(), num1.end());
  8.         reverse(num2.begin(), num2.end());
  9.         //定义一个数组tmp
  10.         int m = num1.size(), n = num2.size();
  11.         vector<int> tmp(m + n - 1);
  12.         //无进位相乘然后相加
  13.         for(int i = 0; i < m; i++)
  14.             for(int j = 0; j < n; j++)
  15.                 tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
  16.         //处理进位
  17.         string ret;
  18.         int t = 0, cur = 0;
  19.         while(cur < m + n - 1 || t != 0)
  20.         {
  21.             if(cur < m + n - 1) t += tmp[cur++];
  22.             ret += to_string(t % 10);
  23.             t /= 10;
  24.         }
  25.         if(t) ret += to_string(t);
  26.         //处理前置0
  27.         while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
  28.         reverse(ret.begin(), ret.end());
  29.  
  30.         return ret;
  31.     }
  32. };

Ceci met fin aux questions liées aux chaînes

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail