Обмен технологиями

Алгоритм: связанный со строкой

2024-07-12

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

Оглавление

Тема 1: Самый длинный общий префикс

Вопрос 2: Самая длинная подстрока палиндрома

Тема 3: Двоичная сумма

Вопрос 4: Умножение строк

Тема первая:самый длинный общий префикс

Напишите функцию для поиска самого длинного общего префикса в массиве строк.

Если общего префикса не существует, возвращает пустую строку.""

Пример 1:

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

Пример 2:

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

намекать:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Состоит только из строчных английских букв.

Решение 1. Парное сравнение

Первым решением является стратегия попарного сравнения. Сначала сравните первые две строки. После сравнения сравните общий префикс первых двух строк с третьей строкой, чтобы получить общий префикс первых трех строк, и так далее.

код показан ниже:

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

Решение 2. Единое сравнение

Унифицированное сравнение означает сравнение одинаковой позиции всех строк одновременно, чтобы определить, являются ли позиции одинаковыми, пока не появятся разные символы.

Здесь будет ситуация выхода за пределы. Если возникнет ситуация выхода за пределы, это означает, что определенная строка закончилась, и тогда сравнение можно прекратить.

код показан ниже:

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

Тема 2:самая длинная подстрока палиндрома

Дай тебе веревкуs,оказатьсяsСамая длинная подстрока палиндрома в

Пример 1:

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

Пример 2:

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

Обычный алгоритм перебора устанавливает два указателя, один i и один j, фиксирует i и перемещает j назад. Каждый раз, когда j перемещается, необходимо определить, является ли строка между i и j подстрокой-палиндромом. j перемещается. И судя по тому, существует ли подстрока-палиндром между i и j, временная сложность здесь равна O(N^2), а поскольку снаружи есть слой i, который используется для обхода всей строки. все время насильственного перебора. Сложность очень высока, достигает O(N^3). Давайте посмотрим на оптимизированный алгоритм расширения центра:

Решение: алгоритм расширения центра

Алгоритм расширения центра:

①Зафиксируйте центральную точку
②Начните с центральной точки и расширяйте в обе стороны (необходимо учитывать как нечетную, так и четную длину)

То есть центральная точка i фиксируется каждый раз, и каждый раз она расширяется слева и справа от i, чтобы определить, является ли она строкой-палиндромом. Временная сложность этого алгоритма, пересекающего i, равна O (N), и вложенное направление находится слева и справа от i. В более широком смысле, временная сложность также равна O (N), поэтому в конечном итоге она равна O (N ^ 2), что гораздо более оптимизировано, чем упомянутое выше принудительное решение. .

Необходимо отметить второй пункт алгоритма расширения центра. Необходимо учитывать нечетные и четные числа, поскольку нечетные числа перемещают левый и правый указатели из позиции i влево и вправо, а четные числа требуют этого. влево, чтобы оказаться в позиции i, и вправо, чтобы оказаться в позиции i + 1., а затем двигаться влево и вправо

Следует отметить, что длина в коде равна right-left-1, потому что если текущие left и right указывают на один и тот же элемент, нужно изменить left--, right++. Если они не совпадают, выйти из цикла. , поэтому левых и правых строк больше, чем строк палиндрома. Он переместился на одну позицию, поэтому длина рассчитывается от правого до левого - 1. Подробности см. на рисунке ниже:

Как показано на рисунке выше, левая и правая точки указывают на текущую точку выхода из цикла, поэтому длина подстроки палиндрома aa равна:
право - лево - 1 = 3 - 0 - 1 = 2

код показан ниже:

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

Тема третья:Двоичная сумма

Дайте вам две двоичные строкиaиb, возвращая их сумму в виде двоичной строки.

Пример 1:

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

Пример 2:

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

Этот вопрос касается расчета высокоточного сложения, выполнения операции моделирования и моделирования процесса вертикального расчета.

Вам нужно установить два указателя, cur1 и cur2, чтобы они указывали на две строки соответственно, а затем установить переменную t для представления переноса.

код показан ниже:

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

Тема четвертая:Умножение строк

Даны два неотрицательных целых числа, представленных в виде строк.num1иnum2,возвращатьсяnum1иnum2Продукт , их продукт также выражается в строковой форме.

Уведомление:Вы не можете использовать ни одну из встроенных библиотек BigInteger или напрямую преобразовать входные данные в целое число.

Пример 1:

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

Пример 2:

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

Решение 1. Имитируйте вертикальные операции

В математике это вертикальная форма столбца умножения. Это самый простой метод.

Следующее:

Мы можем понять это так: каждая цифра из следующих 456 умножается на приведенные выше 123, а затем добавляется три детали:

①Умножение старшего порядка должно быть заполнено 0., потому что при сложении 738 и 615 ошибается один бит, что можно понимать как 738 + 6150
②Руководство процесса 0, может возникнуть ситуация 123 × 0, в этом случае ответ 000 и его необходимо обработать.
③Обратите внимание на порядок результатов расчета., поскольку расчет ведется в обратном порядке, а умножение ведется от последней цифры.

Но этот метод нелегко писать. Нам нужно использовать этот метод для его оптимизации.

Решение второе: оптимизировать решение первое

Умножение и сложение без переноса, а перенос обрабатывается на последнем шаге:

То есть сколько бы ни умножалось, переноса не будет, а перенос будет осуществляться после окончательного сложения.

Аналогично, при запуске вычислений сначала измените порядок. Поскольку умножение может быть двухзначным, строковое представление использовать нельзя. Вместо этого для хранения можно использовать массив.

Поскольку порядок обратный, нижний индекс, соответствующий 123, равен 2,1,0, а нижний индекс, соответствующий 456, также равен 2,1,0.

Есть очень полезное правило: числа с индексами i и j умножаются, и результат оказывается на i + j-й позиции массива.

① Определите массив tmp длиной m + n – 1 (m и n соответствуют длинам двух умноженных чисел)
Индексы двух умножаемых чисел равны i и j соответственно, а вычисленный результат помещается в i + j-ю позицию массива.
②После окончательного сложения перенос необходимо обработать.
③Обработка ведущего 0

код показан ниже:

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

На этом вопросы, связанные со строками, заканчиваются.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта