단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 Swiggy
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 109

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이 문제에서는 일련의 숫자가 주어집니다 (양수 또는 XNUMX 일 수 있음). 우리는 양의 정수를 가져와야합니다. 그리고이 모든 정수를 더하기 시작할 것입니다. 정렬 왼쪽에서 오른쪽으로.
우리는 처음에 가져와야 할 최소 양의 정수를 원하므로 언제든지 현재 합계가 항상 양수로 유지됩니다.

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

설명 :

단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션
여기서 startValue = 5를 선택하면 모든 중간 합계가 양수임을 알 수 있습니다. 올바른 솔루션이 아닌 startValue = 4도 확인할 수 있습니다.

nums = [1,2]
1

설명 :

최소 시작 값은 양수 여야합니다.

접근

배열이 있다고 가정합니다. nums = [-3,2, -3,4,2]
이제 초기 값을 2로 선택하고 요소를 왼쪽에서 오른쪽으로 계속 추가하면 다음과 같습니다.

단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션

위의 예에서는 초기 값을 2로 선택했습니다. 합계는 매번 양수로 유지되지 않으므로 더 큰 요소가 필요합니다.

초기 값을 5로 둡니다.
단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션
이제 시작 값이 5이면 현재 합계를 항상 양수로 유지하면서 배열 전체를 이동할 수 있음을 분명히 알 수 있습니다. 5가 가장 작은 정수라면 답이 될 수 있습니다.
처음에 우리와 함께 val = 0을 선택한다면 상황을 생각해 봅시다.

단계적으로 긍정적 인 단계를 얻기위한 최소값 합계 Leetcode 솔루션

이제 가장 음의 전류 합 (현재 예에서는 -4)의 값을 극복하면 문제없이 배열을 명확하게 전달할 수 있다고 말할 수 있습니다.
위의 예에서 가장 음의 값은 -4이고,이를 극복하려면 1로 만들어야합니다 (가장 작은 양의 정수가 필요하기 때문).

따라서 우리는 가장 부정적인 상황을 통과하기 위해 1-(-4) = 5 값을 원합니다.
우리는 또한 5가 해결책을 통과 할 수 있음을 보았습니다.

음의 전류 합이 없으면 양의 적분 솔루션을 원하기 때문에 1을 출력합니다.

따라서 알고리즘은 다음과 같습니다.

1. 대부분의 네거티브 솔루션을 찾아야하므로 전체 어레이를 순회합니다.
2. 각 반복에서 고리 현재 합계가 최소인지 아닌지 확인하고 그에 따라 최소값을 업데이트합니다.
3. 마지막으로 가장 음의 값을 1로 만들기 위해 1에서 빼면됩니다 (예 : min = -4, val = 1-(-4) = 5).

실시

최소값을위한 C ++ 프로그램을 통해 단계적으로 긍정적 인 단계를 얻을 수 있습니다.

#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

단계적으로 긍정적 인 단계를 얻기위한 최소값을위한 Java 프로그램 Sum Leetcode 솔루션

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

단계적 합리 코드 솔루션을 통해 긍정적 인 단계를 얻기위한 최소값에 대한 복잡성 분석

시간 복잡성

의 위에): 왜냐하면 우리는 주어진 배열을 선형으로 순회하고 있기 때문에 우리의 시간 복잡도는 O (n)이 될 것입니다.

공간 복잡성 

O (1) : 추가 공간을 사용하지 않았으므로 공간 복잡성은 일정합니다.

균열 시스템 설계 인터뷰
Translate »
1