אורך מרבי של תת-מערך חוזר


רמת קושי בינוני
נשאל לעתים קרובות אכן קראט רובלוקס
מערך חיפוש בינארי תכנות דינמי חבטות

בבעיה "אורך מרבי של מערך משנה חוזר" נתנו לשני מערכים מערך 1 ומערך 2, המשימה שלך היא למצוא את האורך המקסימלי של מערך המשנה שמופיע בשני מערכים.

דוגמה

קלט:

[1,2,3,2,1]
[3,2,1,4,7]

פלט:

3

הסבר:

מכיוון שהאורך המרבי של תת-מערך הוא 3 והמערך המשותף הוא [3,2,1]

אורך מרבי של תת-מערך חוזר

אַלגוֹרִיתְם

  1. הגדר את הפלט ל -0.
  2. הכריזו על מערך מספרים שלם משתנה שאורכו 1 יותר מאורכו של מערך הקלט בפועל.
  3. החל מ- אינדקס אחרון למערך בדוק אם מערך 1 [i] שווה למערך 2 [j], אם נכון אז val [i] [j] = val [i + 1] [j + 1] +1.
  4. בדוק אם הפלט נמוך מ- val [i] [j] ואז בצע = val [i] [j].
  5. בוטל על כל המערך ובדוק את התנאים אנו מקבלים את התפוקה המרבית.
  6. תפוקת החזר.

הסבר

כדי להשיג את התפוקה שלנו, עלינו לבצע מסלולים פשוטים. לשם כך אנו הולכים לאתחל את הפלט ל 0. ואז נכריז על ה- 2-D מַטרִיצָה באורך אחד יותר מאורך מערך 1 ומערך 2.

אנו הולכים לחצות את שני המערכים מהאינדקס האחרון של המערך. אז נבדוק חלק מהתנאים ונאחסן את התוצאה בפלט.

אז בואו ניקח דוגמא ונמשיך הלאה.

דוגמה

נניח שיש מערך כמו:

int array1 [] = {1,2,3,2,1};

int array2 [] = {3,2,1,4,7};

פלט = 0;

  • i = 4, j = 4;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

פלט = 0;

  • i = 4, j = 3;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

פלט = 0;

  • i = 4, j = 2;

אם array1 [i] == array2 [j] מחזיר true ו- val [i] [j] = val [i + 1] [j + 1] +1

then val[4][2]=val[5][3]+1=1 then val[i][j]=1.

ואז בדוק אם פלט <val [i] [j] מחזיר נכון ועשה פלט = 1.

פלט = 1;

  • i = 4, j = 1;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 4, j = 0;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 3, j = 4;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 3, j = 3;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 3, j = 2;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 3, j = 1;

אם array1 [i] == array2 [j] מחזיר true ו- val [i] [j] = val [i + 1] [j + 1] +1

ואז val [3] [1] = val [4] [2] + 1 = 2 ואז val [3] [1] = 2.

ואז בדוק אם פלט <val [i] [j] מחזיר true ועשה output = val [i] [j].

פלט = 2;

  • i = 3, j = 0;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 2, j = 4;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 2, j = 3;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 2, j = 2;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 2, j = 1;

אם מערך 1 [i] == מערך 2 [j] מחזיר שקר ולא מתכוון לעשות דבר.

  • i = 2, j = 0;

אם array1 [i] == array2 [j] מחזיר true ו- val [i] [j] = val [i + 1] [j + 1] +1

ואז val [2] [0] = val [3] [1] + 1 = 2 + 1 ואז val [2] [0] = 3.

ואז בדוק אם פלט <val [i] [j] מחזיר true ועשה output = val [2] [0].

פלט = 3;

וזה יהיה האורך המקסימלי של המערך החוזר ונשנה שהוא 3 גם אחרי שנמצא את האלמנטים שווים במעבר אבל זה לא יעשה עדכון בפלט, כי זה לא יהיה מערך המשנה

נניח ב- i = 1, j = 1 אנו נמצא את האלמנט הבא הבא כך שהוא יעשה val [1] [1] = val [2] [2] +1;

ואם אנחנו בודקים פלט <val [1] [1] אז בכל פעם זה מחזיר שקר ולא יעשה כלום.

אז הנה, התפוקה היא 3.

יישום

תוכנית C ++ לאורך מרבי של תת-מערך חוזר

#include <iostream>
using namespace std;

int lengthOfRepeatedArray(int array1[], int array2[])
{
    int output = 0;
    int val[6][6]= {0};

    for (int i = 4; i >= 0; --i)
    {
        for (int j = 4; j >= 0; --j)
        {
            if (array1[i] == array2[j])
            {
                val[i][j] = val[i+1][j+1] + 1;
                if(output < val[i][j])
                {
                    output = val[i][j];
                }
            }
        }
    }
    return output;
}
int main()
{
    int a[]= {1,2,3,2,1};
    int b[]= {3,2,1,4,7};

    cout<<lengthOfRepeatedArray(a,b);
    return 0;
}
3

תוכנית Java למשך אורך מרבי של תת-מערך חוזר

class repeatedArrayLength
{
    public static int lengthOfRepeatedArray(int[] array1, int[] array2)
    {
        int output = 0;
        int val[][] = new int[array1.length + 1][array2.length + 1];
        for (int i = array1.length - 1; i >= 0; --i)
        {
            for (int j = array2.length - 1; j >= 0; --j)
            {
                if (array1[i] == array2[j])
                {
                    val[i][j] = val[i+1][j+1] + 1;
                    if(output < val[i][j])
                        output = val[i][j];
                }
            }
        }
        return output;
    }
    public static void main(String []args)
    {
        int a[]= {1,2,3,2,1};
        int b[]= {3,2,1,4,7};
        System.out.println(lengthOfRepeatedArray(a,b));
    }
}
3

ניתוח מורכבות לאורך אורך מרבי של תת-מערך חוזר

מורכבות זמן

O (a × b) איפה א הוא גודל המערך הראשון ו- "ב" הוא גודל המערך השני.

מורכבות בחלל

O (a × b) איפה א הוא גודל המערך הראשון ו- "ב" הוא גודל המערך השני.

התייחסות