மீண்டும் மீண்டும் சுபாரேயின் அதிகபட்ச நீளம்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது உண்மையில் காரத் Roblox
அணி பைனரி தேடல் டைனமிக் புரோகிராமிங் ஹேஷிங்

"மீண்டும் மீண்டும் செய்யப்படும் சுபாரேயின் அதிகபட்ச நீளம்" என்ற சிக்கலில், வரிசை 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. வெளியீடு வால் [i] [j] ஐ விட குறைவாக இருக்கிறதா என்று சரிபார்க்கவும், பின்னர் வெளியீடு = வால் [i] [j] செய்யுங்கள்.
  5. முழு வரிசையையும் மறுபரிசீலனை செய்து, அதிகபட்ச வெளியீட்டைப் பெறும் நிலைமைகளைச் சரிபார்க்கவும்.
  6. வெளியீடு திரும்பவும்.

விளக்கம்

எங்கள் வெளியீட்டைப் பெற, சில எளிய பயணங்களை நாங்கள் செய்ய வேண்டும். இதற்காக, வெளியீட்டை 0 க்கு துவக்கப் போகிறோம். பின்னர் 2-D ஐ அறிவிப்போம் அணி வரிசை 1 மற்றும் வரிசை 2 இன் நீளத்தை விட நீளம் ஒன்று.

வரிசையின் கடைசி குறியீட்டிலிருந்து இரண்டு வரிசைகளையும் நாம் பயணிக்கப் போகிறோம். எனவே சில நிபந்தனைகளை சரிபார்த்து முடிவை வெளியீட்டில் சேமிப்போம்.

எனவே ஒரு எடுத்துக்காட்டு எடுத்து மேலும் தொடரலாம்.

உதாரணமாக

இவ்வாறு ஒரு வரிசை உள்ளது என்று வைத்துக்கொள்வோம்:

int வரிசை 1 [] = {1,2,3,2,1};

int வரிசை 2 [] = {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;

வரிசை 1 [i] == வரிசை 2 [j] உண்மை மற்றும் மதிப்பு [i] [j] = வால் [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;

வரிசை 1 [i] == வரிசை 2 [j] உண்மை மற்றும் மதிப்பு [i] [j] = வால் [i + 1] [j + 1] +1

பின்னர் val [3] [1] = val [4] [2] + 1 = 2 பின்னர் val [3] [1] = 2.

வெளியீடு <val [i] [j] உண்மைக்கு திரும்பி, வெளியீடு = 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;

வரிசை 1 [i] == வரிசை 2 [j] உண்மை மற்றும் மதிப்பு [i] [j] = வால் [i + 1] [j + 1] +1

பின்னர் val [2] [0] = val [3] [1] + 1 = 2 + 1 பின்னர் val [2] [0] = 3.

வெளியீடு <val [i] [j] உண்மைக்கு திரும்பி, வெளியீடு = val [2] [0] என்பதை சரிபார்க்கவும்.

வெளியீடு = 3;

இது மீண்டும் மீண்டும் வரும் வரிசையின் அதிகபட்ச நீளமாக இருக்கும், இது 3 கூறுகளை நாம் பயணிப்பதில் சமமாகக் கண்டறிந்த பிறகும், ஆனால் அது வெளியீட்டில் புதுப்பிப்பைச் செய்யாது, ஏனென்றால் அது சப்ரேயாக இருக்காது

i = 1, j = 1 இல் சொல்லலாம், அடுத்த ஒத்த உறுப்பைக் கண்டுபிடிப்போம், எனவே அது வால் [1] [1] = வால் [2] [2] +1;

வெளியீடு <வால் [1] [1] ஐச் சரிபார்த்தால், ஒவ்வொரு முறையும் அது தவறானது, எதையும் செய்யாது.

எனவே இங்கே, வெளியீடு 3 ஆகும்.

நடைமுறைப்படுத்தல்

மீண்டும் மீண்டும் செய்யப்படும் சுபாரேயின் அதிகபட்ச நீளத்திற்கான சி ++ நிரல்

#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

மீண்டும் மீண்டும் செய்யப்படும் சுபாரேயின் அதிகபட்ச நீளத்திற்கான ஜாவா நிரல்

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) எங்கே "ஏ" முதல் வரிசையின் அளவு மற்றும் “ஆ” இரண்டாவது வரிசையின் அளவு.

குறிப்பு