Палиндром массивін құру үшін біріктіру операцияларының минималды санын табыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Акколит Adobe Amazon Фуркиттер
Array Ашкөздік математика

Проблемалық мәлімдеме

Сізге ан массив бүтін сандар. Мәселе қою палиндром массивін құру үшін біріктіру операцияларының минималды санын табуды сұрайды, яғни оны палиндромға айналдыру үшін массивте жасалатын біріктіру операцияларының минималды санын анықтайды. Біріктіру операциясы жай көршілес элементтердің қосындысын қосындының орнына алмастыра аламыз дегенді білдіреді.

мысал

arr[] = {1, 4, 6, 6, 5}
1

Түсініктеме: Біз 1 мен 4-ті олардың қосындысымен біріктіре аламыз, сондықтан ол 5-ке, ал біздің массив {5, 6, 6, 5} болады, бұл палиндром болып табылады.

arr[] = {2,1,2,4,3}
2

Түсініктеме: Біз 1 мен 2-ді олардың қосындысымен біріктіре аламыз, сондықтан ол 3-ке айналады, және 2 мен 4-ті біріктіруге болады, сондықтан біздің массив {3, 6, 3} болады

 

Палиндром массивін құру үшін біріктіру операцияларының минималды санын табу алгоритмі

1. Set the value of output to 0.
2. Traverse the array from i = 0 and j = n – 1, to i < n( length of an array).
  1. If arr[i] is equal to arr[j]
    1. Do i++ and j--.
  2. If arr[i] > arr[j]
    1. Do j—
    2. Update and restore the value of arr[j] = arr[j] + arr[j+1].
    3. Increase the output’s value by 1.
  3. If arr[i] < arr[j],
    1. Increase the value of i.
    2. Update arr[i] = arr[i] + arr[i-1].
    3. Increase the output’s value by 1.
3. Return output.

 

Түсіндіру

Біз бүтін сандар жиымын бердік. Бізден ең төменгі санын білу сұралады біріктіру массивте жасауға болатын амалдар палиндром массив. Мұнда біріктіру дегеніміз екі іргелес мәнді қосу және оларды олардың қосындысымен ауыстыру. Міне, біз жасалатын операциялардың санын табамыз.

Біз массивті солдан, сондай-ақ оң жақтан өтеміз, екі көрсеткіш әр траверсаль индексінің орнын көрсетеді. Біз екі жағын да таңдап алдық, өйткені оның палиндромды екенін тексеруге тура келеді. Палиндромда екі жағынан да индекстері бойынша элементтер палиндромдар сияқты тең. Сондықтан біз қарама-қарсы жақтардың мәнін тексеріп, олардың индекстерімен жұмыс жасаймыз. Содан кейін біз біріктіру операцияларын орындаймыз және орындалатын операциялар санын тапқанға дейін жалғастырамыз.

Біз сол жақтағы және оң жақтағы бірінші элементтің тең екендігін тексереміз. Содан кейін көрсеткіштерді орталыққа қарай бір бірлікке ауыстырыңыз. Сол жақ көрсеткіш индексінің элементі оң көрсеткіш индекс элементінен үлкен екенін тексеріп, содан кейін оң көрсеткіш мәнінің мәнін төмендетіп, [j] қатарын іргелес элементтердің қосындысымен жаңартыңыз және шығыс мәнін көбейтіңіз дегеніміз операциялар.

Біз сол жақ көрсеткіш индексінің элементі оң көрсеткіш индекс элементінен кіші екенін тексереміз, содан кейін сол көрсеткіш мәнінің мәнін көбейтеміз және [i] массивін іргелес элементтердің қосындысымен жаңартамыз және шығыс мәнінің жоғарылауын білдіреді операциялардың саны. Ақыр соңында біз шығыс мәнін қайтарамыз.

Палиндром массивін құру үшін біріктіру операцияларының минималды санын табыңыз

Палиндром массивін құру үшін біріктіру операцияларының минималды санын табу үшін код

C ++ коды

#include<iostream>

using namespace std;

int getMinimumOperation(int arr[], int n)
{
    int output = 0;

    for (int i=0,j=n-1; i<=j;)
    {
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }
        else if (arr[i] > arr[j])
        {
            j--;
            arr[j] += arr[j+1] ;
            output++;
        }
        else
        {
            i++;
            arr[i] += arr[i-1];
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = { 1, 4, 6, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum operations to be done: "<< getMinimumOperation(arr, n);
    return 0;
}
Minimum operations to be done: 1

 

Java коды

class ArrayPalindromeMerging
{
    public static int getMinimumOperation(int[] arr, int n)
    {
        int output = 0;
        for (int i=0,j=n-1; i<=j;)
        {
            if (arr[i] == arr[j])
            {
                i++;
                j--;
            }
            else if (arr[i] > arr[j])
            {
                j--;
                arr[j] += arr[j+1] ;
                output++;
            }
            else
            {
                i++;
                arr[i] += arr[i-1];
                output++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 6, 5} ;
        System.out.println("Minimum operations to be done : "+ getMinimumOperation(arr, arr.length));
    }
}
Minimum operations to be done : 1

 

Күрделілікті талдау

Уақыттың күрделілігі

Біз жай ғана массивті бір рет айналып өтеміз, сондықтан бұл сызықтық уақыттың күрделілігі үшін саналады. O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

Біз тек кірісті сақтау үшін n өлшемі бар бір массивті қолданамыз, осылайша бұл палиндром массивін құру үшін біріктіру операцияларының санын табудың алгоритмі кеңістіктің сызықтық күрделілігіне ие. O (N) қайда «N» - бұл массивтегі элементтер саны.