Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək üçün minimum dəyər

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Swiggy
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 45

Problem bəyanat

Bu problemdə bizə bir sıra ardıcıllığı verilir (müsbət mənfi və ya sıfır ola bilər). Özümüzlə müsbət bir tam ədədi götürməliyik və bundan sonra bunun bütün tam ədədlərini əlavə etməyə başlayacağıq array onunla soldan sağa.
Başlanğıcda götürməli olduğumuz minimum müsbət ədədi istəyirik ki, istənilən vaxt cari məbləğimiz həmişə pozitiv qalsın.

misal

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

Explanation:

Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək üçün minimum dəyər
Burada görə bilərik ki, startValue = 5 seçsək, bütün aralıq cəmi müsbət olar. StartValue = 4-i də yoxlaya bilərik, bu düzgün həll deyil.

nums = [1,2]
1

Explanation:

Minimum başlanğıc dəyəri müsbət olmalıdır.

Yanaşma

Tutaq ki, bizdə bir sıra var, nums = [-3,2, -3,4,2]
İndi başlanğıc dəyəri 2 olaraq seçsək və elementləri soldan sağa əlavə etməyə davam etsək, onda:

Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək üçün minimum dəyər

Yuxarıdakı nümunədə ilkin dəyəri 2 olaraq seçmişik. Cəmimiz hər dəfə müsbət qalmayacaq, buna görə daha böyük bir elementə ehtiyacımız var.

İlk val 5 olsun.
Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək üçün minimum dəyər
İndi açıq şəkildə görə bilərik ki, başlanğıc dəyəri 5-dirsə, cari cəmi həmişə pozitiv saxlayaraq mütləq sıra boyunca səyahət edə bilərik. 5 bunu ən kiçik tam olarsa cavab ola bilər.
Başlanğıcda yanımızda Val = 0 seçsək bir vəziyyət düşünək.

Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək üçün minimum dəyər

İndi demək olar ki, ən mənfi cari cəmin dəyərini aşsaq (cari nümunədə -4), onda serialı problemsiz bir şəkildə keçə bilərik.
Yuxarıdakı nümunədə ən çox mənfi dəyər -4 olduğu kimi, onu aradan qaldırmaq üçün onu 1 etməliyik (çünki ən kiçik müsbət tam ədədə ehtiyac var).

Beləliklə, 1 - (- 4) = 5 dəyərinin ən mənfi vəziyyəti keçməsini istəyirik.
5-in həll yolu keçə biləcəyini də gördük.

Və mənfi cari məbləğ yoxdursa, yalnız 1-i çıxacağıq, çünki müsbət inteqrasiya həllini istəyirik.

Beləliklə, alqoritmimiz belə olacaq:

1. Ən çox mənfi həlli axtarmalıyıq, buna görə bütün massivi keçəcəyik.
2. hər təkrarlanmasında loop cari məbləğin minimum olub olmadığını yoxlayacağıq və min dəyərimizi buna uyğun olaraq yeniləyəcəyik.
3. Nəhayət, bu ən mənfi dəyəri 1-ə çatdırmaq üçün onu yalnız 1-dən çıxardacağıq (məsələn min = -4, val = 1 - (- 4) = 5).

Həyata keçirilməsi

C ++ Proqramı Minimum Dəyər Adım Cəm Leetcode Həlli ilə Müsbət Adım əldə etmək

#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

Minimum Dəyər üçün Java Proqramı Adım Cəmi Leetcode Həlli ilə Pozitiv Adım əldə etmək

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

Addım-addım cəm ​​Leetcode həllində müsbət addım əldə etmək üçün minimum dəyər üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n): Çünki verilmiş massivi xətti keçirik, beləliklə zaman mürəkkəbliyimiz O (n) olacaqdır.

Kosmik Mürəkkəblik 

O (1): Əlavə yer istifadə etməmişik, beləliklə kosmik mürəkkəbliyimiz sabit olacaqdır.

Şərh yaz

Translate »
1