。最も近い回文を見つける

564。最も近い回文を見つけます

難易度: 難しい

トピック: 数学、文字列

整数を表す文字列 n が与えられた場合、_最も近い整数 (それ自体は含まない) を返します。これは回文です。同点の場合は、小さい方を返します。

最も近いものは、2 つの整数の間で最小化された絶対差として定義されます。

例 1:

• 入力: n = "123"
• 出力: "121"

例 2:

• 入力: n = "1"
• 出力: "0"
• 説明: 0 と 2 は最も近い回文ですが、最小の 0 を返します。

制約:

• 1
• n は数字のみで構成されます。
• n には先行ゼロがありません。
• n は [1, 10¹⁸ - 1] の範囲の整数を表します。

ヒント:

1. この問題にはブルートフォースが有効でしょうか?別のことを考えてください。
2. 1234、999、1000 などの例をいくつか取り上げ、それらに最も近い回文を確認してください。さまざまなケースが何通り考えられますか?
3. 文字列の左半分だけを考慮する必要がありますか?
4. これらの数字から最も近い回文を見つけてください - 12932、99800、12120。何か観察しましたか?

解決策:

潜在的な回文候補を生成し、入力数値に最も近いものを選択する関数の作成に焦点を当てます。

解決策のアプローチ:

1. 回文候補の特定:

   • 数字の前半をミラーリングして回文を形成します。
   • すべての数字が 9、100...001、または 99...99 であるなどの特殊なケースを考慮してください。
   • 数値の中央を 1 ずつ上下に変更して回文を生成します。

2. 最も近い回文を計算します:

   • 各回文候補について、元の数値との差の絶対値を計算します。
   • 差が最小の回文を返します。同点の場合は、小さい方の回文を返します。

このソリューションを PHP で実装してみましょう: 564。最も近い回文を見つけます

<?php
/**
* @param String $n
* @return String
*/
function nearestPalindromic($n) {
    ...
    ...
    ...
    /**
     * go to https://github.com/mah-shamim/leet-code-in-php/tree/main/algorithms/000564-find-the-closest-palindrome/solution.php
     */
}

function generatePalindrome($firstHalf, $isOddLength) {
    ...
    ...
    ...
}

// Example usage
echo nearestPalindromic("123"); // Output: "121"
echo nearestPalindromic("1");   // Output: "0"
?>

説明：

• generatePalindrome($firstHalf, $isOddLength):
  • このヘルパー関数は、数値の前半をミラーリングして回文を作成します。

<?php
/**
* @param $firstHalf
* @param $isOddLength
* @return string
*/
function generatePalindrome($firstHalf, $isOddLength) {
    $secondHalf = strrev(substr($firstHalf, 0, $isOddLength ? -1 : $firstHalf));
    return $firstHalf . $secondHalf;
}
?>

• エッジケース:

  • 100...001 や 99...99 などの数値から生成された回文は、これらのケースを明示的にチェックすることで処理されます。

• メインロジック:

  • 考えられる回文を計算し、絶対差を比較することで最も近い回文を見つけます。

このソリューションは、考えられる回文の候補を効率的に絞り込み、少数のオプションのみを考慮して最も近いものを選択するため、総当たりのアプローチよりもはるかに高速になります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。最も近い回文を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。