عرض المشكلة:

نظرًا لمصفوفة أعداد صحيحة، قم بإرجاع إجابة مصفوفة بحيث تكون الإجابة[i] مساوية لمنتج جميع عناصر الأعداد باستثناء الأعداد[i].

يضمن المنتج الذي يحتوي على أي بادئة أو لاحقة من الأرقام أن يتناسب مع عدد صحيح 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
• يضمن المنتج الذي يحتوي على أي بادئة أو لاحقة من الأرقام أن يتناسب مع عدد صحيح 32 بت.

متابعة:

هل يمكنك حل المشكلة في تعقيد المساحة الإضافية O(1)؟ (لا يتم احتساب مصفوفة الإخراج كمساحة إضافية لتحليل تعقيد المساحة.)

عملية التفكير الأولية:

لحل هذه المشكلة، نحتاج إلى حساب حاصل ضرب جميع العناصر باستثناء العنصر الحالي دون استخدام عملية القسمة. يمكن القيام بذلك باستخدام تمريرتين على المصفوفة:

1. حساب منتجات البادئة لكل عنصر.
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 هو طول المصفوفة. نحن نكرر خلال المصفوفة ثلاث مرات.
• تعقيد المساحة: 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 هو طول المصفوفة. نحن نكرر خلال المصفوفة مرتين.
• تعقيد المساحة: 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. معالجة المصفوفة:

   • المشاكل التي تحتاج فيها إلى تعديل المصفوفات بناءً على شروط محددة.
   • مثال: نقل الأصفار إلى نهاية المصفوفة.

خاتمة:

• يمكن حل مشكلة حساب منتج مصفوفة باستثناء الذات بكفاءة باستخدام كل من النهج الأساسي مع مساحة إضافية والنهج الموضعي الأمثل.
• إن فهم المشكلة وتقسيمها إلى أجزاء يمكن التحكم فيها أمر بالغ الأهمية.
• يضمن استخدام المنطق الواضح وتحسين سهولة القراءة سهولة متابعة الحل.
• يضمن الاختبار باستخدام حالات الحافة المختلفة المتانة.
• يمكن أن يساعد التعرف على أنماط المشكلات في تطبيق حلول مماثلة لتحديات أخرى.

من خلال ممارسة مثل هذه المشكلات والاستراتيجيات، يمكنك تحسين مهاراتك في حل المشكلات والاستعداد بشكل أفضل لمواجهة تحديات البرمجة المختلفة.