목표 합계

난이도 중급
자주 묻는 질문 아마존 블룸버그 게시물에서 Facebook
깊이 우선 검색 동적 프로그래밍조회수 101

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

“Target Sum”은 제가 오늘 가지고있는 모든 DPHolics의 특별한 문제입니다. 나머지 사랑스러운 독자들을 버릴 것이라고 걱정할 필요가 없습니다. 우리 모두는 가방을 부수 지 않고 자루에 넣을 수있는 최대 항목 수를 찾으려고 노력하는 고전적인 KnapSack 문제를 겪었습니다.

따라서 더 이상 지체하지 않습니다. 문제에 대해 알아 봅시다. 오늘 나와 함께 사용하는 문제가 있습니다.

문제 정책

주어진 : 정렬 우리가 달성해야 할 요소와 목표 합계로

정황:

  • 우리는 서로 요소를 더하거나 뺄 수 있습니다.
  • 목표를 달성하기 위해 기존 합계와 함께 + 또는 –를 사용할 수 있습니다.

출력은 어떻게되어야합니까?

목표에 도달 할 수있는 방법의 수

예제 배열 : [1,1,1,1,1]

Target_sum : 3

접근 방식 -1

목표 합계를 찾기위한 일반 Jane 재귀

이 접근 방식에는 가능한 모든 조합을 시도한 다음 target_sum으로 이어지는 조합을 선정하는 것이 포함됩니다.

  • 여기서 재귀 함수는 계산하다
  • 가능한 조합을 추적하기 위해 전역 변수 수를 유지합니다.
  • 우리가 새로운 직책을 가질 때마다. 우리는 다음을 확인합니다.
    • pos <= 배열의 길이
      • 지금까지의 합계가 목표와 같으면
        • 증가 카운트
      • 합계가 목표와 같지 않은 경우
        • 돌아 가기 (세그멘테이션 오류를 원하지 않습니까?)
    • 우리가 다음 위치를 계산할 때마다
      • 합계에 다음 요소를 추가합니다.
        • 따라서 "+"를 사용하여
      • 합계에서 다음 요소를 뺍니다.
  • 따라서 "-"사용

이제 프로세스에 대한 개요를 얻었으므로 코드를 작성하겠습니다.

목표 합계에 대한 Java 코드

class Solution
{
    int count=0;
    public void calculate(int[]nums,int pos,int sum,int S)
    {
        if(pos==nums.length)
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
    public int findTargetSumWays(int[] nums, int S) 
    {
        calculate(nums,0,0,S);
        return count;
    }
}

목표 합계에 대한 C ++ 코드

class Solution 
{
public:
    int count=0;
public:
    void calculate(vector<int>& nums,int pos,int sum,int S)
    {
        if(pos==nums.size())
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
public:
    int findTargetSumWays(vector<int>& nums, int S)
    {
       calculate(nums,0,0,S);
       return count;
    }
};

복잡성 분석

시간 복잡도 = O (2 ^ n)

왜? = 재귀 트리의 크기는 (2 ^ n) x (n)입니다.

접근 방식 -2

목표 합계를 찾기위한 동적 프로그래밍

  • 배열 Dp 만들기
  • Dp [i] [j] = I 요소로 합계에 도달하는 방법의 수
  • 배열을 채울 때 두 가지를 확인합니다.
    • 요소 + 이전 요소의 합계 <2 * sum
      • 다음 요소를 추가 할 수있을만큼 안전합니다.
      • 따라서 Dp [i] [j] = Dp [i-1] [j] + Dp [i-1] [j + nums [i-1]]
      • 따라서 우리는 "+"를 포함하는 조합을 얻습니다.
    • 이전 요소의 요소 합계가> = 0 인 경우
      • 다음 요소를 뺄 수있을만큼 안전합니다.
      • 따라서 Dp [i] [j] = Dp [i-1] [j] -Dp [i-1] [j + nums [i-1]] Target_sum 찾기
      • 이제 "-"가 포함 된 조합입니다.
  • dp [sum + Target] 반환
    • 이유는 무엇입니까?
    • 범위는 -sum에서 + sum까지 다양합니다.

해당 사례에 대한 다이어그램으로 프로세스 설명

예제 배열의 목표 합계 찾기
주황색, 빨간색 및 녹색으로 강조 표시된 값이있는 주어진 문제에 대한 DP 배열

이미지 키

  • Green-0 값
  • 주황색 -XNUMX이 아닌 값
  • 빨간 대답

코딩 부분을 살펴 보겠습니다.

목표 합계에 대한 Java 코드

class Solution 
{
    public int findTargetSumWays(int[] nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.length;i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    int dp[][]=new int[nums.length+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.length;i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.length][sum+S];
    }
}

목표 합계에 대한 C ++ 코드

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    vector<vector<int>> dp(nums.size() + 1, vector<int>(sum*2 + 1, 0));
    //int dp[nums.size()+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.size();i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.size()][sum+S];    
    }
};

복잡성 분석

시간 복잡도 = O (n * sum)

공간 복잡성 = O (n ^ 2)

참조

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