技術共有

アルゴリズム: 文字列関連

2024-07-12

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

目次

トピック 1: 最長の共通プレフィックス

質問 2: 最長の回文部分文字列

トピック 3: 2 進和

質問 4: 文字列の乗算

トピック 1:最長の共通プレフィックス

文字列の配列内で最も長い共通プレフィックスを見つける関数を作成します。

共通のプレフィックスが存在しない場合は、空の文字列を返します。""

例 1:

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

例 2:

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

ヒント：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]小文字の英字のみで構成されています

解決策 1: ペアごとの比較

最初の解決策は、ペアごとの比較戦略です。最初に最初の 2 つの文字列を比較し、その後、最初の 2 つの文字列の共通のプレフィックスを 3 番目の文字列と比較して、最初の 3 つの文字列の共通のプレフィックスを取得します。

コードは以下のように表示されます:

  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 の 2 つのポインターを設定し、j を移動するたびに、i と j の間の文字列が回文部分文字列であるかどうかを判断する必要があります。 j が移動され、i と j の間に回文部分文字列があるかどうかを判断すると、ここでの時間計算量は O(N^2) になります。また、外側にネストされた i の層があり、文字列全体を走査するために使用されます。暴力的な列挙時間全体の複雑さは非常に高く、O(N^3) に達します。最適化された中心拡張アルゴリズムを見てみましょう。

解決策: 中心拡張アルゴリズム

中心拡張アルゴリズムは次のとおりです。

①中心点を固定する
②中心点から開始して両側に拡張します（奇数と偶数の長さの両方を考慮する必要があります）

つまり、中心点 i は毎回固定され、毎回それが回文文字列であるかどうかを判断するために i の左右に展開されます。i を横断するこのアルゴリズムの時間計算量は O(N) です。入れ子になった方向は i の左と右です。拡張すると、時間計算量も O(N) になるため、最終的には O(N^2) となり、上記の暴力的な解決策よりもはるかに最適化されます。 。

注意する必要があるのは、中心拡張アルゴリズムの 2 番目の点です。奇数と偶数を考慮する必要があります。これは、奇数では左右のポインタが i 位置から左右に移動するのに対し、偶数では左右のポインタが移動する必要があるためです。左は i の位置、右は i + 1 の位置になり、その後、左右に移動します。

現在の left と right が同じ要素を指している場合は、left--、right++ に変更する必要があるため、コードの長さは right - left - 1 であることに注意してください。同じでない場合は、ループを終了します。 、回文文字列よりも左右の数が 1 つ移動しているため、長さは右 - 左 - 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. };

トピック 3:バイナリ合計

2 つのバイナリ文字列を与えてくださいaそしてb、それらの合計をバイナリ文字列として返します。

例 1:

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

例 2:

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

高精度加算の計算、シミュレーション演算の実行、垂直計算の過程のシミュレーションに関する問題です。

2 つのポインター cur1 と cur2 をそれぞれ 2 つの文字列を指すように設定し、キャリーを表す変数 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. };

トピック 4:文字列の乗算

文字列として表現された 2 つの非負の整数が与えられた場合num1そしてnum2、戻るnum1そしてnum2の積、彼らの積も文字列形式で表現されます。

知らせ：組み込み BigInteger ライブラリを使用したり、入力を整数に直接変換したりすることはできません。

例 1:

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

例 2:

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

解決策 1: 垂直方向の操作をシミュレートする

数学では、掛け算の列を縦に並べるのが一番考えやすい方法です。

次のように：

次の 456 の各桁に上の 123 を掛けて加算すると、3 つの詳細が得られると理解できます。

①上位の乗算は0で埋める必要があります。738 と 615 を加算するときに 1 ビットが間違っているため、738 + 6150 として理解できます。
②処理先頭0、123 × 0 の状況が発生する可能性があり、その場合、答えは 000 となるため、対処する必要があります。
③計算結果の順序に注意, 計算は逆の順序で行われ、乗算は最後の桁から計算されるためです。

しかし、この方法はコードを書くのが簡単ではありません。この方法を使用して最適化する必要があります。

ソリューション 2: ソリューション 1 を最適化する

キャリーなしで乗算と加算を行うと、キャリーは最後のステップで処理されます。

つまり、いくら乗算してもキャリーは発生せず、最終加算後にキャリーが行われます。

同様に、計算を開始するときは、最初に順序を逆にします。乗算は 2 桁になるため、代わりに配列を使用して格納できます。

順序が逆なので、123 に対応する添字は 2,1,0 となり、456 に対応する添字も 2,1,0 となります。

非常に便利なルールがあります。つまり、i と j で添字が付いた数値が乗算され、その結果が配列の i + j 番目の位置に配置されます。

①長さ m + n - 1 の配列 tmp を定義します (m と n は 2 つの乗算した数の長さに相当します)
乗算される 2 つの数値の添字はそれぞれ 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 などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料