0 же 1 деп чектеш элементтердин айырмасы менен максималдуу узундуктагы секреция  


Кыйынчылык деңгээли орто
Көп суралган Cisco Expedia Qualtrics SAP Labs Терадата
согуштук тизме Динамикалык программалоо

Маселени билдирүү  

Сизге ан бүтүн согуштук тизме. "Чектелген элементтердин айырмасы 0 же 1 деп максималдуу узундуктун ырааттуулугу" көйгөйү чектеш элементтердин айырмасы менен максималдуу ырааттуулуктун узундугун 0 же 1ден башка болбошу керек.

мисал  

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

түшүндүрүү

Кийинки = 4, 5, 6, 5, 4

arr[] = {1, -3, -2, 0, -1, -2, -3, -4}
6

түшүндүрүү

Кийинкилик = -3, -2, -1, -2, -3, -4

0 же 1 деп чектеш элементтердин айырмасы менен максималдуу узундуктун ырааттуулугун табуу алгоритми  

1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
  1. Initialize a variable temp to 0.
  2. Check if Map contains the key as arr[i-1],
    1. If true, then get the value of arr[i-1] and store it to temp.
  3. Check if Map contains the key as arr[i],
    1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
  4. Check if Map contains the key as arr[i+1],
    1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
  5. Check if the temp is greater than maxValue,
    1. If true then store the value of temp to maxValue.
  6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.

түшүндүрүү

ошондой эле
Массивдин Stack Sortable экендигин текшериңиз

Бизге ан бүтүн массив, көйгөйлөрдүн жыйындысы максималдуу кийинки узундукту билүүнү суранат. Жана тандалган төмөнкүдөй болушу керек, ал чектеш маанилердин айырмасы 0 же 1ден башка болбошу керек. Муну чечүү үчүн колдонобуз Хеширлөө биздин чечүүбүздү натыйжалуу кылуу. Ачкычты массивдин элементи катары коюп, ачкычтын маанисин алып, ар дайым максималдуу маанини таап, аны убактылуу сактайбыз.

Келгиле, бир мисалды карап чыгып, муну түшүнүп алалы:

мисал

Arr [] = {1, 4, 5, 2, 6, 5, 4, 8}

Биз жасай турган биринчи нерсе - жарыялоо карта анткени биз массивдин элементин жана temp маанисин талкуулаган алгоритмге ылайык сактайбыз. MaxValue маанисин 0 деп коюңуз. Бул өзгөрмөнү кайтарабыз. Ошол өзгөрмөдө эмне бар болсо, ал бизге жооп берет. Биз массивди айланып өтүп, аны массивдин узундугуна жеткиребиз. Массивди жаңы i мааниси менен өткөн сайын, temp маанисин 0 деп инициализациялайбыз.

i = 0, arr [i] = 1, temp = 0, maxValue = 0 Map = {}

Кайсы шарттын аткарыларын текшериңиз. Бул учурда эч кандай шарт жок. Ошентип, ал temp ++ кылып, temp maxValue дан чоң экендигин текшерет. Эгер чын болсо, анда tempди maxValue ичине сактап, маанисин жана темпин картага киргизиңиз.

i = 1, arr [i] = 4, temp = 0, maxValue = 1.

Карта = {1,1}

Жогорудагыдай эле, биз картага баалуулуктарды киргизебиз

i = 2, arr [i] = 5, temp = 0, maxValue = 1.

ошондой эле
Берилген аралыктагы жуп же так сандын ыктымалдуулугу боюнча суроолор

Карта = {1: 1, 4: 1}

Бул жолу биз биринчи шартты туура таптык, ал картада [i] -1 4 турат, демек, ал 1ди темп катары кабыл алат жана temp ++ жасайт. Андан кийин maxValue 2ге өзгөртүңүз жана arr [i] киргизип, ага темпти киргизиңиз.

Жана ушул сыяктуу эле, биз шарттарды текшерип, маанилерди ылдамдык менен кабыл алабыз. Картага киргизе бериңиз, акыры maxValue маанисине ээ болобуз.

0 же 1 деп чектеш элементтердин айырмасы менен максималдуу узундуктагы секрециятөөнөч

коду  

C ++ кодун табуу үчүн, чектеш элементтердин айырмасы 0 же 1 болушу мүмкүн

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int maxValue = 0;
    for (int i=0; i<n; i++)
    {
        int temp = 0;
        if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
            temp = MAP[arr[i]-1];

        if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
            temp = MAP[arr[i]];

        if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
            temp = MAP[arr[i]+1];

        MAP[arr[i]] = temp + 1;

        if (maxValue < MAP[arr[i]])
            maxValue = MAP[arr[i]];
    }
    return maxValue;
}
int main()
{
    int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumLenSubsequence(arr, n);
    return 0;
}
5

Java кодун табуу үчүн, чектеш элементтердин айырмасы 0 же 1 деп максималдуу узундуктагы секреция болот

import java.util.HashMap;

class subsequenceLength
{
    public static int getMaximumLenSubsequence(int[] arr)
    {
        int maxValue = 0;
        HashMap<Integer, Integer> MAP = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            int temp = 0;
            if (MAP.containsKey(arr[i] - 1))
            {
                temp = MAP.get(arr[i] - 1);
            }

            if (MAP.containsKey(arr[i]))
            {
                temp = Math.max(temp, MAP.get(arr[i]));
            }

            if (MAP.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, MAP.get(arr[i] + 1));
            }
            temp++;
            if (temp > maxValue)
            {
                maxValue = temp;
            }
            MAP.put(arr[i], temp);
        }
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
        System.out.println(getMaximumLenSubsequence(arr));
    }
}
5

Комплекстик анализ  

Убакыт татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Биз жөн гана массивдеги бардык элементтерди кыдырып чыктык. HashMap колдонулгандыктан, биз аны сызыктуу убакыттын татаалдыгында жасай алдык.

ошондой эле
Cooldown Leetcode Solution менен Стокту сатып алуу жана сатуу үчүн мыкты убакыт

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Картада элементтерге байланыштуу маалыматтарды сактап жаткандыктан, мейкиндиктин татаалдыгы дагы сызыктуу.