最大ビット単位の AND を使用した最長のサブ配列

2419。最大ビット単位 AND

を持つ最長のサブ配列

難易度: 中

トピック: 配列、ビット操作、頭の体操

サイズ n の整数配列 nums が与えられます。

可能な最大のビット単位のANDを持つnumsからの空でない部分配列を考えます。

• 言い換えると、k を nums の任意の部分配列のビット単位の AND の最大値とします。次に、k に等しいビット単位の AND を持つ部分配列のみを考慮する必要があります。

そのようなサブ配列の最長の長さを返します。

配列のビット単位の AND は、配列内のすべての数値のビット単位の AND です。

サブ配列は、配列内の要素の連続したシーケンスです。

例 1:

• 入力: 数値 = [1,2,3,3,2,2]
• 出力: 2
• 説明:
  • 部分配列のビットごとの AND の最大値は 3 です。
  • その値を持つ最長の部分配列は [3,3] であるため、2 を返します。

例 2:

• 入力: 数値 = [1,2,3,4]
• 出力: 1
• 説明:
  • 部分配列のビットごとの AND の最大値は 4 です。
  • その値を持つ最長の部分配列は [4] であるため、1 を返します。

制約:

• 1 1
• 1 6

ヒント:

1. 2 つの異なる数値のビット単位の AND は、常にこれら 2 つの数値の最大値よりも厳密に小さいことに注意してください。
2. このことから、選択すべきサブ配列の性質について何がわかりますか?

解決策:

まず問題を段階的に分析してみましょう:

主要な洞察:

1. ビットごとの AND プロパティ:

   • 2 つの数値のビット単位の AND は、通常、両方の数値以下になります。
   • したがって、配列内で最大値が見つかった場合、この最大ビット単位 AND 値を達成する部分配列は、この最大値の繰り返しで構成されなければなりません。

2. 目的:

   • 配列内の最大値を見つけます。
   • その最大値の最も長く連続するサブ配列を見つけます。サブ配列内に他の数値があると、全体のビット単位の AND 結果が減少するためです。

プラン：

1. 配列を走査し、最大値を決定します。
2. 配列を再度スキャンして、すべての要素がこの最大値に等しい、最も長く連続する部分配列を見つけます。

例：

入力配列 [1,2,3,3,2,2] の最大値は 3 です。3 だけを持つ最長の連続部分配列は [3,3] で、長さは 2 です。

このソリューションを PHP で実装してみましょう: 2419。最大ビット単位 AND
を持つ最長のサブ配列

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSubarray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [1, 2, 3, 3, 2, 2];
$nums2 = [1, 2, 3, 4];

echo "Output for [1, 2, 3, 3, 2, 2]: " . longestSubarray($nums1) . "\n"; // Output: 2
echo "Output for [1, 2, 3, 4]: " . longestSubarray($nums2) . "\n";       // Output: 1
?>

説明：

1. ステップ 1: まず、PHP の組み込み max() 関数を使用して、配列内の最大値を見つけます。
2. ステップ 2: 2 つの変数、最長の部分配列の長さを保存する $maxLength と、最大値の現在の連続する部分配列の長さを追跡する $currentLength を初期化します。
3. ステップ 3: 配列を反復処理します。
   • 現在の数値が最大値と等しい場合、現在の部分配列の長さを増分します。
   • 現在の数値が最大値と等しくない場合は、現在の部分配列がこれまでで最長かどうかを確認し、長さをリセットします。
4. 最終ステップ: ループの後、最長の部分配列が配列の最後にある場合でも、それが考慮されることを確認します。
5. 最後に、最大値のみを含む最長の部分配列の長さを返します。

時間計算量:

• 最大値を見つけるには (O(n)) がかかります。
• 配列を走査して最長の部分配列を見つけるには (O(n)) かかります。
• 全体の時間計算量: (O(n))、ここで (n) は配列の長さです。

テストケース:

予想どおり、入力 [1, 2, 3, 3, 2, 2] の場合、出力は 2 になり、[1, 2, 3, 4] の場合、出力は 1 になります。

このソリューションは制約を処理し、問題を効率的に解決します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が最大ビット単位の AND を使用した最長のサブ配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。