د 1d سرې لیټکوډ حل حل چلول


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه د بلومبرګ über
پیشه

ستونزه بیان

د 1d په روانه کچه سور ستونزه موږ ته یو سرنی شمیره راکړل شوې ده د کوم لپاره چې موږ باید یو سیر بیرته راوړو چېرته چې د هرې شاخص لپاره i په پایله کې د سرې آرر [i] = جمع (شمیره [0] ... نمبرونه [i]).

بېلګه

 nums = [1,2,3,4]
[1,3,6,10]

وضاحت:

د چلولو اندازه دا ده: [1 ، 1 + 2 ، 1 + 2 + 3 ، 1 + 2 + 3 + 4] = [1 ، 3 ، 6 ، 10]

nums = [1,1,1,1,1]
[1,2,3,4,5]

وضاحت:

روانه برخه دا ده: [1 ، 1 + 1 ، 1 + 1 + 1 ، 1 + 1 + 1 + 1 ، 1 + 1 + 1 + 1 + 1] = [1 ، 2 ، 3 ، 4 ، 5]

او کړنلاره

پدې ستونزه کې موږ باید یو صف رامینځته کړو چیرې چې په شاخص کې د عنصر ارزښت به په لومړي سر کې د لومړي څخه تر ith لړل شوي عنصر پورې د عناصرو مجموعې سره برابر وي.
د دې لپاره موږ کولی شو د ورکړل شوي شوي اندازې سره مساوي اندازه صفونه رامینځته کړو. بیا په لوپ کې د هر عنصر لپاره موږ کولی شو عنصر له شاخص 0 څخه شاخص i ته په اصلي صف کې اضافه کړو د بل لپاره د لوپ لپاره وکاروئ. د دې الګوریتم لپاره د وخت پیچلتیا به O (n ^ 2) وي.

موږ کولی شو یوازې د واحد په کارولو سره د دې ستونزې لپاره د وخت پیچلتیا کمه کړو لوپ.
راځئ چې شمیره ورکړل شوي صفونه وي او ریسز یو صف وي په کوم کې چې موږ د روانې پیسو ذخیره کوو ، نو بیا موږ ریسز محاسبه کولی شو [i] په لاندې ډول:

ریس [i] = ریس [i-1] + نمبرونه [i].

مثال: نمبرونه [[1,2,3,4،XNUMX،XNUMX،XNUMX] په لاندې شکل کې ښودل شوي ،

د 1d سرې لیټکوډ حل حل چلول

نو لدې امله موږ اړتیا نلرو چې د لقب د بیا محاسبې لپاره لوپ پرمخ بوزو ځکه چې موږ دمخه سرشمېر لرو چې ما د ریس سرلي په تیر شاخص کې ساتلی دی.

تطبیق

د 1d سرې لیټکوډ حل حل لپاره چلولو لپاره C ++ برنامه

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

vector<int> runningSum(vector<int>& nums) 
{
    vector<int> res(nums.size());
    if(nums.size()==0) return res;

    res[0]=nums[0];
    for(int i=1;i<nums.size();i++)
    {
        res[i]=res[i-1]+ nums[i];
    }

    return res;

}

int main() 
{
  vector<int> nums={1,2,3,4};
  vector<int> res= runningSum(nums);
  
  cout<<"[";
  
  for(int i=0;i<res.size()-1;i++) cout<<res[i]<<",";
  
  cout<<res.back()<<"]"<<endl;

  return 0; 
}
[1,3,6,10]

د 1d سرنی لیټکوډ حل حل لپاره روانې جاوا برنامې

import java.lang.*;

class Rextester
{  
    public static int[] runningSum(int[] nums) 
    {
        int[] res= new int[nums.length];
        if(nums.length==0) return res;

        res[0]=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            res[i]=res[i-1]+ nums[i];
        }

        return res;
    }
    
    public static void main(String args[])
    {
        int nums[]={1,2,3,4};
        int res[]= runningSum(nums);

        System.out.print("[");

        for(int i=0;i<res.length-1;i++) System.out.print(res[i]+",");

        System.out.println( res[res.length-1] + "]");
        
    }
}
[1,3,6,10]

د 1d سرې لیټکوډ حل حل چلولو لپاره پیچلي تحلیلونه

د وخت پیچلتیا

O (n): چیرې چې n د ورکړل شوي صف اندازه ده. لکه څنګه چې موږ یوازې د لوپ لپاره یوازې یو ، نو له دې امله د وخت پیچلتیا به خطي وي.

د ځای پیچلتیا 

O (n): دلته موږ د n اندازه اندازې پایله کې رامینځته کوو. د همدې لپاره د ځای پیچلتیا به هم خطي وي.