Εξασφαλίστε το μέγιστο στη λύση Generated Array Leetcode  


Επίπεδο δυσκολίας Εύκολος
αλγόριθμοι Παράταξη κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions

Το πρόβλημα Get Maximum in Generated Array Leetcode Solution μας έδωσε έναν ενιαίο ακέραιο. Με το δεδομένο single ακέραιος αριθμός, πρέπει να βρούμε τον μέγιστο ακέραιο στον παραγόμενο πίνακα. Η δημιουργία πίνακα έχει ορισμένους κανόνες. Κάτω από τους επιβληθέντες περιορισμούς, πρέπει να βρούμε τον μέγιστο ακέραιο που θα μπορούσε να είχε δημιουργηθεί. Οι κανόνες είναι:

  1. arr [0] = 0, arr [1] = 1
  2. arr [2 * i] = arr [i] όπου 2 <= 2 * i <= n
  3. και arr [2 * i + 1] = arr [i] + arr [i + 1] όπου 2 <= 2 * i + 1 <= n

Αλλά πριν βυθιστείτε περαιτέρω στη λύση. Πρέπει να ρίξουμε μια ματιά σε μερικά παραδείγματα.

Εξασφαλίστε το μέγιστο στη λύση Generated Array LeetcodeΚαρφώστε

n = 7
3

Επεξήγηση: Σύμφωνα με τους δεδομένους κανόνες:
αριθμοί [0] = 0, αριθμοί [1] = 1
αριθμοί [(1 * 2) = 2] = αριθμοί [1] = 1
αριθμοί [(1 * 2) + 1 = 3] = αριθμοί [1] + αριθμοί [2] = 1 + 1 = 2
αριθμοί [(2 * 2) = 4] = αριθμοί [2] = 1
αριθμοί [(2 * 2) + 1 = 5] = αριθμοί [2] + αριθμοί [3] = 1 + 2 = 3
αριθμοί [(3 * 2) = 6] = αριθμοί [3] = 2
αριθμοί [(3 * 2) + 1 = 7] = αριθμοί [3] + αριθμοί [4] = 2 + 1 = 3

Έτσι, μπορούμε να δούμε αριθμούς = [0,1,1,2,1,3,2,3], και το μέγιστο είναι 3 μεταξύ τους. Έτσι, η απάντηση είναι 3.

Προσέγγιση για τη λήψη του μέγιστου σε παραγόμενη λύση Aret Leetcode  

Το πρόβλημα Get Maximum in Generated Array Leetcode Solution έχει ορισμένους περιορισμούς που πρέπει να ικανοποιηθούν. Κάτω από τους δεδομένους περιορισμούς, πρέπει να βρούμε τον μέγιστο ακέραιο. Οι κανόνες για τη δημιουργία πίνακα έχουν ήδη εξηγηθεί στην περιγραφή του προβλήματος. Η πρώτη μέθοδος που έρχεται στο μυαλό είναι η δημιουργία πίνακα και η εύρεση του μέγιστου στοιχείου. Αλλά αυτό θα λύσει το πρόβλημα;

Βλέπε επίσης
Συγχώνευση δύο ταξινομημένων λιστών Λύσεις κωδικού Leetcode

Αν απλά προχωρήσουμε με τη γενιά δεν θα μπορέσουμε να βρούμε σωστά αποτελέσματα. Επειδή εξαρτάται από τον τρόπο δημιουργίας του πίνακα. Εάν δημιουργούμε στοιχεία στο ευρετήριο 2ith και (2i + 1) όταν βρισκόμαστε στο ευρετήριο ith. Εκείνη τη στιγμή, δεν θα έχουμε την παραγόμενη τιμή για το (i + 1) th ευρετήριο. Σε αυτήν την περίπτωση, το αποτέλεσμα δεν θα είναι ακριβές.

Για να λύσουμε το πρόβλημα, θα χειριστούμε τους τύπους για τη δημιουργία στοιχείων. Αν αντικαταστήσουμε το i με το i-1, στον 3ο κανόνα. βρίσκουμε ότι arr [2 * i-1] = arr [i] + arr [i-1]. Έτσι, τώρα μπορούμε να χρησιμοποιήσουμε τους κανόνες για τη δημιουργία πίνακα. Επειδή αυτός ο κανόνας χρησιμοποιεί την τιμή της ήδη δημιουργημένης τιμής. Έτσι, αντί να χρησιμοποιήσουμε μελλοντικές άγνωστες τιμές, χρησιμοποιούμε τις προκαθορισμένες τιμές. Τώρα λοιπόν απλώς προσομοιώνουμε ολόκληρη τη διαδικασία χρησιμοποιώντας ένα για βρόχο και ελέγχουμε αν τα 2 * i και 2 * i-1 βρίσκονται στα όρια του πίνακα. Μόλις επιβεβαιωθεί, χρησιμοποιούμε τους τύπους για να συμπληρώσουμε τον πίνακα.

Κώδικας  

Κωδικός C ++ για Λήψη Μέγιστου σε Λύση Generated Array Leetcode

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

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

Κωδικός Java για Λήψη Μέγιστου σε Λύση Generated Array Leetcode

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

Ανάλυση πολυπλοκότητας  

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί δημιουργούμε όλα τα στοιχεία n.

Βλέπε επίσης
Σύνολο λύσεων Leetcode Left Leaves

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

ΕΠΙ), επειδή δημιουργήσαμε έναν προσωρινό πίνακα για να αποθηκεύσουμε τις τιμές του πίνακα.

1