ထပ်ခါတလဲလဲ Subarray ၏အမြင့်ဆုံးအရှည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် တကယ်ပါပဲ ကရာတေး Roblox
အခင်းအကျင်း Binary Search Dynamic Programming တားဆီးခြင်း

ပြproblemနာ“ Maximum Repeated Subarray” တွင် Array 1 နှင့် Array 2 နှစ်ခုကိုကျွန်ုပ်တို့ပေးထားပြီး၊ သင်၏တာ ၀ န်သည်နှစ်ခုလုံးတွင်ပါရှိသော sub-array ၏အများဆုံးအရှည်ကိုရှာဖွေရန်ဖြစ်သည်။ Array များ.

နမူနာ

input:

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

output:

3

ရှင်းလင်းချက်:

အဘယ်ကြောင့်ဆိုသော် sub-ခင်းကျင်း၏အမြင့်ဆုံးအရှည်မှာ ၃ ဖြစ်၍ ဘုံခင်းကျင်းမှုသည် [3]

ထပ်ခါတလဲလဲ Subarray ၏အမြင့်ဆုံးအရှည်

algorithm

  1. 0 ကို output ထားပါ။
  2. ကိန်းဂဏန်းအမှန်တစ်ခု၏အရှည်ထက် ၁ အရှည်ပိုသောကိန်းသေကိန်းတစ်ခုကိုကြေငြာပါ။
  3. ကနေစတင် ခင်းကျင်း၏နောက်ဆုံးအညွှန်းကိန်း array1 [i] သည် array2 [j] နှင့်ညီမျှမှုရှိမရှိစစ်ဆေးပါ၊ မှန်လျှင် val [i] [j] = val [i + 1] [j + 1] +1 ။
  4. output [Val] ထက်နည်းလျှင် output = val [i] [j] ကိုလုပ်ပါ။
  5. ခင်းကျင်းမှုတစ်ခုလုံးကိုဖြတ်ပြီးကျွန်ုပ်တို့အများဆုံးထွက်ရှိသည့်အခြေအနေများကိုစစ်ဆေးပါ။
  6. output ကိုပြန်သွားပါ။

ရှင်းလင်းချက်

ကျွန်တော်တို့ရဲ့ output ကိုရရန်, ငါတို့သည်အချို့သောရိုးရှင်းသောဖြတ်သန်းလုပ်ဖို့လိုအပ်ပါတယ်။ ဒီအတွက် output ကို 0 ဖြစ်အောင်လုပ်မယ်။ 2-D ကိုကြေငြာမယ် matrix array1 နှင့် array2 ၏အရှည်ထက်အရှည်တ ဦး တည်းပို။

ကျွန်ုပ်တို့သည် array ၏နောက်ဆုံးအညွှန်းကိန်းမှနှစ်မျိုးလုံးကိုဖြတ်သွားပါမည်။ ဒါကြောင့်ကျွန်တော်တို့ဟာအခြေအနေအချို့ကိုစစ်ဆေးပြီးရလဒ်ကို output ထဲမှာသိမ်းထားပါမယ်။

ဒါကြောင့်ဥပမာတစ်ခုယူပြီးထပ်မံလုပ်ဆောင်ကြပါစို့။

နမူနာ

ဥပမာအားဖြင့်ခင်းကျင်းထားသည်ဆိုပါစို့။

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

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

output = 0;

  • ဈ = 4, ည = 4;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

output = 0;

  • ဈ = 4, ည = 3;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

output = 0;

  • ဈ = 4, ည = 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.

ထို့နောက် output ကို <Val [i] [ည] စစ်မှန်တဲ့ပြန်လာနှင့် output ကို = 1 ပြုပါလျှင်စစ်ဆေးပါ။

output = 1;

  • ဈ = 4, ည = 1;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 4, ည = 0;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 3, ည = 4;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 3, ည = 3;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 3, ည = 2;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 3, ည = 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 ။

ထို့နောက် output ကို <val [i] [ည] စစ်မှန်တဲ့ပြန်လာနှင့် output ကို = val [i] [ည] ပြုပါလျှင်စစ်ဆေးပါ။

output = 2;

  • ဈ = 3, ည = 0;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 2, ည = 4;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 2, ည = 3;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 2, ည = 2;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 2, ည = 1;

array1 [i] == array2 [ည] သည်မှားယွင်းစွာပြန်လာလျှင်ဘာတစ်ခုမှမလုပ်ပါ။

  • ဈ = 2, ည = 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 ။

ထို့နောက် output ကို <val [i] [ည] စစ်မှန်တဲ့ပြန်လာနှင့် output ကို = val [2] [0] ပြုပါလျှင်စစ်ဆေးပါ။

output = 3;

၎င်းသည်ထပ်ပေါင်းထားသော array ၏အရှည်သည် ၃ ဖြစ်သည်၊ ကျွန်ုပ်တို့သည် element များကို traversing တွင်တူညီစွာတွေ့ရှိပြီးနောက်၌ပင် output သည် update မလုပ်နိုင်ပါ၊ အဘယ်ကြောင့်ဆိုသော်၎င်းသည် subarray မဟုတ်သောကြောင့်ဖြစ်သည်

i = 1, j = 1 မှာဆိုပါစို့နောက်ထပ်အလားတူဒြပ်စင်ကိုရှာတော့မည်။ val [1] [1] = val [2] [2] +1;

output <val [1] [1] ကိုစစ်ဆေးပါက၎င်းသည် false ပြန်လာတိုင်းမည်သည့်အရာမျှလုပ်လိမ့်မည်မဟုတ်ပါ။

ဒီတော့ဒီမှာ output က 3 ။

အကောင်အထည်ဖော်ရေး

ထပ်ခါတလဲလဲပြုလုပ်သော Subarray အများဆုံးအရှည်အတွက် 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

Repeated Subarray ၏အများဆုံးအရှည်အတွက် 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

ထပ်ခါတလဲလဲ Subarray ၏အများဆုံးအရှည်များအတွက်ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (က×ခ) ဘယ်မှာ "တစ်ဦးက" သည်ပထမဆုံးခင်းကျင်းသည့်အရွယ်အစားဖြစ်သည် “ ခ” ဒုတိယခင်းကျင်းမှု၏အရွယ်အစားဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (က×ခ) ဘယ်မှာ "တစ်ဦးက" သည်ပထမဆုံးခင်းကျင်းသည့်အရွယ်အစားဖြစ်သည် “ ခ” ဒုတိယခင်းကျင်းမှု၏အရွယ်အစားဖြစ်သည်။

အညွှန်း