「労働者が自分の仕事をうまくやりたいなら、まず自分の道具を研ぎ澄まさなければなりません。」 - 孔子、「論語。陸霊公」
表紙 > プログラミング > Typescript コーディングクロニクル: Self を除く配列の積

Typescript コーディングクロニクル: Self を除く配列の積

2024 年 7 月 31 日に公開
ブラウズ:619

Typescript Coding Chronicles: Product of Array Except Self

問題文:

整数配列 nums を指定すると、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列の回答を返します。

nums の接頭辞または接尾辞の積は、32 ビット整数に収まることが保証されます。

除算演算を使用せずに、O(n) 時間で実行されるアルゴリズムを作成する必要があります。

例 1:

  • 入力: 数値 = [1,2,3,4]
  • 出力: [24,12,8,6]

例 2:

  • 入力: 数値 = [-1,1,0,-3,3]
  • 出力: [0,0,9,0,0]

制約:

  • 2
  • -30
  • nums の接頭辞または接尾辞の積は、32 ビット整数に収まることが保証されます。

フォローアップ:

O(1) 個の余分な空間複雑さの問題を解決できますか? (出力配列は、空間複雑性分析の追加スペースとしてカウントされません。)

最初の思考プロセス:

この問題を解決するには、除算演算を使用せずに、現在の要素を除くすべての要素の積を計算する必要があります。これは、配列

に対して 2 つのパスを使用することで実行できます。
  1. 各要素のプレフィックス積を計算します。
  2. 各要素の接尾辞の積を計算し、接頭辞の積を乗算します。

基本的な解決策:

2 つの配列を使用してプレフィックスとサフィックスの積を保存し、それらを乗算して最終結果を得ることができます。

コード:

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const prefixProducts = new Array(n).fill(1);
    const suffixProducts = new Array(n).fill(1);
    const result = new Array(n).fill(1);

    // Compute prefix products
    for (let i = 1; i = 0; i--) {
        suffixProducts[i] = suffixProducts[i   1] * nums[i   1];
    }

    // Compute the result by multiplying prefix and suffix products
    for (let i = 0; i 



時間計算量の分析:

  • 時間計算量: O(n)、n は配列の長さです。配列を 3 回繰り返します。
  • 空間複雑度: O(n)、プレフィックスとサフィックスの積を格納します。

制限事項:

基本的なソリューションはうまく機能しますが、プレフィックスとサフィックスの製品を保存するために余分なスペースを使用します。

最適化されたソリューション:

出力配列を使用して最初にプレフィックス製品を格納し、次にそれをインプレースで変更してサフィックス製品を含めることにより、O(1) 個の追加スペースを使用するようにソリューションを最適化できます。

コード:

function productExceptSelfOptimized(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(1);

    // Compute prefix products in the result array
    for (let i = 1; i = 0; i--) {
        result[i] = result[i] * suffixProduct;
        suffixProduct *= nums[i];
    }

    return result;
}

時間計算量の分析:

  • 時間計算量: O(n)、n は配列の長さです。配列を 2 回繰り返します。
  • 空間複雑度: O(1)。出力配列を使用して中間結果を保存し、追加の空間を使用していないためです。

基本的なソリューションの改善点:

  • 最適化されたソリューションは、中間結果の出力配列を使用することにより、空間の複雑さを O(1) に削減します。

エッジケースとテスト:

エッジケース:

  1. 配列にはゼロが含まれています。
  2. 配列には負の数値が含まれています。
  3. 配列の長さは最小値 (2) または最大値 (10^5) の制限です。

テストケース:

console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelf([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelf([0,0])); // [0,0]
console.log(productExceptSelf([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelf([1,2])); // [2, 1]

console.log(productExceptSelfOptimized([1,2,3,4])); // [24,12,8,6]
console.log(productExceptSelfOptimized([-1,1,0,-3,3])); // [0,0,9,0,0]
console.log(productExceptSelfOptimized([2,2,2,2])); // [8,8,8,8]
console.log(productExceptSelfOptimized([0,0])); // [0,0]
console.log(productExceptSelfOptimized([5])); // This should not be a valid input as the minimum length is 2
console.log(productExceptSelfOptimized([1,2])); // [2, 1]

一般的な問題解決戦略:

  1. 問題を理解する: 問題の説明を注意深く読み、要件と制約を理解します。
  2. キー操作の特定: プレフィックス積とサフィックス積の計算など、必要なキー操作を決定します。
  3. 読みやすさを最適化: 明確かつ簡潔なロジックを使用して、コードを理解しやすくします。
  4. 徹底的にテストする: エッジ ケースを含むさまざまなケースでソリューションをテストし、正確さを確認します。

同様の問題を特定する:

  1. プレフィックス合計配列:

    • 範囲クエリのプレフィックス合計を計算する必要がある問題。
    • 例: 範囲合計クエリ。
  2. インプレース アルゴリズム:

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

    • 特定の条件に基づいて配列を変更する必要がある問題。
    • 例: ゼロを配列の末尾に移動します。

結論:

  • 自分自身を除く配列の積を計算する問題は、追加スペースを使用した基本的なアプローチと最適化されたインプレース アプローチの両方を使用して効率的に解決できます。
  • 問題を理解し、管理可能な部分に分割することが重要です。
  • 明確なロジックを使用し、読みやすさを最適化することで、ソリューションは理解しやすくなります。
  • さまざまなエッジケースでのテストにより、堅牢性が保証されます。
  • 問題のパターンを認識すると、同様の解決策を他の課題に適用するのに役立ちます。

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

リリースステートメント この記事は次の場所に転載されています: https://dev.to/__zamora__/typescript-coding-chronicles-product-of-array-excel-self-3gg4?1 侵害がある場合は、[email protected] に連絡して削除してください。それ
最新のチュートリアル もっと>

免責事項: 提供されるすべてのリソースの一部はインターネットからのものです。お客様の著作権またはその他の権利および利益の侵害がある場合は、詳細な理由を説明し、著作権または権利および利益の証拠を提出して、電子メール [email protected] に送信してください。 できるだけ早く対応させていただきます。

Copyright© 2022 湘ICP备2022001581号-3