მაქსიმალური სიგრძის თანმიმდევრობა მეზობელ ელემენტებს შორის სხვაობით, როგორც 0 ან 1


Რთული ტური საშუალო
ხშირად ეკითხებიან Cisco Expedia Qualtrics SAP ლაბორატორიები Teradata
Array დინამიური პროგრამირება

პრობლემის განცხადება

თქვენ გეძლევათ მთელი რიცხვი მასივი. პრობლემა "მაქსიმალური სიგრძის თანმიმდევრობა მეზობელ ელემენტებს შორის სხვაობით, როგორც 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.

განმარტება

ჩვენ გვაძლევენ მთელი რიცხვი მასივი, პრობლემის დებულებები ითხოვს თანმიმდევრობის მაქსიმალური სიგრძის გარკვევას. არჩეული თანმიმდევრობა ისეთი უნდა იყოს, რომ მას სხვაობა ჰქონდეს მომიჯნავე მნიშვნელობებს შორის, გარდა 0 ან 1. ამის გადასაჭრელად გამოვიყენებთ ჰასინგი რომ ჩვენი გამოსავალი იყოს ეფექტური. ჩვენ ვაყენებთ კლავიშს, როგორც მასივის ელემენტს, და კლავიშის მნიშვნელობას ყოველთვის ვიპოვით მაქსიმალურ მნიშვნელობას და ვინახავთ მას ტემპერატურაზე.

მოდით განვიხილოთ მაგალითი და გავიგოთ ეს:

მაგალითი

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

პირველი, რასაც ჩვენ ვაკეთებთ, არის გამოცხადება ა რუკა რადგან ჩვენ ვაპირებთ მასივის ელემენტის და მნიშვნელობის ტემპერატურის შენახვას ჩვენს მიერ განხილული ალგორითმის შესაბამისად. დააყენეთ maxValue- ის მნიშვნელობა 0. ჩვენ ვაპირებთ ამ ცვლადის დაბრუნებას. რა არის ამ ცვლადში, იქნება ჩვენი პასუხი. ჩვენ გადავკვეთთ მასივს და მივაწვდინეთ მასივის სიგრძეს. ყოველთვის, როდესაც მასივს გადავატარებთ i- ს ახალ მნიშვნელობას, ჩვენ ვიცავთ მნიშვნელობას temp 0-ზე.

i = 0, arr [i] = 1, temp = 0, maxValue = 0 რუქა = {}

შეამოწმეთ რომელი პირობის შესრულება აპირებს. ამ შემთხვევაში არანაირი პირობა არ არსებობს. ასე რომ, ის ახდენს temp ++ - ს და ამოწმებს, ტემპერატურა maxValue– ზე მეტია თუ არა. თუ სიმართლეა, შეინახეთ ტემპერატურა 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}

ამჯერად პირველი პირობა სწორად მიგვაჩნია, რომ რუკა შეიცავს arr [i] -1, ანუ 4. ასე რომ, ის 1-ს იღებს temp- ით და აკეთებს temp ++. შემდეგ maxValue შეცვალეთ 2-ით და ჩასვით arr [i] და temp მასში.

და უბრალოდ ასე, ჩვენ განვაგრძობთ პირობების შემოწმებას და ტემპერატურის მნიშვნელობების აღებას. განაგრძეთ რუქაში ჩასმა, ბოლოს და ბოლოს, ჩვენ ვიღებთ მნიშვნელობას 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

ჯავის კოდი, რომ იპოვოთ მაქსიმალური სიგრძის თანმიმდევრობა, სხვაობა მიმდებარე ელემენტებს შორის, როგორც 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ჩვენ უბრალოდ გადავხედეთ მასივის ყველა ელემენტს. იმის გამო, რომ ჩვენ გამოვიყენეთ HashMap, ჩვენ შეგვეძლო ამის გაკეთება ხაზოვანი დროის სირთულეში.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც ჩვენ რუკაში ვინახავთ ელემენტებთან დაკავშირებულ მონაცემებს, სივრცის სირთულე ასევე ხაზოვანია.