1d வரிசை லீட்கோட் தீர்வின் இயங்கும் தொகை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ப்ளூம்பெர்க் கிழித்து
அணி

சிக்கல் அறிக்கை

1d இயங்கும் தொகையில் வரிசை சிக்கல் எங்களுக்கு ஒரு வரிசை எண்கள் வழங்கப்பட்டுள்ளன, அதற்காக நாம் ஒரு வரிசையை திருப்பித் தர வேண்டும், அங்கு ஒவ்வொரு குறியீட்டுக்கும் நான் முடிவு வரிசையில் arr [i] = sum (எண்கள் [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]

அணுகுமுறை

இந்த சிக்கலில் நாம் ஒரு வரிசையை உருவாக்க வேண்டும், அங்கு குறியீட்டு i இல் உள்ள தனிமத்தின் மதிப்பு கொடுக்கப்பட்ட வரிசையில் 1 முதல் ith குறியீட்டு உறுப்பு வரையிலான உறுப்புகளின் கூட்டுத்தொகைக்கு சமமாக இருக்கும்.
இதற்காக நாம் கொடுக்கப்பட்ட வரிசை அளவுக்கு சமமான அளவிலான வரிசையை உருவாக்கலாம். ஒரு ஃபார் லூப்பில் உள்ள ஒவ்வொரு உறுப்புக்கும் நாம் அசல் வரிசையில் குறியீட்டு 0 இலிருந்து குறியீட்டு i க்கு உறுப்பைச் சேர்க்கலாம். இந்த வழிமுறைக்கான நேர சிக்கலானது O (n ^ 2) ஆக இருக்கும்.

ஒற்றை மட்டுமே பயன்படுத்துவதன் மூலம் இந்த சிக்கலுக்கான நேர சிக்கலை நாம் குறைக்க முடியும் லூப்.
எண்கள் கொடுக்கப்பட்ட வரிசையாகவும், ரெஸ் ஒரு வரிசையாகவும் இருக்கட்டும், அதில் நாம் இயங்கும் தொகையை சேமித்து வைக்கிறோம், பின்னர் ரெஸ் [i] ஐ பின்வருமாறு கணக்கிடலாம்:

res [i] = res [i-1] + nums [i].

எடுத்துக்காட்டு: எண்கள் = [1,2,3,4] கீழே உள்ள படத்தில் காட்டப்பட்டுள்ளது,

1d வரிசை லீட்கோட் தீர்வின் இயங்கும் தொகை

ஆகவே, முன்னொட்டுத் தொகையை மீண்டும் கணக்கிட ஒரு லூப்பை இயக்க வேண்டிய அவசியமில்லை, ஏனென்றால் ரெஸ் வரிசையின் முந்தைய குறியீட்டில் நான் சேமித்து வைத்திருக்கும் குறியீட்டு வரை ஏற்கனவே தொகை உள்ளது.

நடைமுறைப்படுத்தல்

1 டி வரிசை லீட்கோட் தீர்வின் தொகையை இயக்குவதற்கான சி ++ திட்டம்

#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]

1 டி வரிசை லீட்கோட் தீர்வின் தொகையை இயக்குவதற்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (ந): இங்கு n என்பது கொடுக்கப்பட்ட வரிசையின் அளவு. நாம் வளையத்திற்கு ஒற்றை மட்டுமே இயங்குவதால், நேர சிக்கலானது நேர்கோட்டுடன் இருக்கும்.

விண்வெளி சிக்கலானது 

ஓ (ந): இங்கே நாம் n இன் அளவு வரிசையை உருவாக்குகிறோம். எனவே விண்வெளி சிக்கலானது நேர்கோட்டுடன் இருக்கும்.