20200202 千年に一度の対称性の日、すべての「回文アルゴリズム」をキャッチする時が来ました!

[[313923]]

今日は2020年2月2日、「千年に一度の対称の日」として知られています。20200202は表でも裏でも同じで、どちらも「愛しています、愛しています」という意味です。多くの新婚夫婦が今日を結婚証明書を取得する日として選んだが、肺炎のため、いくつかの場所では今日の予約がキャンセルされた。

しかし、今日はこの日の意味について話すのではなく、テクノロジー関連のトピックについて話しましょう。

20200202 このように順方向と逆方向で同じ文字列を、アルゴリズムでは「回文」と呼びます。構造が異なるため、回文数、回文文字列、回文リンクリストなどに分類されます。

これにより、Leetcode のアルゴリズムにいくつかの問題が発生します。今日、他の人が結婚証明書を取得する日に、「回文」に関連するアルゴリズムの問題を確認します。

1. 回文文字列を検証する

今日の日付を文字列で表すと、「20200202」となり、回文文字列になります。

したがって、回文文字列であるかどうかを確認するメソッドを記述する場合、最も簡単な方法は文字列を反転して比較することです。

ブール型isPalindrome(文字列s) {
新しい StringBuilder(s).reverse().equals(s)を返します。
}

しかし、ほとんどの場合、API を直接使用することはできません。それ以外では、2 つのポインターを使用して、文字列の前後方向から内側にクランプする方法がより一般的です。

ブール型isPalindrome(文字列s) {
整数i = 0;
 int j = s.length() - 1;
  i < j の場合
    if (文字.toLowerCase(s.charAt(i) !=文字.toLowerCase(s.charAt(j))) {
戻る 間違い;
    }
    私は++;
    j --;  
  }
戻る 真実;
 }

ロジックはシンプルで、1 つのループと 2 つのポインターで完了します。

ただし、これは文字列なので、文字列の長さを取得するのは簡単です。そのため、一般的なアルゴリズムの問題では、いくつかの追加条件が追加され、難易度が上がります。

たとえば、Leetcode の「125. 回文を検証する」では、指定された文字列にスペースが含まれています。

この場合、前のソリューションを修正するだけです。 2 つのポインターが移動しているときにスペースに遭遇すると、もう 1 ステップ進みます。

パブリックブール値isPalindrome(文字列s) {
 int i = 0、j = s.length() - 1;
  i < j の場合{
    while(i < j && !文字.isLetterOrDigit(s.charAt(i)))
      私は++;
    while(i < j && !文字.isLetterOrDigit(s.charAt(j)))
      j --;  
    if(文字.toLowerCase(s.charAt(i)) !=
文字.toLowerCase(s.charAt(j)))
戻る 間違い;
    i++; j --;  
  }
戻る 真実;
 }

isLetterOrDigit() を使用すると、現在の文字が文字と数字のみであるかどうかを直接判断できます。

文字列の回文アルゴリズムについては、125 のほか、Leetcode の質問 680 も回文文字列に属します。興味があれば、調べてみてください。

2. 回文の数を確認する

回文文字列に数字のみが含まれている場合は、20200202 などの回文数字になることもあります。

回文を検証する場合、比較的簡単な方法は、回文を文字列に変換してから、文字の回文を検証するためのアルゴリズムパターンを適用することです。しかし、これは数字の特性を利用していません。

これは数値なので、割り算 / と剰余 % を使用して数値の後半部分を取り出し、反転してから、2 つの数値が等しいかどうかを比較できます。

パブリックブール値isPalindrome( int x) {
  (x < 0 || (x % 10 == 0 && x != 0))の場合
戻る 間違い;
 int戻された数値 = 0;
  while (x > 戻された数値) {
    戻された数値 = 戻された数値 * 10 + x % 10;
    x /= 10;
  }
 x == 戻された数値 || x == 戻された数値 / 10 を返します。
 }

簡単な説明:

1. まず簡単な検証を行ってください。 0 より大きい非ゼロの数値の一の位に 0 がある場合、それは間違いなく回文ではありません。対応する回文の位置はこの数値の最上位ビットであり、最上位ビットは 0 にならないためです。

2. ループを通じて、各ループで反転された数字がビットごとに生成され、元の数字の最下位ビットが削除されます。

3. ループが終了した場合、後半部分が反転されたことを意味します。次に、数値の長さが奇数か偶数かという 2 つのケースを検討します。次に、元の数値 x と、後半部分を反転した反転した数値 (reverseNumber) が同じかどうかを判断します。

ちなみに、この質問は、Leetcode の「9. 回文」の質問です。

3. 回文リストを確認する

回文文字列と回文数について説明したので、次は回文連結リストについて見てみましょう。

単一リンクリストのような特殊な構造の場合、その長さを決定するには O(n) の計算量が必要であり、先行ポインタが存在しないため、ダブルポインタを使用して前後をクランプする方法は使用できません。

もちろん、計算のためにおなじみの回文数や回文文字列に変換することもできますが、これもリンクリストの特性を利用していません。

回文リンクリストを検証するシナリオでは、高速ポインターと低速ポインターを使用してリンクリストの中間ノードを見つけ、元のリンクリストの半分を逆にしてから比較を開始できます。

効率性を高めるために、これら 2 つのステップを 1 つのループに組み合わせることができます。

パブリックブール値isPalindrome(ListNode head) {
  if(head == null || head.next == null ) {
戻る 真実;
  }
  ListNode 遅い = ヘッド、速い = ヘッド;
  ListNode pre = head、prepre = null ;
  while ( fast != null && fast.next != null ) {
    pre = 遅い;
    遅い = slow.next ;
    高速= fast.next.next ;
    pre.next = prepre;
    prepre = プレ;
  }
  // fast がnullでない場合は奇数なので増分する必要があることを意味します
  if (fast != null ) {
    遅い = slow.next ;
  }
  // このとき、preは元のリンクリストの前半を反転したサブリンクリストです
  // slow は元のリンクリストの中間ノードです
  while(pre != null && slow != null ) {
    if(pre.val != slow.val) {
戻る 間違い;
    }
    pre = pre.next ;
    遅い = slow.next ;
  }
戻る 真実;
 }