በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Swiggy
ሰልፍ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ የቁጥሮች ቅደም ተከተል ተሰጥቶናል (አዎንታዊ አሉታዊ ወይም ዜሮ ሊሆን ይችላል) ፡፡ ከእኛ ጋር አዎንታዊ ኢንቲጀር መውሰድ አለብን ከዚያ በኋላ የዚህን ሁሉ ቁጥሮች መጨመር እንጀምራለን ደርድር ከእሱ ጋር ከግራ ወደ ቀኝ
እኛ በጅማሬው መውሰድ ያለብንን ዝቅተኛውን አዎንታዊ ኢንቲጀር እንፈልጋለን ፣ ስለሆነም በማንኛውም ጊዜ የአሁኑ ድምራችን ሁል ጊዜ አዎንታዊ ሆኖ እንዲቆይ ፡፡

ለምሳሌ

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

ማብራሪያ:

በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ
የመነሻ ዋጋ = 5 ን ከመረጥን ሁሉም መካከለኛ ድምር አዎንታዊ እንደሆንን እዚህ ማየት እንችላለን ፡፡ እኛ ደግሞ የ StartValue = 4 ን ማረጋገጥ እንችላለን ፣ ይህም ትክክለኛ መፍትሔ አይደለም።

nums = [1,2]
1

ማብራሪያ:

ዝቅተኛው የመነሻ ዋጋ አዎንታዊ መሆን አለበት ፡፡

ቀረበ

ድርድር አለን እንበል ፣ ቁጥሮች = [-3,2, -3,4,2]
የመጀመሪያ ዋጋን እንደ 2 ከመረጥን እና አባሎችን ከግራ ወደ ቀኝ ማከል ከቀጠልን

በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ

ከላይ በምሳሌው ላይ ፣ የመነሻ ዋጋን እንደ 2. መርጠናል ፣ ድምራችን በእያንዳንዱ ጊዜ አዎንታዊ ሆኖ አይቆይም ፣ ስለሆነም አንዳንድ ትላልቅ ንጥረ ነገሮችን እንፈልጋለን።

የመጀመሪያ ቫል 5 ይሁን ፡፡
በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ
አሁን ፣ የመነሻ እሴት ከዚያ 5 ከሆነ ፣ የአሁኑን ድምር ሁሌም አዎንታዊ ሆኖ በመቆየቱ በእውነቱ በመላው ድርድር መጓዝ እንደምንችል በግልፅ ማየት እንችላለን ፡፡ 5 ይህን ማድረግ ትንሹ ኢንቲጀር ከሆነ መልሱ ሊሆን ይችላል ፡፡
መጀመሪያ ላይ ከእኛ ጋር ቫል = 0 ከመረጥን ስለ አንድ ሁኔታ እናስብ ፡፡

በደረጃ አዎንታዊ ውጤትን ለማግኘት አነስተኛ እሴት ድምር Leetcode መፍትሔ

አሁን ፣ እኛ በጣም አሉታዊ የአሁኑን ድምር እሴት (-4 በአሁን ምሳሌ) ካሸነፍን ከዚያ ያለምንም ችግር ድርድርን በግልጽ ማለፍ እንችላለን ማለት እንችላለን?
ልክ ፣ ከላይ በምሳሌው ላይ ፣ በጣም አሉታዊ እሴት -4 ነው ፣ እሱን ለማሸነፍ 1 ማድረግ አለብን (ምክንያቱም ፣ በጣም አነስተኛ አዎንታዊ ኢንቲጀር ያስፈልጋል)።

ስለዚህ በጣም አሉታዊ ሁኔታን ለማለፍ ዋጋ 1 - (- 4) = 5 እንፈልጋለን።
እኛ ደግሞ 5 መፍትሄውን ሊያልፍ እንደሚችል ተመልክተናል ፡፡

እና ምንም አሉታዊ የአሁኑ ድምር ከሌለ እኛ አዎንታዊ የውስጣዊ መፍትሔ ስለምንፈልግ 1 ብቻ እናወጣለን ፡፡

ስለዚህ የእኛ ስልተ ቀመር ይሆናል

1. በጣም አሉታዊ መፍትሄ መፈለግ አለብን ፣ ስለሆነም መላውን ድርድር እናቋርጣለን።
2. በእያንዳንዱ ድግግሞሽ ውስጥ መዞር የአሁኑ ድምር አነስተኛ መሆኑን ወይም አለመሆኑን እንፈትሻለን እናም የእኛን አነስተኛ ዋጋ በዚህ መሠረት እናዘምነዋለን ፡፡
3. በመጨረሻም ይህንን በጣም አሉታዊ እሴት ወደ 1 ለማድረግ ፣ ከ 1. ብቻ እናውለዋለን (ለምሳሌ ደቂቃ = -4 ፣ val = 1 - (- 4) = 5) ፡፡

አፈጻጸም

የ C ++ መርሃግብር ቀናውን ደረጃ በደረጃ ለማግኘት ድምር Leetcode መፍትሄ ለማግኘት አነስተኛ እሴት

#include <iostream>
#include<vector>
using namespace std;

int minStartValue(vector<int>& nums) {
    
    int min=0,sum=0;
    for (int i = 0; i < nums.size(); i++){
        sum+=nums[i];
        min=min<sum?min:sum;
    }
    
    return 1-min;
}

int main() {
    vector<int> nums{-3,2,-3,4,2}; 
    cout<<minStartValue(nums)<<endl;	
  return 0;
}
5

የጃቫ ፕሮግራም በአዎንታዊ ደረጃ አዎንታዊ ውጤት ለማግኘት ድምር Leetcode Solution

import java.util.*;

class Rextester{
    
    public static int minStartValue(int[] nums) 
    {
        Integer min=0,sum=0;
        for(int i:nums){
            sum+=i;
            min=Math.min(min,sum);
        }
        return 1-min;
    }
    
    public static void main(String args[])
    {
       	int[]nums={-3,2,-3,4,2};
        int ans=minStartValue(nums);
        System.out.println(ans);
    }
}
5

አወንታዊ ደረጃ በደረጃ አዎንታዊ ድምርን ለማግኘት ለዝቅተኛ እሴት ትንታኔ Leetcode Solution

የጊዜ ውስብስብነት

ኦ (n): ምክንያቱም ፣ የተሰጠንን ድርድር በተዘዋዋሪ እያለፍን ነው ፣ ስለሆነም የዘመናችን ውስብስብነት O (n) ይሆናል።

የቦታ ውስብስብነት 

ኦ (1) ምንም ተጨማሪ ቦታ አልተጠቀምንም ፣ ስለሆነም የቦታ ውስብስብነታችን ቋሚ ይሆናል።