Ən uzun Fibonacci Nəticəsinin Uzunluğu

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon
Geyim Dinamik proqramlaşdırmaBaxılıb 79

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Ciddi bir artım verildi array müsbət tam ədədin ən uzununu tapın Fibonacci sonrakılıq.
N elementdən ibarət olan bir sıra fibonacci, kimi,

  • n> = 3
  • xi = x(i - 2) +x(mən -1), burada xi mənth ardıcıllığın müddəti və i> = 2

Nümunələr

Input
arr [] = {1, 2, 3, 4, 5, 6, 7, 8}
Buraxılış
5
Izahat
Ən sonrakı kimi fibonacci {1, 2, 3, 5, 8}

Ən uzun Fibonacci Nəticəsinin UzunluğuPin

Input
arr [] = {1, 3, 7, 11, 12, 14, 18}
Buraxılış
3
Izahat
Aşağıdakı kimi ən uzun fibonacci {1, 11, 12} və ya {3, 11, 14} və ya {7, 11, 18}

Ən uzun fibonacci ardıcıllığının uzunluğu üçün sadəlövh yanaşma

Bir fibonacci kimi bir sıra üçün ilk iki şərt istənilən bir dəyəri əldə edə bilər və qalan şərtlər yuxarıda göstərilən düsturdan istifadə edərək müəyyən edilir. Misal üçün,
Birinci dövr 2, ikinci müddət 3 olarsa, fibonacci kimi ardıcıllıq 2, 3, 5, 8, 11,… kimi görünür.

The alqoritm hər hansı iki elementi Fibonacci kimi ardıcıllığın birinci və ikinci dövrü kimi seçməkdir, bunlar sırasıyla arr [i] və arr [j] kimi təmsil olunsun. Sonra növbəti müddət (arr [i] + arr [j]) olacaq, serialdakı növbəti termini axtarın. Əgər mövcuddursa, növbəti müddət (arr [j] + (arr [i] + arr [j])) olacaq, yenidən növbəti termini axtarın və növbəti müddət massivdə mövcud oluncaya qədər bu əməliyyatı təkrarlayın və tapın maksimum fibonacci uzunluğu.
Dizidəki növbəti müddət üçün axtarış hashing istifadə edərək optimallaşdırıla bilər.

Ən uzun fibonacci ardıcıllığının uzunluğu üçün komplekslik analizi

Zaman Mürəkkəbliyi = O (n)2 * log (m))
Kosmik Mürəkkəblik = O (n)
burada n - verilən massivdəki elementlərin sayı və m - verilmiş massivdəki maksimum dəyərdir.

JAVA Kodu

import java.util.HashSet;

public class LengthOfLongestFibonacciSubsequence {
    private static int longestLengthFibonacci(int[] arr) {
        int n = arr.length;
        HashSet<Integer> set = new HashSet<>();
        
        // Store all the elements of array in a hash set
        for (int i = 0; i < n; i++) {
            set.add(arr[i]);
        }
        
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Choose any two elements as the first and second term of fibonacci like sequence
                int firstTerm = arr[i];
                int secondTerm = arr[j];
                
                int nextTerm = firstTerm + secondTerm;
                int currLength = 2;
                
                // Search for next term till it exists in the array
                while (set.contains(nextTerm)) {
                    currLength++;
                    firstTerm = secondTerm;
                    secondTerm = nextTerm;
                    // Update next term
                    nextTerm = firstTerm + secondTerm;
                }
                
                // Update the maximum length of fibonacci like sequence
                maxLength = Math.max(maxLength, currLength);
            }
        }
        
        // If maxLength is 2, then return 0, else return maxLength
        return (maxLength == 2) ? 0 : maxLength;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {1, 2, 3, 4, 5, 6, 7, 8};

        System.out.println(longestLengthFibonacci(arr1));

        // Example 2
        int arr2[] = new int[] {1, 3, 7, 11, 12, 14, 18};

        System.out.println(longestLengthFibonacci(arr2));
    }
}
5
3

C ++ kodu

#include<bits/stdc++.h> 
using namespace std;

