Group All s Together II への最小スワップ

2134。すべての 1 をグループ化するための最小スワップ II

中

スワップは、配列内の 2 つの 異なる 位置を取得し、それらの値を交換することとして定義されます。

円形配列は、最初の要素と最後の要素が隣接していると見なされる配列として定義されます。

バイナリ循環配列番号を指定すると、配列内に存在するすべての 1 を 任意の場所でグループ化するために必要なスワップの最小数を返します。

例 1:

• 入力: 数値 = [0,1,0,1,1,0,0]
• 出力: 1
• 説明: すべての 1 をグループ化する方法をいくつか示します。
  • [0,0,1,1,1,0,0] 1 スワップを使用します。
  • [0,1,1,1,0,0,0] 1 スワップを使用します。
  • [1,1,0,0,0,0,1] 2 つのスワップを使用します (配列の循環プロパティを使用)。
  • スワップが 0 の場合、すべての 1 をグループ化する方法はありません。
  • したがって、必要なスワップの最小数は 1 です。

例 2:

• 入力: 数値 = [0,1,1,1,0,0,1,1,0]
• 出力: 2
• 説明: すべての 1 をグループ化する方法をいくつか示します。
  • [1,1,1,0,0,0,0,1,1] (配列の循環プロパティを使用) 2 つのスワップを使用します。
  • [1,1,1,1,1,0,0,0,0] 2 つのスワップを使用します。
  • 0 または 1 のスワップですべての 1 をグループ化する方法はありません。
  • したがって、必要なスワップの最小数は 2 です。

例 3:

• 入力: 数値 = [1,1,0,0,1]
• 出力: 0
• 説明: 配列の循環特性により、すべての 1 はすでにグループ化されています。
  • したがって、必要なスワップの最小数は 0 です。

制約:

• 1 5
• nums[i] は 0 または 1 です。

ヒント:

1. グループ化される 1 の数は固定されていることに注意してください。それは配列全体が持つ 1 の数です。
2. この数字を合計と呼びます。次に、合計サイズ (おそらくラップアラウンド) のすべてのサブ配列について、サブ配列をすべて 1 にするために必要なスワップの回数を確認する必要があります。
3. 必要なスワップの数は、サブ配列内の 0 の数です。
4. 配列の循環特性を排除するには、元の配列をそれ自体に追加します。次に、各部分配列の長さの合計を確認します。
5. 部分配列内の 0 の数を毎回数え直すのを避けるにはどうすればよいでしょうか?スライディング ウィンドウ手法が役に立ちます。

解決策:

この問題を解決するには、次の手順に従います:

1. 1 の合計数を数える: これは、グループ化する必要がある 1 の数になります。
2. 配列の拡張: 循環の性質を処理するには、配列をそれ自体に追加します。
3. スライディング ウィンドウ手法を使用する: 拡張配列にスライディング ウィンドウ手法を適用して、必要なスワップの最小数を見つけます。

このソリューションを PHP で実装してみましょう: 2134。すべて 1 をグループ化する最小スワップ II

<?php
// Example usage
$nums1 = [0,1,0,1,1,0,0];
$nums2 = [0,1,1,1,0,0,1,1,0];
$nums3 = [1,1,0,0,1];

echo minSwaps($nums1) . "\n"; // Output: 1
echo minSwaps($nums2) . "\n"; // Output: 2
echo minSwaps($nums3) . "\n"; // Output: 0

?>

説明：

1. 1 の合計数を数える: 元の配列内の 1 の合計数を計算します。
2. 配列の拡張: 循環の性質を処理するために、元の配列をそれ自体に連結します。
3. 初期ウィンドウ: 1 の合計数と同じサイズの初期ウィンドウ内の 0 の数を数えます。
4. スライディング ウィンドウ: 拡張配列上でウィンドウをスライドさせます。新しい位置ごとに、ウィンドウに出入りする要素に基づいて 0 のカウントを更新します。
5. 最小値の検索: 必要なスワップの最小数に対応する、発生する 0 の最小数を追跡します。

このソリューションは、円形配列を線形問題に変換することで効率的に処理し、スライディング ウィンドウ手法を使用して、1 の合計数に等しいサイズの各ウィンドウで 0 の連続カウントを維持します。

連絡先リンク

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

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

• LinkedIn
• GitHub

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