סכום כל פתרונות ה- Leetcode באורך מוזר


רמת קושי קַל
נשאל לעתים קרובות לינקדין
מערך

הצהרת בעיה

בבעיה זו ניתן מערך של מספרים שלמים חיוביים. עלינו לחשב ולהחזיר מספר שלם יחיד, סכום כל מערכי המשנה האפשריים באורך מוזר של המערך הנתון. מערך משנה הוא המשך רציף של מערך.

דוגמה

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.

גישה (כוח ברוט)

כדי לפתור בעיה זו בכוח גס, קל מאוד לראות מהבעיה שעלינו פשוט ללכת על כל מערכי המשנה באורך מוזר ולחשב את הסכום הכולל ולהחזיר אותו.
אנו יכולים ליישם זאת על ידי ביצוע שלבים פשוטים:

1. צור משתנה סכום לאחסון הסכום הכולל.
2. הפעל לולאה עבור כל מערכי המשנה באורך מוזר החל מ לן= 1 והמשיך להגדיל את הערך ב -2 בזמן לן <= n (גודל המערך).
3. בתוך הלולאה הזו, הפעל א לולאה למיקום ההתחלה של מערך המשנה מ- i = 0 ל- i = n-len.
4. בתוך הלולאה שלעיל, הפעל לולאה למערך המשנה הזה שהאינדקס שלו מתחיל מ- i ומסתיים ב- i +לן-1 והוסף את כל האלמנטים של מערך המשנה הזה.
5. סוף סוף להחזיר את סכום.

יישום לסכום של כל פתרונות ה- Leetcode באורך מוזר

תוכנית 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 באורך מוזר

מורכבות זמן

O (n ^ 3): השתמשנו בשלושה לולאות בצורה מקוננת כאשר כל לולאה פועלת בפעמים הבאות:
הלולאה הראשונה פועלת n / 2 פעמים.
הלולאה השנייה פועלת (n-לן) פעמים, היכן לן הוא 1,3,4, ....
הלולאה השלישית פועלת לן פעמים.
הזמן הכולל יהיה (n / 2) * (n-לן)*לן. מכאן שהגבול העליון של מורכבות הזמן יהיה O (n ^ 3) כאשר n הוא גודל המערך הנתון.

מורכבות בחלל 

O (1): מורכבות החלל היא קבועה.

גישה (זמן אופטימיזציה)

כפי שאנו רואים שלפתרון הכוח הגס יש מורכבות זמן O (n ^ 3). אנו יכולים למזער זאת מכיוון שבגישה לעיל אנו מוסיפים את אותו אלמנט מספר רב של פעמים עבור מערכי משנה שונים. אם איכשהו אנו יודעים כמה פעמים מוסיפים אלמנט מסוים או צריך להוסיף אותו לסכום הכולל, אז נוכל להפחית את מורכבות הזמן מ- O (n ^ 3) ל- O (n).

אנו יכולים לנתח שאם ניקח את כל מערכי המשנה (באורך אחיד ואי-זוגי), אז במקרה כזה יסוד מסוים באינדקס i יתרחש בכל מערכי המשנה שמדד ההתחלה שלהם פחות משווה ל- i, ואינדקס הסיום גדול משווה ל- i .

לכן אנו יכולים לומר כי המספר הכולל של אותם מערכי משנה המכילים arr [i] (0 באינדקס) יהיה שווה ל- (i + 1) * (ni).
תן לערך זה להיות x.
מתוכם יש (x + 1) / 2 מערכי משנה באורך מוזר המכילים arr [i].
ו- x / 2 אפילו מערכי משנה באורך המכילים arr [i].
מכאן ש- [i] יתרום (x + 1) / פי 2 בסכום הכולל בפתרון שלנו.

אנו יכולים לראות זאת בדוגמה פשוטה:

תן ל- arr = [1, 2, 3, 4, 5]

סכום כל פתרונות ה- Leetcode באורך מוזר

מכאן התרומה של כל אלמנט arr [i] במערכי משנה מוזרים = arr [i] * ((i + 1) * (ni) +1) / 2.
ניתן לעשות זאת באמצעות לולאה אחת ומכאן שמורכבות הזמן של פתרון זה תהיה ליניארית.

יישום לסכום של כל פתרונות ה- Leetcode באורך מוזר

תוכנית 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 באורך מוזר

מורכבות זמן

O (n): כשעברנו כל אלמנט במערך פעם אחת בלבד, ולכן מורכבות הזמן תהיה O (n). כאשר n הוא גודל המערך הנתון.

מורכבות בחלל 

O (1): לא השתמשנו בזיכרון נוסף, ולכן מורכבות החלל תהיה קבועה.