Άθροισμα Λύσης Leetcode Subarrays Μονής Μονάδας


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις LinkedIn
Παράταξη

Δήλωση προβλήματος

Σε αυτό το πρόβλημα δίνεται μια σειρά θετικών ακέραιων αριθμών. Πρέπει να υπολογίσουμε και να επιστρέψουμε έναν ενιαίο ακέραιο, το άθροισμα όλων των πιθανών υποζώνων μονής διάρκειας της συγκεκριμένης συστοιχίας. Ένα subarray είναι μια συνεχόμενη ακολουθία του παράταξη.

Παράδειγμα

arr = [1,4,2,5,3]
58

Επεξήγηση:

Οι δευτερεύουσες σειρές του arr και των αθροισμάτων τους είναι:
[1] = 1, [4] = 4, [2] = 2, [5] = 5, [3] = 3, [1,4,2] = 7, [4,2,5] = 11, [2,5,3] = 10, [1,4,2,5,3] = 15
Προσθέτοντας όλα αυτά μαζί παίρνουμε 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

arr = [1,2]
3

Επεξήγηση:

Υπάρχουν μόνο 2 δευτερεύουσες σειρές με περίεργο μήκος, [1] και [2]. Το άθροισμά τους είναι 3.

Προσέγγιση (Brute Force)

Για την επίλυση αυτού του προβλήματος με ωμή βία, είναι πολύ εύκολο να δούμε από το πρόβλημα ότι πρέπει απλώς να πάμε για όλα τα δευτερεύοντα δευτερεύοντα μήκη και να υπολογίσουμε το συνολικό άθροισμα και να το επιστρέψουμε.
Μπορούμε να το εφαρμόσουμε ακολουθώντας απλά βήματα:

1. Δημιουργήστε μια μεταβλητή άθροισμα για να αποθηκεύσετε το συνολικό ποσό.
2. Εκτελέστε ένα βρόχο a για όλες τις δευτερεύουσες σειρές με αρχικό μήκος len= 1 και συνεχίστε να αυξάνετε την τιμή κατά 2 ενώ len <= n (μέγεθος του πίνακα).
3. Μέσα σε αυτόν τον βρόχο, εκτελέστε ένα βρόχος για την αρχική θέση του subarray από i = 0 έως i = n-len.
4. Μέσα στον παραπάνω βρόχο, εκτελέστε έναν βρόχο για αυτήν την υποπεριοχή του οποίου ο δείκτης ξεκινά από το i και τελειώνει στο i +len-1 και προσθέστε όλα τα στοιχεία αυτής της περιοχής.
5. Επιτέλους επιστρέψτε το άθροισμα.

Εφαρμογή για το άθροισμα όλων των υπομονάδων μονής διάρκειας Leetcode Solution

Πρόγραμμα C ++

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Πρόγραμμα Java

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int len=1;len<=n;len+=2)
        for(int i=0;i<n-len+1;i++)
            for(int j=i;j<i+len;j++) 
                sum+=arr[j];
    
    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Ανάλυση πολυπλοκότητας για το άθροισμα όλων των σειρών με περίεργο μήκος Leetcode Solution

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

O (n ^ 3): Έχουμε χρησιμοποιήσει τρεις βρόχους σε ένθετη μορφή όπου κάθε βρόχος εκτελείται τις ακόλουθες φορές:
Ο πρώτος βρόχος εκτελείται n / 2 φορές.
Ο δεύτερος βρόχος εκτελείται (n-len) φορές, πού len είναι 1,3,4,….
Τρίτος βρόχος εκτελείται len φορές.
Ο συνολικός χρόνος θα είναι (n / 2) * (n-len)*len. Ως εκ τούτου, το ανώτερο όριο της πολυπλοκότητας του χρόνου θα είναι O (n ^ 3) Όπου n είναι το μέγεθος της δεδομένης συστοιχίας.

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

O (1): Η πολυπλοκότητα του διαστήματος είναι σταθερή.

Προσέγγιση (Βελτιστοποιημένη ώρα)

Όπως μπορούμε να δούμε ότι η παραπάνω λύση brute force έχει πολυπλοκότητα χρόνου O (n ^ 3). Μπορούμε να το ελαχιστοποιήσουμε γιατί στην παραπάνω προσέγγιση προσθέτουμε το ίδιο στοιχείο πολλές φορές για διαφορετικά subarrays. Εάν κατά κάποιο τρόπο γνωρίζουμε πόσες φορές προστίθεται ένα συγκεκριμένο στοιχείο ή πρέπει να προστεθεί στο συνολικό άθροισμα, τότε μπορούμε να μειώσουμε την πολυπλοκότητα του χρόνου από O (n ^ 3) σε O (n).

Μπορούμε να αναλύσουμε ότι αν πάρουμε όλα τα subarrays (ομοιόμορφα και μονό μήκος), τότε σε αυτήν την περίπτωση ένα συγκεκριμένο στοιχείο στο ευρετήριο i θα εμφανιστεί σε όλες τις subarrays των οποίων ο αρχικός δείκτης είναι μικρότερος από ίσος με το i, και ο τελικός δείκτης είναι μεγαλύτερος από ίσος με i .

Επομένως μπορούμε να πούμε ότι ο συνολικός αριθμός αυτών των υποζώνων που περιέχει arr [i] (0-indexed) θα είναι ίσος με (i + 1) * (ni)
Αφήστε αυτήν την τιμή να είναι x.
Από τις οποίες υπάρχουν (x + 1) / 2 δευτερεύουσες σειρές με μονό μήκος που περιέχει arr [i].
Και x / 2 ζεύγους υπόγειους μήκους που περιέχουν arr [i].
Ως εκ τούτου, ένα [i] θα συνεισφέρει (x + 1) / 2 φορές στο συνολικό ποσό της λύσης μας.

Μπορούμε να το δούμε με ένα απλό παράδειγμα:

Ας arr = [1, 2, 3, 4, 5]

Άθροισμα Λύσης Leetcode Subarrays Μονής Μονάδας

Εξ ου και η συνεισφορά κάθε στοιχείου arr [i] σε περίεργες υποπεριοχές = arr [i] * ((i + 1) * (ni) +1) / 2.
Αυτό μπορεί να γίνει χρησιμοποιώντας έναν απλό βρόχο και ως εκ τούτου η χρονική πολυπλοκότητα αυτής της λύσης θα είναι γραμμική.

Εφαρμογή για το άθροισμα όλων των υπομονάδων μονής διάρκειας Leetcode Solution

Πρόγραμμα C ++

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Πρόγραμμα Java

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

int sumOddLengthSubarrays(vector<int>& arr) 
{
    int sum=0;
    int n=arr.size();

    for(int i=0;i<n;i++)
    {
        int contribution= ((i+1)*(n-i) +1)/2;
        sum+= contribution* arr[i];
    }

    return sum;
}

int main() 
{
    vector<int> arr = {1,4,2,5,3};
  
  cout<<sumOddLengthSubarrays(arr)<<endl;

  return 0; 
}
58

Ανάλυση πολυπλοκότητας για το άθροισμα όλων των σειρών με περίεργο μήκος Leetcode Solution

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

Επί) : Καθώς διασχίσαμε κάθε στοιχείο του πίνακα μόνο μία φορά, ως εκ τούτου η πολυπλοκότητα του χρόνου θα είναι O (n). Όπου n είναι το μέγεθος του δεδομένου πίνακα.

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

O (1): Δεν έχουμε χρησιμοποιήσει επιπλέον μνήμη, επομένως η πολυπλοκότητα του χώρου θα είναι σταθερή.