Ακολουθία μέγιστου μήκους με διαφορά μεταξύ γειτονικών στοιχείων είτε 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.

εξήγηση

Μας δίνεται ένα ακέραιος αριθμός πίνακα, οι δηλώσεις προβλημάτων ζητούν να μάθουν το μέγιστο μήκος ακολουθίας. Και η επιλεγμένη ακολουθία πρέπει να είναι τέτοια ώστε να έχει διαφορά μεταξύ των παρακείμενων τιμών, εκτός από 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. Εάν ισχύει, αποθηκεύστε το temp στο maxValue και εισαγάγετε την τιμή και το temp στο χάρτη.

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

Κωδικός 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) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Έχουμε διαβάσει απλώς όλα τα στοιχεία του πίνακα. Επειδή χρησιμοποιήσαμε το HashMap, καταφέραμε να το κάνουμε σε γραμμική πολυπλοκότητα χρόνου.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα. Δεδομένου ότι αποθηκεύουμε δεδομένα που σχετίζονται με στοιχεία στο χάρτη, η πολυπλοκότητα του διαστήματος είναι επίσης γραμμική.