في مقابلات الخوارزمية ، يرغب المقابلات دائمًا في إنشاء مقالات حول القوائم المرتبطة ، والفرز ، والأشجار الثنائية ، والبحث الثنائي ، ويمكن لمعظم الناس متابعة الكتب المهنية لحفظها. لا يرغب القائم بإجراء المقابلة في توظيف مبرمج بمهارات ذاكرة جيدة ولكن لا يمكنه التعلم وتطبيقه. لذلك ، من المهم للغاية تعلم نموذج وتحليل المشكلات رياضيا واستخدام خوارزميات أو هياكل بيانات معقولة لحل المشكلات.
سؤال المقابلة: طباعة الحد الأدنى لعدد المصفوفة الدوارة
العنوان: انقل العناصر العديدة الأولى من صفيف إلى نهاية الصفيف ، والتي نسميها دوران الصفيف. أدخل دوران صفيف مرتبة بشكل متزايد وإخراج عنصر الحد الأدنى من صفيف الدوران. على سبيل المثال ، Array {3 ، 4 ، 5 ، 1 ، 2} هو دوران الصفيف {1 ، 2 ، 3 ، 4 ، 5} ، والقيمة الدنيا للمصفوفة هي 1.
لتحقيق هذا المطلب ، نحتاج فقط إلى اجتياز الصفيف ، والعثور على أصغر قيمة والخروج من الحلقة مباشرة. تطبيق الكود كما يلي:
test class public test08 {public static int getTheMin (int nums []) {if (nums == null || nums.length == 0) {رمي new runTimeException ("خطأ الإدخال!") ؛ } int result = nums [0] ؛ لـ (int i = 0 ؛ i <nums.length - 1 ؛ i ++) {if (nums [i + 1] <nums [i]) {result = nums [i + 1] ؛ استراحة؛ }} نتيجة الإرجاع ؛ } main static void main (string [] args) {// الإدخال النموذجي ، دوران من صفيف تصاعدي رتابة int [] array1 = {3 ، 4 ، 5 ، 1 ، 2} ؛ System.out.println (getThemin (Array1)) ؛ // هناك أرقام مكررة ، وأصغر عدد هو أصغر عدد int [] Array2 = {3 ، 4 ، 5 ، 1 ، 1 ، 2} ؛ System.out.println (getTheMin (Array2)) ؛ // هناك أرقام مكررة ، لكن الأرقام المكررة ليست الأرقام الأولى والأخيرة int [] Array3 = {3 ، 4 ، 5 ، 1 ، 2 ، 2} ؛ System.out.println (getThemin (Array3)) ؛ // هناك أرقام مكررة ، وتصدر أن الأرقام المكررة هي الأرقام الأولى والأخيرة int [] Array4 = {1 ، 0 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array4)) ؛ // صفيف تصاعدي رتيب ، تدوير 0 عناصر ، أي صفيف تصاعدي رتيب نفسه int [] array5 = {1 ، 2 ، 3 ، 4 ، 5} ؛ System.out.println (getThemin (Array5)) ؛ // هناك رقم واحد فقط في Array int [] Array6 = {2} ؛ System.out.println (getThemin (Array6)) ؛ // الأرقام الموجودة في الصفيف هي نفس int [] Array7 = {1 ، 1 ، 1 ، 1 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array7)) ؛ }}لا حرج في نتائج الطباعة. ومع ذلك ، من الواضح أن هذه الطريقة ليست الأفضل. دعونا نرى ما إذا كانت هناك طريقة لإيجاد طريقة أفضل للتعامل معها.
منظم ، ما زلت بحاجة للبحث؟
عندما نجد هاتين الكلمة الرئيسية ، سنفكر حتماً في طريقة البحث الثنائية لدينا ، لكن العديد من الأصدقاء سيطلبون بالتأكيد أن صفيفنا لم يعد صفيفًا تم طلبه حقًا بعد تدويره ، ولكنه يشبه مزيج من المصفوفتين المتزايدة. يمكننا أن نفكر هكذا.
يمكننا تعيين اثنين من المشتركين منخفضة وعالية ، وضبط Mid = (Low + High)/2 ، ويمكننا أن نجد بشكل طبيعي صفيف العنصر [Mid] في منتصف الصفيف. إذا كان العنصر الأوسط في الصفيف الإضافي في المقدمة ، فيجب أن يكون أكبر من أو يساوي العنصر المقابل للترتيب المنخفض. في هذا الوقت ، يجب أن يكون أصغر عنصر في الصفيف وراء العنصر. يمكننا توجيه المنخفض المنخفض إلى العنصر الوسيط ، والذي يمكن أن يضيق نطاق عمليات البحث.
وبالمثل ، إذا كان العنصر الوسيط موجودًا في المكسر الفرعي التزايدي اللاحق ، فيجب أن يكون أقل من العنصر المقابل أو يساوي العنصر المقابل للتراكب العالي. في هذا الوقت ، يجب أن يكون أصغر عنصر في الصفيف أمام العنصر المتوسط. يمكننا تحديث العدد العالي إلى الوسيط المتوسط ، والذي يمكنه أيضًا تضييق نطاق عمليات البحث. لا تزال العناصر المقابلة للانتشار العالي بعد الانتقال في المساعد الفرعي التزايدي اللاحق.
سواء أكان تحديثًا منخفضًا أو مرتفعًا ، سيتم تقليل نطاق البحث الخاص بنا إلى نصف الأصل. بعد ذلك ، سوف نستخدم الترتيب المحدث لتكرار جولة جديدة من عمليات البحث. حتى آخر اثنين من الاشتراكين متاخمين ، أي حالة نهاية الحلقة لدينا.
لقد قلت الكثير ، ويبدو أنني كنت في حالة من الفوضى. قد نستخدم أيضًا المدخلات في السؤال لمحاكاة الخوارزمية والتحقق منها.
دعونا نلقي نظرة على كيفية تنفيذ هذه الفكرة في جافا باستخدام الكود:
test class public test08 {public static int getTheMin (int nums []) {if (nums == null || nums.length == 0) {رمي new runTimeException ("خطأ الإدخال!") ؛ } // إذا كان هناك عنصر واحد فقط ، فأعود مباشرة إذا (nums.length == 1) إرجاع NUMS [0] ؛ int النتيجة = nums [0] ؛ int low = 0 ، high = nums.length - 1 ؛ int منتصف // تأكد من أن القيمة المقابلة للترجمة المنخفضة هي في المساعد الفرعي للزيادة على اليسار ، والقيمة المقابلة للثانوية هي في المكسر الفرعي زيادة على اليمين بينما (nums [low]> = nums [high]) {// تأكد من نهاية حالة الحلقة إذا (منخفضة - منخفض = 1) } // خذ الوضع الأوسط Mid = (Low + High) / 2 ؛ // يشير إلى أن العنصر الأوسط يتم زيادة على اليسار إذا (nums [mid]> = nums [low]) {low = mid ؛ } آخر {high = mid ؛ }} نتيجة الإرجاع ؛ } main static void main (string [] args) {// الإدخال النموذجي ، دوران من صفيف تصاعدي رتابة int [] array1 = {3 ، 4 ، 5 ، 1 ، 2} ؛ System.out.println (getThemin (Array1)) ؛ // هناك أرقام مكررة وأصغر عدد يكرر فقط الأرقام هو int [] Array2 = {3 ، 4 ، 5 ، 1 ، 1 ، 2} ؛ System.out.println (getTheMin (Array2)) ؛ // هناك أرقام مكررة ، لكن الأرقام المكررة ليست الأرقام الأولى والأخيرة int [] Array3 = {3 ، 4 ، 5 ، 1 ، 2 ، 2} ؛ System.out.println (getThemin (Array3)) ؛ // هناك أرقام مكررة ، والأرقام المكررة هي بالضبط الأرقام الأولى والأخيرة int [] Array4 = {1 ، 0 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array4)) ؛ // صفيف تصاعدي رتيب ، تدوير 0 عناصر ، أي صفيف تصاعدي رتيب نفسه int [] array5 = {1 ، 2 ، 3 ، 4 ، 5} ؛ System.out.println (getThemin (Array5)) ؛ // هناك رقم واحد فقط في Array int [] Array6 = {2} ؛ System.out.println (getThemin (Array6)) ؛ // الأرقام الموجودة في الصفيف هي نفس int [] Array7 = {1 ، 1 ، 1 ، 1 ، 1 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array7)) ؛ // Special لا أعرف كيفية نقل int [] array8 = {1 ، 0 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array8)) ؛ }}ذكرنا في وقت سابق أنه في صفيف دوار ، نظرًا لأن عدة أرقام في الصفيف المرتبة بشكل تدريجي يتم نقلها خلف الصفيف ، فإن الرقم الأول دائمًا أكبر من أو يساوي العدد الأخير ، وهناك حالة خاصة أخرى يتم نقل 0 عناصر ، أي أن الصفيف نفسه هو أيضًا صفيفها الدوار الخاص به. يتم طلب هذا الموقف نفسه ، لذلك نحتاج فقط إلى إعادة العنصر الأول ، وهذا هو السبب في أني أخصب النتيجة إلى NUMS [0] أولاً.
هل الرمز أعلاه مثالي؟ لم نلبي متطلباتنا من خلال حالات الاختبار. دعنا نلقي نظرة على إدخال Array8 بالتفصيل. دعنا أولاً نحلل تشغيل الكمبيوتر:
ولكن يمكننا أن نرى في لمحة أن الحد الأدنى لقيمتنا ليست 1 ، ولكن 0 ، لذلك عندما يكون الصفيف [منخفض] ، صفيف [منتصف] ، صفيف [مرتفع] ، لا يعرف برنامجنا كيفية التحرك. وفقًا لطريقة الحركة الحالية ، يتم زيادة الصفيف [Mid] على اليسار افتراضيًا. من الواضح أن هذا غير مسؤول.
دعنا نصحح الرمز:
test class public test08 {public static int getTheMin (int nums []) {if (nums == null || nums.length == 0) {رمي new runTimeException ("خطأ الإدخال!") ؛ } // إذا كان هناك عنصر واحد فقط ، فأعود مباشرة إذا (nums.length == 1) إرجاع NUMS [0] ؛ int النتيجة = nums [0] ؛ int low = 0 ، high = nums.length - 1 ؛ int mid = low ؛ // تأكد من أن القيمة المقابلة للترجمة المنخفضة هي في المساعد الفرعي للزيادة على اليسار ، والقيمة المقابلة للثانوية هي في المكسر الفرعي زيادة على اليمين بينما (nums [low]> = nums [high]) {// تأكد من نهاية حالة الحلقة إذا (منخفضة - منخفض = 1) } // خذ الوضع الأوسط Mid = (Low + High) / 2 ؛ // في الحالات الخاصة التي تكون فيها القيم الثلاث متساوية ، تحتاج إلى العثور على أصغر قيمة من البداية إلى النهاية إذا (nums [mid] == nums [low] && nums [mid] == nums [high]) {return midinorder (nums ، low ، high) ؛ } // يشير إلى أن العنصر الأوسط يتم زيادة على اليسار إذا (nums [mid]> = nums [low]) {low = mid ؛ } آخر {high = mid ؛ }} نتيجة الإرجاع ؛ } / *** ابحث عن القيمة الدنيا في المصفوفة** param nums array* param start start start start* param end end position* @return the أصغر رقم موجود* / public static int midinorder (int [] nums ، int end) {int result = nums [start] ؛ لـ (int i = start+1 ؛ i <= end ؛ i ++) {if (result> nums [i]) result = nums [i] ؛ } نتيجة الإرجاع ؛ } main static void main (string [] args) {// الإدخال النموذجي ، دوران من صفيف تصاعدي رتابة int [] array1 = {3 ، 4 ، 5 ، 1 ، 2} ؛ System.out.println (getThemin (Array1)) ؛ // هناك أرقام مكررة وأصغر عدد يحدث فقط أن يكون الرقم الأكثر شيوعًا [] Array2 = {3 ، 4 ، 5 ، 1 ، 1 ، 2} ؛ System.out.println (getTheMin (Array2)) ؛ // هناك أرقام مكررة ، لكن الأرقام المكررة ليست الأرقام الأولى والأخيرة int [] Array3 = {3 ، 4 ، 5 ، 1 ، 2 ، 2} ؛ System.out.println (getThemin (Array3)) ؛ // هناك أرقام مكررة ، والأرقام المكررة هي بالضبط الأرقام الأولى والأخيرة int [] Array4 = {1 ، 0 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array4)) ؛ // صفيف تصاعدي رتيب ، تدوير 0 عناصر ، أي صفيف تصاعدي رتيب نفسه int [] array5 = {1 ، 2 ، 3 ، 4 ، 5} ؛ System.out.println (getThemin (Array5)) ؛ // هناك رقم واحد فقط في Array int [] Array6 = {2} ؛ System.out.println (getThemin (Array6)) ؛ // جميع الأرقام في الصفيف هي نفس int [] Array7 = {1 ، 1 ، 1 ، 1 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array7)) ؛ // Special لا أعرف كيفية نقل int [] array8 = {1 ، 0 ، 1 ، 1 ، 1} ؛ System.out.println (getThemin (Array8)) ؛ }}ثم نضعه في حالات اختبار كاملة ويمر الاختبار.
لخص
في الواقع ، يحتوي هذا السؤال على العديد من النقاط التي يجب فحصها ، ولكن في الواقع هو فحص التطبيق المرن للبحث الثنائي. يجب على العديد من الأصدقاء اتباع عمليات البحث الثنائية بشكل منظم دون تعلم فكرة البحث الثنائي ، مما سيؤدي إلى التفكير فقط في الحد الأدنى للبحث الدائري.
أدلى العديد من الأصدقاء ببيان خلال المقابلة بأن النظام البيئي الأصلي Android الأصلي يتغلف بشكل أساسي من الخوارزميات المشتركة واحتجوا على هذه الخوارزميات غير الفعالة في المقابلة. هذا في الواقع غبي جدا. نحن لا نسعى إلى تنفيذ خوارزميات Rote ، لكننا نسعى لتعلم الأفكار الذكية فيه. فقط من خلال تحسين قدرة تفكير الفرد باستمرار يمكن للمرء أن يساعد المرء في الحصول على تطوير مهني أفضل.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.