Compartilhamento de tecnologia

Algoritmo: relacionado a string

2024-07-12

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

Índice

Tópico 1: O prefixo comum mais longo

Pergunta 2: A substring do palíndromo mais longa

Tópico 3: Soma binária

Pergunta 4: Multiplicando strings

Tópico um:prefixo comum mais longo

Escreva uma função para encontrar o prefixo comum mais longo em uma matriz de strings

Se não existir nenhum prefixo comum, retorna uma string vazia""

Exemplo 1:

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

Exemplo 2:

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

dica:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Consiste apenas em letras minúsculas do inglês

Solução 1: comparação em pares

A primeira solução é a estratégia de comparação entre pares. Primeiro compare as duas primeiras strings. Após a comparação, compare o prefixo comum das duas primeiras strings com a terceira string para obter o prefixo comum das três primeiras strings.

código mostrado abaixo:

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

Solução 2: comparação unificada

Comparação unificada significa comparar a mesma posição de todas as strings de uma só vez para determinar se as posições são as mesmas até que caracteres diferentes apareçam.

Haverá uma situação fora dos limites aqui. Se houver uma situação fora dos limites, significa que uma determinada string terminou e então a comparação pode ser encerrada.

código mostrado abaixo:

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

Tópico 2:substring do palíndromo mais longo

Dê-lhe uma cordas,virar para cimasA substring do palíndromo mais longa em

Exemplo 1:

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

Exemplo 2:

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

O algoritmo comum de enumeração de força bruta define dois ponteiros, um i e um j, fixa i e move j para trás. Cada vez que j é movido, é necessário determinar se a string entre i e j é uma substring do palíndromo. j é movido. E julgando se existe uma substring de palíndromo entre i e j, a complexidade de tempo aqui é O (N ^ 2), e como há uma camada de i aninhada externamente, que é usada para percorrer toda a string, o todo o tempo de enumeração violenta A complexidade é muito alta, chegando a O (N ^ 3). Vejamos o algoritmo de expansão central otimizado:

Solução: algoritmo de expansão central

O algoritmo de expansão central é:

①Conserte um ponto central
②Comece do ponto central e expanda para ambos os lados (comprimentos pares e ímpares precisam ser considerados)

Ou seja, um ponto central i é fixo a cada vez e cada vez é expandido para a esquerda e para a direita de i para determinar se é uma string palíndromo. A complexidade de tempo deste algoritmo que atravessa i é O(N), e a direção aninhada está à esquerda e à direita de i. Por extensão, a complexidade do tempo também é O(N), então no final é O(N^2), que é muito mais otimizado do que a solução violenta mencionada acima. .

O que precisa ser observado é o segundo ponto do algoritmo de expansão central. Os números pares e ímpares precisam ser considerados, porque os números ímpares movem os ponteiros esquerdo e direito da posição i para a esquerda e para a direita, enquanto os números pares exigem. esquerda para estar na posição i e direita para estar na posição i + 1. e, em seguida, mova para a esquerda e para a direita

Deve-se observar que o comprimento no código é direita - esquerda - 1, porque se a esquerda e a direita atuais apontam para o mesmo elemento, você precisa alterar para esquerda--, direita++. , portanto, há mais strings à esquerda e à direita do que no palíndromo. Ele se moveu uma posição, então o comprimento é calculado de direita - esquerda - 1. Veja a figura abaixo para obter detalhes:

Conforme mostrado na figura acima, a esquerda e a direita apontam para o ponto atual para sair do loop, então o comprimento da substring do palíndromo aa é:
direita - esquerda - 1 = 3 - 0 - 1 = 2

código mostrado abaixo:

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

Tópico três:Soma binária

Dê a você duas strings bináriasaeb, retornando sua soma como uma string binária.

Exemplo 1:

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

Exemplo 2:

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

Esta questão trata de calcular adição de alta precisão, realizar uma operação de simulação e simular o processo de cálculo vertical.

Você precisa definir dois ponteiros, cur1 e cur2, para apontar para duas strings respectivamente e, em seguida, definir uma variável t para representar carry.

código mostrado abaixo:

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

Tópico quatro:Multiplicação de cordas

Dados dois inteiros não negativos representados como stringsnum1enum2,retornarnum1enum2O produto de seu produto também é expresso em forma de string.

Perceber:Você não pode usar nenhuma das bibliotecas BigInteger integradas ou converter diretamente a entrada em um número inteiro.

Exemplo 1:

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

Exemplo 2:

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

Solução 1: Simule operações verticais

Em matemática, é a forma vertical da coluna de multiplicação. Este é o método mais fácil de pensar.

Do seguinte modo:

Podemos entendê-lo como se cada dígito dos 456 a seguir fosse multiplicado pelos 123 acima e, em seguida, somado, há três detalhes:

①A multiplicação de ordem superior precisa ser preenchida com 0, porque um bit está errado ao somar 738 e 615, que pode ser entendido como 738 + 6150
②Processo líder 0, pode ocorrer uma situação de 123 × 0, caso em que a resposta é 000 e precisa ser processada.
③Preste atenção à ordem dos resultados do cálculo, porque o cálculo é feito na ordem inversa e a multiplicação é calculada a partir do último dígito.

Mas esse método não é fácil de escrever código. Precisamos usá-lo para otimizá-lo.

Solução dois: otimizar a solução um

Multiplique e some sem transportar, e o transporte será processado na última etapa:

Ou seja, por mais que seja multiplicado, não haverá carry, e o carry será realizado após a adição final.

Da mesma forma, ao iniciar o cálculo, primeiro inverta a ordem. Como a multiplicação pode ter dois dígitos, a representação de string não pode ser usada.

Como a ordem é invertida, o subscrito correspondente a 123 é 2,1,0, e o subscrito correspondente a 456 também é 2,1,0

Existe uma regra muito útil: os números subscritos por i e j são multiplicados e o resultado é colocado na i + j-ésima posição do array.

① Defina uma matriz tmp com comprimento m + n - 1 (m e n correspondem aos comprimentos de dois números multiplicados)
Os subscritos dos dois números sendo multiplicados são i e j respectivamente, e o resultado calculado é colocado na i + j-ésima posição da matriz.
②Após a adição final, o transporte precisa ser processado
③Processamento inicial 0

código mostrado abaixo:

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

Isso encerra as questões relacionadas a strings

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de trinta anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc., e fez muitas contribuições no campo de código aberto. uma estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência