يدرس هذه المقالة بشكل أساسي المحتوى المتعلق بأكبر مجموعة فرعية في صفائف برمجة Java ، على النحو المفصل أدناه.
مقابلة شخص جيد يمكن أن يغير حياتك ؛ مقابلة كتاب جيد ، أليس كذلك؟
في الآونة الأخيرة ، كان لدي الكثير من الأفكار عندما قرأت السيد Zuo Chengyun " الحلول المثلى للخوارزمية وهيكل البيانات أسئلة مقابلة رمز المبرمج " . يوصى بأن يذهب المدونون الذين لديهم هوايات في هذا المجال.
إن خوارزمية أكبر مصفوفة من الصفيف القائم على المكدس الموضحة في الكتاب كلاسيكية للغاية ، لكن المدون لديه قدرة محدودة ولم يتمكن من فهم جوهر الخوارزمية تمامًا. ومع ذلك ، بناءً على هذه الفكرة ، توصل المدون إلى خوارزمية بسيطة للتعامل مع هذا النوع من المشكلات ، وهو ملخص على النحو التالي.
فكرة أساسية
دعونا نلقي نظرة على صورة أولاً ، ويمكننا أن نفهمها تقريبًا.
كما هو موضح في الشكل ، فإن كل جولة هي عملية ، ونوهرنا هو العملية الداخلية لكل جولة.
احسب الحد الأقصى لطول كل طبقة بشكل مستمر وبدون انقطاع
بمعنى آخر ، نحن أهم صفيف لحساب الجولات السفلية إلى الأعلى ، وبعد ذلك يمكننا حساب مساحة الكفاءة الفرعية المستمرة التي يمكن الحصول عليها في هذه الجولة لكل جولة. ثم تحتاج فقط إلى مقارنة أكبر البيانات لكل جولة ، والعودة للعثور على مساحة أكبر مجموعة فرعية مستمرة للمصفوفة.
شفرة
حسنًا ، مع وضع الأفكار الأساسية أعلاه ، يمكننا البدء في كتابة التعليمات البرمجية. (على الرغم من أنني لا أعتقد أنني قلت ذلك بوضوح شديد ، أرجو أن تسامحني).
package stack_and_queue ؛/*** auuthor guo pu <br>* احسب مساحة أكبر منطقة مستطيل مستمر تعتمد على الصفيف*/الفئة العامة maxRectangle {public static void main (string [] MaxRectanglearea (arr) ؛ system.out.println ("مساحة أكبر منطقة مستطيل مستمر في المصفوفة هي:" + maxRectangle) ؛}/*** @param arr* return الحد الأقصى لمنطقة المستطيل المستمر في array*/integer integer maxrectanglearea (inte). int [arr.length] ؛ // احسب الصفيف عن طريق اجتياز الطول المستمر من الأسفل إلى الأعلى لأعلى (int i = 1 ؛ i <= arr.length ؛ i ++) {// يتم تطبيق القيمة المؤقتة للطول المستمر المتراكم في الجولة الحالية من المعبد الأول = 0 ؛ من بين المُخطط التراكمي للطبقة الأولى سوف يتسبب في فقدان الجزء السابق من البيانات (int j = 1 ؛ j <= arr.length ؛ j ++) {if (arr [j - 1]> = i) {templen += 1 ؛ templen_max = templen ؛} else {templen = 0 ؛}}}} I + "الحد الأقصى المستمر وغير المنقطعة للطبقة هو:" + templen_max) ؛} // ابحث عن الرقم ذي القيمة العددية الأكبر في صفيف مجموعة النتائج ، أي ، مساحة أكبر مجال مستطيل في منطقة الاستمرارية التي تم العثور عليها maxarea = 0 ؛ Maxarea: النتيجة [i] ؛} // إرجاع مساحة حقل المستطيل المستمر الأقصى الذي تم الحصول عليه عن طريق إرجاع maxarea ؛}}التعليقات في الكود شاملة نسبيًا ، لذلك لن أخوض في الكثير من التفاصيل.
امتحان
فيما يلي اختبار الصفيف. أولاً ، دعنا نختبرها مع الصفيف الموضح في الصورة في بداية هذه المقالة.
عدد صحيح [] arr = {2،1،3،5،7،6،4} ・・・・مساحة أكبر منطقة مستطيلة مستمرة في الصفيف هي: 16
ثم نقوم بتعديل قيم العناصر في الصفيف للاختبار الإضافي لمعرفة ما إذا كانت النتائج صحيحة.
عدد صحيح [] arr = {2،1،3،1،7،6،4} ・・・・مساحة أكبر منطقة مستطيلة مستمرة في الصفيف هي: 12
بعد اختبار المدون نفسه ، تعمل الخوارزمية بشكل طبيعي. سائدا
جزء التحسين
عند الحديث عن جزء التحسين ، فإن أول ما يمكننا رؤيته هو العثور على أقصى قيمة في مجموعة مجموعة النتائج في الخطوة الأخيرة.
في الواقع ، يمكننا في الواقع تطبيق متغير آخر لتسجيل مساحة أكبر مجموعة فرعية من الجولة حتى الآن. ومع ذلك ، فإن هذا التحسين لا يلعب دورًا كبيرًا ، ولا يوجد أي تحسن كبير في التعقيد الزمني.
نقطة أخرى ، أعتقد أن نقطة الدخول الأفضل هي إضافة حكم عند إجراء حسابات لكل جولة لتقرير ما إذا كان سيتم ركوبها لأسفل قبل الجولة الحالية. إذا تذبذب العناصر الموجودة في الصفيف بشكل كبير ، فإن مستوى التحسين لا يزال جيدًا جدًا.
لخص
هذه الخوارزمية الصغيرة أكثر روعة ، والشيء الوحيد الأكثر معيبة هو أن تعقيد الوقت أكثر كثافة قليلاً. إذا كان القراء يبحثون عن خوارزمية ذات تعقيد منخفض نسبيًا ، فيرجى أخذ التفاف.
إنه أمر جيد إذا كنت تريد فقط العثور على نتيجة. على الأقل هو أكثر كفاءة من الطريقة العنيفة للحوسبة.
ما ورد أعلاه هو كل محتوى هذه المقالة حول الحل البسيط إلى الحد الأقصى لتكريم الفرعية في صفائف برمجة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها. شكرا لك يا أصدقائك لدعمكم لهذا الموقع!