。最大スワップ

670。最大スワップ

難易度: 中

トピック: 数学、貪欲

整数が与えられます。最大値の数値を取得するために、最大 2 桁を 1 回交換できます。

取得できる最大値を返します。

例 1:

• 入力: 数値 = 2736
• 出力: 7236
• 説明: 数字の 2 と数字の 7 を交換します。

例 2:

• 入力: 数値 = 9973
• 出力: 9973
• 説明: スワップはありません。

制約:

• 0 8

解決策:

私たちは貪欲なアプローチに従うことができます。段階的な説明と解決策は次のとおりです:

アプローチ：

1. 数値を配列に変換する: 数字を交換する必要があるため、数値を数字の配列に変換すると、個々の数字へのアクセスと操作が容易になります。
2. 各数字の右端の出現を追跡: 各数字 (0 ～ 9) の右端の位置を配列に保存します。
3. 最適な交換機会を見つける: 番号の桁を左から右に移動し、各桁について、後で表示される上位の桁があるかどうかを確認します。その場合は、それらを交換して数を最大化します。
4. スワップと中断を実行します: 最適なスワップが見つかるとすぐに、スワップを実行してループを中断します。
5. 配列を数値に戻す: 交換後、数字の配列を数値に変換して返します。

このソリューションを PHP で実装してみましょう: 670。最大スワップ

<?php
/**
 * @param Integer $num
 * @return Integer
 */
function maximumSwap($num) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
echo maximumSwap(2736); // Output: 7236
echo maximumSwap(9973); // Output: 9973
?>

説明：

• ステップ 1: strval($num) は整数を文字列に変換し、str_split($numStr) はそれを数字の配列に分割します。
• ステップ 2: 最後の配列は、0 から 9 までの各桁の右端のインデックスを追跡します。
• ステップ 3: 各桁を反復処理し、交換可能なより大きな桁を探します。
• ステップ 4: 適切な大きい桁が見つかった場合 (数値の後ろに表示されます)、桁が交換されます。
• ステップ 5: 変更された配列は文字列に変換され、次に intval() を使用して整数に変換されます。

複雑：

• 時間計算量: O(n)、n は num の桁数です。これは、最後の配列を埋めるために数値を通過させ、最適なスワップを見つけるために別のパスを実行するためです。
• 空間複雑度: 最後の配列が 10 要素で固定されているため、O(1) (入力サイズを無視)。

このソリューションは、必要に応じて数字を 1 回だけ交換することで最大値を効率的に見つけます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が。最大スワップの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。