int longestLengthFibonacci(int *arr, int n) {
    set<int> hashSet;

    // Store all the elements of array in a hash set
    for (int i = 0; i < n; i++) {
        hashSet.insert(arr[i]);
    }
    
    int maxLength = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Choose any two elements as the first and second term of fibonacci like sequence
            int firstTerm = arr[i];
            int secondTerm = arr[j];
            
            int nextTerm = firstTerm + secondTerm;
            int currLength = 2;
            
            // Search for next term till it exists in the array
            while (hashSet.find(nextTerm) != hashSet.end()) {
                currLength++;
                firstTerm = secondTerm;
                secondTerm = nextTerm;
                // Update next term
                nextTerm = firstTerm + secondTerm;
            }
            
            // Update the maximum length of fibonacci like sequence
            maxLength = std::max(maxLength, currLength);
        }
    }
    
    // If maxLength is 2, then return 0, else return maxLength
    return (maxLength == 2) ? 0 : maxLength;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8};
    cout<<longestLengthFibonacci(arr1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, 3, 7, 11, 12, 14, 18};
    cout<<longestLengthFibonacci(arr2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
5
3

Ən uzun fibonacci ardıcıllığının uzunluğu üçün optimal yanaşma

Yuxarıda göstərilən problem istifadə edərək optimal şəkildə həll edilə bilər dinamik proqramlaşdırma.
İstənilən iki şərt Fibonacci kimi ardıcıllığın ilk iki şərtini təşkil edə bilər, ölçüsü 2-D olan dp (n X n), burada n, massivin ölçüsüdür. 2 ölçülü massivin bir elementi dp [i] [j], (i, j) ilə bitən Fibonacci ardıcıllığının maksimum uzunluğunu bildirir, yəni ardıcıllığın son iki şərtləri müvafiq olaraq i və j-dir.

Bir nümunəni nəzərdən keçirək, arr [] = {1, 2, 3, 4, 5, 6, 7, 8}
Mümkün olan bir fibonacci ardıcıllığı {1, 2, 3, 5, 8}, yəni {arr [0], arr [1], arr [2], arr [4], arr [7]}
Əvvəlcə hər hansı bir (i, j) ilə bitən ən uzun fibonacci ardıcıllığının uzunluğu 2, yəni əvvəlcə dp [i] [j] = 2-dir.
(J, k) ilə bitən ardıcıllığın maksimum uzunluğu = 1 + (i, j) ilə bitən ardıcıllığın maksimum uzunluğu, burada i elementin göstəricisi (arr [k] - arr [j]).
Yəni,
dp [j] [k] = 1 + dp [i] [j], burada i array arr içindəki elementin göstəricisi (arr [k] - arr [j]).

  1. Dizinin bütün elementlərinin indeksini hash xəritəsində saxlayın.
  2. N ölçüsünün (array) uzunluğu olduğu (n X n) ölçülü 2-ölçülü bir dp yaradın.
  3. Dp massivinin bütün elementlərinin başlanğıc dəyəri 2-dir.
  4. K> j olduğu hər cüt (j, k) üçün yuxarıda göstərildiyi kimi i indeksini hesablayın, əgər i varsa və j-dən fərqlənərsə, dp [j] [k] -i (1 + dp [i] [j] kimi yeniləyin. ). Həm də maksimum fibonacci uzunluğunu ardıcıllıqla yeniləyin.
  5. Fibonacci kimi ardıcıllığın maksimum uzunluğu 2-dirsə, 0-a qayıdın, əks halda maksimum uzunluğu qaytarın.

Ən uzun fibonacci ardıcıllığının uzunluğu üçün komplekslik analizi

Zaman Mürəkkəbliyi = O (n)2
Kosmik Mürəkkəblik = O (n)2

burada n - verilən massivdəki elementlərin sayı.

JAVA Kodu

import java.util.HashMap;

public class LengthOfLongestFibonacciSubsequence {
    private static int longestLengthFibonacci(int[] arr) {
        int n = arr.length;

        // Store the indices of all the elements of arr
        HashMap<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(arr[i], i);
        }

        // Initialize all the elements of dp as 2
        int dp[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }

        int maxLength= 2;

        for (int k = 0; k < n; k++) {
            for (int j = 0; j < k; j++) {
                // For every pair (j, k)
                if (index.containsKey(arr[k] - arr[j])) {
                    // Find the index i
                    int i = index.get(arr[k] - arr[j]);
                    // if i and j are not same
                    if (i != j) {
                        // use the formula dp[j][k] = 1 + dp[i][j]
                        dp[j][k] = 1 + dp[i][j];
                        // Update the maximum length
                        maxLength = Math.max(maxLength, dp[j][k]);
                    }
                }
            }
        }

        // If maxLength is 2, then return 0, else return maxLength
        return (maxLength == 2) ? 0 : maxLength;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {1, 2, 3, 4, 5, 6, 7, 8};

        System.out.println(longestLengthFibonacci(arr1));

        // Example 2
        int arr2[] = new int[] {1, 3, 7, 11, 12, 14, 18};

        System.out.println(longestLengthFibonacci(arr2));
    }
}
5
3

C ++ kodu

#include<bits/stdc++.h> 
using namespace std;

int longestLengthFibonacci(int *arr, int n) {
    // Store the indices of all the elements of arr
    unordered_map<int, int> index;
    for (int i = 0; i < n; i++) {
        index.insert(make_pair(arr[i], i));
    }
    
    // Initialize all the elements of dp as 2
    int dp[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 2;
        }
    }
    
    int maxLength = 2;
    
    for (int k = 0; k < n; k++) {
        for (int j = 0; j < k; j++) {
            // For every pair (j, k)
            auto itr = index.find(arr[k] - arr[j]);
            if (itr != index.end()) {
                // Find the index i
                int i = itr->second;
                // if i and j are not same
                if (i != j) {
                    // use the formula dp[j][k] = 1 + dp[i][j]
                    dp[j][k] = 1 + dp[i][j];
                    // Update the maximum length
                    maxLength = std::max(maxLength, dp[j][k]);
                }
            }
        }
    }
    
    // If maxLength is 2, then return 0, else return maxLength
    return (maxLength == 2) ? 0 : maxLength;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8};
    cout<<longestLengthFibonacci(arr1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, 3, 7, 11, 12, 14, 18};
    cout<<longestLengthFibonacci(arr2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
5
3

References

Crack Sistemi Dizayn Müsahibələri
Translate »