K サイズの部分配列の検出力を求める I-PHPチュートリアル-php.cn

K サイズの部分配列の検出力を求める I

Mary-Kate Olsen

リリース： 2024-11-25 00:58:27

オリジナル

608 人が閲覧しました

Find the Power of K-Size Subarrays I

3254。 K サイズの部分配列の検出力を求める I

難易度: 中

トピック: 配列、スライディングウィンドウ

長さ n の整数 nums と正の整数 k の配列が与えられます。

配列の電力は次のように定義されます:

すべての要素が連続であり、昇順順にソートされている場合の最大要素。
それ以外の場合は -1。

サイズ k の数値のすべての部分配列1の^累乗を見つける必要があります。

サイズ n - k 1 の整数配列結果を返します。ここで、results[i] は nums[i..(i k - 1)] の累乗です。

例 1:

入力: nums = [1,2,3,4,3,2,5]、k = 3
出力: [3,4,-1,-1,-1]
説明: サイズ 3 の num の部分配列が 5 つあります。
- [1, 2, 3] の最大要素は 3.
- [2, 3, 4] 最大要素 4.
- [3, 4, 3] の要素は連続していません。
- [4, 3, 2] の要素はソートされていません。
- [3, 2, 5] の要素は連続していません。

例 2:

入力: nums = [2,2,2,2,2]、k = 4
出力: [-1,-1]

例 3:

入力: nums = [3,2,3,2,3,2]、k = 2
出力: [-1,3,-1,3,-1]

制約:

ヒント:

ネストされたループと HashSet を使用したブルートフォースソリューションを使用できますか?

解決策:

タスクは次のように分類できます:

問題の内訳:

長さ n の配列 nums と正の整数 k が与えられます。サイズ k のすべての部分配列を考慮し、それらのべきを計算する必要があります。
部分配列の べき乗 は次のとおりです。
- すべての要素が連続であり、昇順順にソートされている場合の部分配列の最大要素。
- それ以外の場合は -1。
サイズ n - k 1 の配列を返す必要があります。ここで、各要素はそれぞれの部分配列のべき乗に対応します。

プラン：

スライディングウィンドウアプローチ: 配列上をスライドして、長さ k の各部分配列をチェックします。
部分配列がソートされているかどうかを確認します: 部分配列に連続した要素があり、昇順にソートされているかどうかを確認する必要があります。
最大値または -1 を返す: 部分配列が有効な場合は、最大要素を返します。それ以外の場合は、-1 を返します。

手順:

部分配列がソートされているかどうかを確認します:
スライディングウィンドウ:

このソリューションを PHP で実装してみましょう:

3254。 K サイズの部分配列の検出力を求める I

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

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>

ログイン後にコピー

説明：

Sliding Window: i = 0 から i = n - k までの for ループを使用して、サイズ k のすべての部分配列を考慮します。各部分配列について、array_slice() を使用して部分配列を抽出します。
並べ替えチェック: 各部分配列について、部分配列を反復処理し、連続する要素の各ペアの差が 1 であるかどうかを確認することにより、連続する要素で並べ替えられているかどうかを確認します。
結果: 部分配列が有効な場合、部分配列の最大値が結果に追加されます。それ以外の場合は、-1 を追加します。