Compartir tecnología

Algoritmo: relacionado con cadenas

2024-07-12

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

Tabla de contenido

Tema 1: El prefijo común más largo

Pregunta 2: la subcadena palíndromo más larga

Tema 3: Suma binaria

Pregunta 4: Multiplicar cadenas

Tema uno:prefijo común más largo

Escriba una función para encontrar el prefijo común más largo en una matriz de cadenas

Si no existe un prefijo común, devuelve una cadena vacía""

Ejemplo 1:

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

Ejemplo 2:

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

pista:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Consta únicamente de letras inglesas minúsculas.

Solución 1: comparación por pares

La primera solución es la estrategia de comparación por pares. Primero compare las dos primeras cadenas. Después de la comparación, compare el prefijo común de las dos primeras cadenas con la tercera cadena para obtener el prefijo común de las tres primeras cadenas, y así sucesivamente.

El código se muestra a continuación:

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

Solución 2: comparación unificada

La comparación unificada significa comparar la misma posición de todas las cadenas a la vez para determinar si las posiciones son las mismas hasta que aparecen caracteres diferentes.

Habrá una situación fuera de límites aquí. Si hay una situación fuera de límites, significa que una determinada cadena ha finalizado y luego se puede finalizar la comparación.

El código se muestra a continuación:

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

Tema 2:subcadena palíndromo más larga

darte una cuerdas,aparecersLa subcadena palíndromo más larga en

Ejemplo 1:

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

Ejemplo 2:

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

El algoritmo de enumeración de fuerza bruta ordinario establece dos punteros, uno i y otro j, fija i y mueve j hacia atrás. Cada vez que se mueve j, es necesario determinar si la cadena entre i y j es una subcadena palíndromo. j se mueve. Y al juzgar si hay una subcadena palíndromo entre i y j, la complejidad del tiempo aquí es O (N ^ 2), y debido a que hay una capa de i anidada afuera, que se usa para atravesar toda la cadena, la todo el tiempo de enumeración violenta La complejidad es muy alta y alcanza O (N ^ 3). Veamos el algoritmo de expansión central optimizado:

Solución: algoritmo de expansión central

El algoritmo de expansión central es:

①Fijar un punto central
②Comience desde el punto central y expanda hacia ambos lados (se deben considerar las longitudes pares e impares)

Es decir, se fija un punto central i cada vez, y cada vez se expande hacia la izquierda y hacia la derecha de i para determinar si es una cadena palíndromo. La complejidad temporal de este algoritmo que atraviesa i es O (N). y la dirección anidada está a la izquierda y a la derecha de i. Por extensión, la complejidad del tiempo también es O (N), por lo que al final es O (N ^ 2), que está mucho más optimizada que la solución violenta mencionada anteriormente. .

Lo que hay que tener en cuenta es que se deben tener en cuenta los números pares e impares del segundo punto del algoritmo de expansión central, porque los números impares mueven los punteros izquierdo y derecho desde la posición i hacia la izquierda y la derecha, mientras que los números pares requieren. izquierda para estar en la posición i y derecha para estar en la posición i + 1, y luego moverse hacia la izquierda y hacia la derecha

Cabe señalar que la longitud en el código es derecha-izquierda-1, porque si la izquierda y la derecha actuales apuntan al mismo elemento, debe cambiar izquierda--, derecha++, si no son iguales, salga del ciclo. , por lo que hay más cadenas izquierda y derecha que palíndromos. Se ha movido una posición, por lo que la longitud se calcula de derecha a izquierda - 1. Consulte la figura a continuación para obtener más detalles:

Como se muestra en la figura anterior, la izquierda y la derecha apuntan al punto actual para salir del bucle, por lo que la longitud de la subcadena palíndromo aa es:
derecha - izquierda - 1 = 3 - 0 - 1 = 2

El código se muestra a continuación:

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

Tema tres:Suma binaria

Darte dos cadenas binariasayb, devolviendo su suma como una cadena binaria.

Ejemplo 1:

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

Ejemplo 2:

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

Esta pregunta trata sobre el cálculo de la suma de alta precisión, la realización de una operación de simulación y la simulación del proceso de cálculo vertical.

Debe configurar dos punteros, cur1 y cur2, para que apunten a dos cadenas respectivamente, y luego configurar una variable t para representar el acarreo.

El código se muestra a continuación:

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

Tema cuatro:Multiplicación de cadenas

Dados dos números enteros no negativos representados como cadenasnum1ynum2,devolvernum1ynum2El producto de , su producto también se expresa en forma de cadena.

Aviso:No puede utilizar ninguna de las bibliotecas integradas de BigInteger ni convertir directamente la entrada a un número entero.

Ejemplo 1:

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

Ejemplo 2:

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

Solución 1: Simular operaciones verticales

En matemáticas, es la forma vertical de la columna de multiplicación. Este es el método más fácil de imaginar.

Como sigue:

Podemos entenderlo como, cada dígito del siguiente 456 se multiplica por el 123 anterior y luego se suma, hay tres detalles:

①La multiplicación de orden superior debe completarse con 0, porque un bit falla al sumar 738 y 615, lo que puede entenderse como 738 + 6150
②Proceso líder 0, puede ocurrir una situación de 123 × 0, en cuyo caso la respuesta es 000 y debe procesarse.
③Preste atención al orden de los resultados del cálculo., porque el cálculo se realiza en orden inverso y la multiplicación se calcula a partir del último dígito.

Pero este método no es fácil de escribir código. Necesitamos utilizar este método para optimizarlo.

Solución dos: optimizar la solución uno

Multiplica y suma sin acarreo, y el acarreo se procesa en el último paso:

Es decir, no importa cuánto se multiplique, no habrá acarreo y el acarreo se realizará después de la suma final.

De manera similar, al comenzar el cálculo, primero invierta el orden. Dado que la multiplicación puede tener dos dígitos, no se puede usar la representación de cadena. En su lugar, se puede usar una matriz para almacenar.

Como el orden está invertido, el subíndice correspondiente a 123 es 2,1,0 y el subíndice correspondiente a 456 también es 2,1,0

Hay una regla muy útil: los números subíndices de i y j se multiplican y el resultado se coloca en la posición i + j de la matriz.

① Defina una matriz tmp con una longitud de m + n - 1 (m y n corresponden a las longitudes de dos números multiplicados)
Los subíndices de los dos números que se multiplican son i y j respectivamente, y el resultado calculado se coloca en la posición i + j de la matriz.
②Después de la adición final, es necesario procesar el acarreo.
③Procesamiento inicial 0

El código se muestra a continuación:

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

Esto finaliza las preguntas relacionadas con cadenas.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de treinta años, domina varios lenguajes como java, linux, javascript, php, css, etc., y ha realizado muchas contribuciones en el campo del código abierto. una estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo