House Robber Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 아마존 Apple 시스코 Microsoft 신탁
알고리즘 코딩 동적 프로그래밍 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 124

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

문제 정책

이 문제에서는 거리에 집이 있고 집 강도가이 집을 털어 야합니다. 그러나 문제는 그가 연속적으로 하나 이상의 집, 즉 서로 인접한 집을 털 수 없다는 것입니다. 각 집의 금액을 나타내는 음이 아닌 정수 목록이 주어지면 그가받을 수있는 최대 금액을 알아 내야합니다.

nums = [1,2,3,1]
4

설명 :집 강도

집 1 (돈 = 1)을 약탈 한 다음 집 3 (돈 = 3)을 약탈합니다.
약탈 할 수있는 총 금액 = 1 + 3 = 4.

nums = [2,7,9,3,1]
12

설명 :

롭 하우스 1 (돈 = 2), 롭 하우스 3 (돈 = 9), 5 번째 (돈 = 1).
약탈 할 수있는 총 금액 = 2 + 9 + 1 = 12.

접근

이 문제는 탐욕스러운 접근으로 해결할 수 없습니다.
예를 들어 보겠습니다.
숫자 = [1,7,9,5,1,3,4]

배열의 최대 요소 (예 : 9)로 이동하면 인접한 합계 (예 : 7 + 5)를 잃게됩니다. 그리고 우리가 가질 수있는 최선은 총합으로 15입니다.

짝수 또는 홀수 위치 요소로 이동하면 짝수 합계 = 15 (7 + 5 + 3) 및 홀수 합계 = 15 (1 + 9 + 1 + 4)입니다.

이 예에 대한 최적의 답은 [7 + 5 + 4] = 12입니다.

따라서 이러한 유형의 문제를 해결하려면 모든 선택을 재귀 적으로 검색하고 최대를 선택해야합니다. 다음을 표시하겠습니다.

f (n) = 첫 번째 집에서 n 번째 색인 된 집으로 훔칠 수있는 최대 금액.
Ai = i 번째 인덱스 하우스의 금액.

각 집에서 우리는 그것을 강탈하거나 떠날 수 있습니다.
사례 1 – 마지막 집을 선택하면 :
그런 다음 (n-1) 번째 집을 선택할 수 없으므로 f (n) = An + f (n-2)
사례 2 – 마지막 집을 떠나는 경우 :
그런 다음 (n-1) 번째 집까지 최대 이익을 유지하므로 f (n) = f (n-1)

기본 사례를 살펴 보겠습니다.
n = 0, 분명히 f (0) = A0.
n = 1이면 f (1) = max (A0, A1).

따라서 공식을 다음과 같이 요약 할 수 있습니다.
f (n) = 최대 (An + f (n-2), f (n-1))

이것은 단순 재귀를 통해 구현할 수있는 재귀 공식이지만 여기서 시간 복잡도는 O (2 ^ n)입니다. 따라서 우리는 동적 프로그래밍 중간 결과에 접근하고 배열에 저장합니다.
계산 후 배열의 n 번째 (마지막) 인덱스에 저장된 값을 반환합니다.

실시

House Robber Leetcode 솔루션을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums)
{
    int n=nums.size();

    if(n==0) return 0;
    if(n==1) return nums[0];

    int a[n];

    a[0]=nums[0];
    a[1]=max(nums[0],nums[1]);

    for(int i=2;i<n;i++)
    a[i]=max(nums[i]+a[i-2], a[i-1]);

    return a[n-1];

}
int main() 
{
    vector<int> arr={1,2,3,1};
    
    cout<<rob(arr)<<endl;
    
  return 0; 
}
4

House Robber Leetcode 솔루션을위한 Java 프로그램

import java.util.*;
import java.lang.*;

class HouseRobber
{  
    public static int rob(int[] nums) {
        
        int n=nums.length;
        
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        int a[]=new int[n];
       
        a[0]=nums[0];
        a[1]=Math.max(nums[0],nums[1]);
        
        for(int i=2;i<n;i++)
            a[i]=Math.max(nums[i]+a[i-2], a[i-1]);
        
        return a[n-1];
    }
    
    
    public static void main(String args[])
    {
        int arr[]={1,2,3,1};
        System.out.println(rob(arr));
    }
}
4

House Robber Leetcode 솔루션의 복잡성 분석

시간 복잡성

의 위에) : 우리는 단일 루프에서 1 집에서 n 집까지 반복합니다. 여기서 n은 총 주택 수입니다.

공간 복잡성 

의 위에) : 중간 결과를 저장하기 위해 크기 n의 배열을 사용했습니다.

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