Typescript コーディング クロニクル: トリプレット サブシーケンスの増加

問題の説明:

整数配列 nums が指定された場合、i

例 1:

• 入力: nums = [1,2,3,4,5]
• 出力: true
• 説明: i
の任意の 3 つ組。 j
例 2:
入力: nums = [5,4,3,2,1]
出力: false
説明: トリプレットは存在しません。
例 3:
入力: nums = [2,1,5,0,4,6]
出力: true
説明: nums[3] == 0 < であるため、トリプレット (3、4、5) は有効です。数値[4] == 4
制約:
1 -2^31
フォローアップ：
O(n) の時間計算量と O(1) の空間計算量で実行されるソリューションを実装できますか?
最初の思考プロセス:
この問題を効率的に解決するには、これまでに見つかった最小値と 2 番目に小さい値を追跡する必要があります。 2 番目に小さい値より大きい 3 番目の値が見つかった場合、増加する 3 つの値が見つかったことになります。
基本的な解決策 (総当たり):
総当たりの解決策には、考えられるすべてのトリプレットをチェックして、条件 i コード：

function increasingTripletBruteForce(nums: number[]): boolean {
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] < nums[j] && nums[j] < nums[k]) {
                    return true;
                }
            }
        }
    }
    return false;
}

• 時間計算量:
O(n^3)、n は配列の長さです。これは、考えられるすべてのトリプレットをチェックしているためです。
• スペースの複雑さ:
O(1)、余分なスペースを使用していないため。

function increasingTriplet(nums: number[]): boolean {
    let first = Infinity;
    let second = Infinity;

    for (let num of nums) {
        if (num <= first) {
            first = num; // smallest value
        } else if (num <= second) {
            second = num; // second smallest value
        } else {
            return true; // found a value greater than second smallest, thus an increasing triplet exists
        }
    }

    return false;
}

• 時間計算量:
O(n)、n は配列の長さです。配列を 1 回反復処理します。
• スペースの複雑さ:
O(1)。一定量の追加スペースのみを使用しているためです。

このソリューションは線形時間で実行され、一定の空間を使用するため、指定された制約に対して最適化されます。

配列は降順です。
配列には、昇順に正確に 3 つの要素が含まれています。
配列には、トリプレットが増加しない多数の要素があります。
配列には重複が含まれています。

console.log(increasingTripletBruteForce([1,2,3,4,5])); // true
console.log(increasingTripletBruteForce([5,4,3,2,1])); // false
console.log(increasingTripletBruteForce([2,1,5,0,4,6])); // true
console.log(increasingTripletBruteForce([1,1,1,1,1])); // false
console.log(increasingTripletBruteForce([1,2])); // false
console.log(increasingTripletBruteForce([1,2,3])); // true
console.log(increasingTripletBruteForce([1,5,0,4,1,3])); // true

console.log(increasingTriplet([1,2,3,4,5])); // true
console.log(increasingTriplet([5,4,3,2,1])); // false
console.log(increasingTriplet([2,1,5,0,4,6])); // true
console.log(increasingTriplet([1,1,1,1,1])); // false
console.log(increasingTriplet([1,2])); // false
console.log(increasingTriplet([1,2,3])); // true
console.log(increasingTriplet([1,5,0,4,1,3])); // true

1. 問題を理解する:
問題の説明を注意深く読み、要件と制約を理解します。
2. キー操作の特定:
最小値と 2 番目に小さい値の追跡など、必要なキー操作を決定します。
3. 効率の最適化:
効率的なアルゴリズムとデータ構造を使用して、時間と空間の複雑さを最小限に抑えます。
4. 徹底的にテストします:
エッジケースを含むさまざまなケースでソリューションをテストし、正確さを確認します。

1. サブ配列の問題:

   特定のプロパティを持つ部分配列を見つける必要がある問題。
   例: 最大合計部分配列の検索 (Kadane のアルゴリズム)。

2. ツーポイントテクニック:

   2 つのポインターを使用すると解の最適化に役立つ問題。
   例: ソートされた配列から重複を削除します。

3. インプレースアルゴリズム:

   • 限られた追加スペースで操作を適切な場所で実行する必要がある問題。
   • 例: 配列を右に k ステップ回転します。

結論：

• 増加する三重項部分列を見つける問題は、力ずくのアプローチと、線形時間と一定空間の複雑さを備えた最適化されたソリューションの両方を使用して効率的に解決できます。
• 問題を理解し、管理可能な部分に分割することが重要です。
• 効率的なアルゴリズムを使用することで、大規模な入力に対して最適なソリューションが得られます。
• さまざまなエッジケースでのテストにより、堅牢性が保証されます。
• 問題のパターンを認識すると、同様の解決策を他の課題に適用するのに役立ちます。

このような問題と戦略を実践することで、問題解決スキルを向上させ、さまざまなコーディングの課題に対する準備を整えることができます。

以上がTypescript コーディング クロニクル: トリプレット サブシーケンスの増加の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。