በአጠገብ ባሉት አካላት መካከል እንደ 0 ወይም 1 ልዩነት ካለው የከፍተኛው ርዝመት ቀጣይነት  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ Cisco Expedia Qualtrics የ SAP ላብራቶሪዎች ተራዳታ
ሰልፍ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ  

አንድ ተሰጥቶሃል ኢንቲጀር ደርድር. ችግሩ “በአጎራባች አካላት መካከል ያለው ልዩነት የከፍተኛው ርዝመት ቀጣይነት እንደ 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. በታች ባልሆኑ እሴቶች መካከል ልዩነት ሊኖረው ይገባል ፣ ይህንን ለመፍታት እኛ የምንጠቀምበት ማሳከክ መፍትሄያችንን ቀልጣፋ ለማድረግ ፡፡ ቁልፉን እንደ ድርድር አካል አድርገን እንወስዳለን እና የቁልፍ እሴቱን ሁልጊዜ ከፍተኛውን እሴት ፈልጎ ለማግኘት እና ለሙከራው ለማከማቸት እንሄዳለን ፡፡

እስቲ አንድ ምሳሌን እንመልከት እና ይህንን እንረዳ ፡፡

ለምሳሌ

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

እኛ የምናደርገው የመጀመሪያው ነገር ሀ ካርታ ምክንያቱም እኛ በተወያየንበት ስልተ-ቀመር መሠረት የድርድርን ንጥረ ነገር እና የእሴት ቴምፕሩን እናከማቸዋለን። የከፍተኛው ዋጋን ወደ 0. ያቀናብሩ ይህንን ተለዋዋጭ እንመልሳለን ፡፡ በዚያ ተለዋዋጭ ውስጥ ያለው የእኛ መልስ ይሆን ነበር ፡፡ አደረጃጀቱን አቋርጠን ወደ ድርድሩ ርዝመት እንዲደርስ እናደርጋለን ፡፡ ድርድሩን በአዲሱ የ i እሴት በምናቋርጥ ቁጥር የእሴት ቴምፕሬሽንን ወደ 0 እንጀምራለን ፡፡

i = 0, arr [i] = 1, temp = 0, ከፍተኛ ዋጋ = 0 ካርታ = {}

የትኛው ሁኔታ እንደሚሟላ ይፈትሹ ፡፡ በዚህ ሁኔታ ምንም ሁኔታ የለም ፡፡ ስለዚህ ቴምፕ ++ ን ይሠራል እና ቴምብሩ ከከፍተኛው እሴት የበለጠ ከሆነ ይፈትሻል። እውነት ከሆነ ታዲያ ቴምፕሩን ወደ ከፍተኛው እሴት ያከማቹ እና እሴቱን እና ቴምፕሩን በካርታው ውስጥ ያስገቡ።

i = 1 ፣ arr [i] = 4 ፣ temp = 0 ፣ ከፍተኛ እሴት = 1

ካርታ = {1,1}

ከላይ ካለው ሁኔታ ጋር ተመሳሳይ ፣ እሴቶቹን በካርታ ላይ ብቻ እናስገባቸዋለን

i = 2 ፣ arr [i] = 5 ፣ temp = 0 ፣ ከፍተኛ እሴት = 1

ተመልከት
በተሰጡት ክልሎች ውስጥ እኩል ወይም ጎዶሎ ቁጥር ሊኖር ስለሚችል ጥያቄዎች

ካርታ = {1: 1, 4: 1}

በዚህ ጊዜ ካርታው “[i] -1 ን የያዘውን የመጀመሪያውን ሁኔታ ትክክለኛ ሆኖ እናገኘዋለን ፡፡ 4. ስለሆነም 1 ን እንደ ቴምፕ ይወስዳል እና ቴምፕ ++ ያድርጉ ፡፡ ከዚያ ከፍተኛውን እሴት ወደ 2 ይቀይሩ እና arr [i] ን እና ውስጡን ያስገቡ።

እና እንደዚህ በቀላሉ እኛ ሁኔታዎችን መፈተሽ እና እሴቶችን በቅጽበት መውሰድ እንቀጥላለን። በካርታ ውስጥ ማስገባትዎን ይቀጥሉ ፣ በመጨረሻ እኛ እንደ ውጤታችን በከፍተኛው እሴት ውስጥ እሴቱን እናገኛለን።

በአጠገብ ባሉት አካላት መካከል እንደ 0 ወይም 1 ልዩነት ካለው የከፍተኛው ርዝመት ቀጣይነትጭንቅላታም መያያዣ መርፌ

ኮድ  

በአጠገብ ባሉት አካላት መካከል እንደ 0 ወይም 1 ባሉ ልዩነቶች መካከል ከፍተኛውን ርዝመት ቀጣይነት ለማግኘት የ C + + ኮድ

#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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ሁሉንም ንጥረ ነገሮች በቅደም ተከተል በቀላሉ ተሻግረናል። እኛ ሃሽ ማፕን ስለ ተጠቀምን በ Linear የጊዜ ውስብስብነት ውስጥ ማድረግ ችለናል ፡፡

ተመልከት
ከቀዝቃዛው ሌቲኮድ መፍትሄ ጋር ክምችት ለመግዛት እና ለመሸጥ የተሻለው ጊዜ

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በካርታው ውስጥ ካሉ ንጥረ ነገሮች ጋር የተዛመዱ መረጃዎችን ስለምናስቀምጥ የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።