House Robber Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Cisco microsoft Kahin
alqoritmlər kodlaşdırma Dinamik proqramlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 126

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bu problemdə bir küçədə evlər var və Ev soyğunçusu bu evləri qarət etmək məcburiyyətindədir. Ancaq problem ondadır ki, ardıcıl olaraq bir-birinə bitişik olan birdən çox evi talaya bilməz. Hər evin pul miqdarını təmsil edən mənfi olmayan tam ədədlərin siyahısı verildiyi üçün ala biləcəyi maksimum pulu tapmaq məcburiyyətindəyik.

misal

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

Explanation:Ev qulduru

Ev 1 (pul = 1) və sonra ev 3 (pul = 3) soyulur.
Qara biləcəyiniz ümumi məbləğ = 1 + 3 = 4.

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

Explanation:

Soyğun evi 1 (pul = 2), soyğun evi 3 (pul = 9) və sonra 5-ci (pul = 1).
Qara biləcəyiniz ümumi məbləğ = 2 + 9 + 1 = 12.

Yanaşma

Bu problem acgöz yanaşma ilə həll edilə bilməz.
Bir nümunə götürək:
saylar = [1,7,9,5,1,3,4]

Dizidəki maksimum elementə (yəni 9) gedərsək, bitişik cəmini itirərdik (yəni. 7 + 5). Və əldə edə biləcəyimiz ən yaxşı cəmi 15-dir.

Cüt və ya tək mövqe elementlərinə gəlsək, cüt cəmi = 15 (7 + 5 + 3) və tək cəmi = 15 (1 + 9 + 1 + 4) olur.

Bu nümunə üçün optimal cavab [7 + 5 + 4] = 12 olacaqdır.

Bu səbəbdən bu tip problemi həll etmək üçün bütün seçimləri təkrarən axtarmalı və onlardan maksimumunu seçməliyik. Bunu bildirək:

f (n) = Birinci evdən n-indeksli evə qədər soyacağınız ən böyük məbləğ.
Ai = indeks evindəki pul miqdarı.

Hər evdə onu soymaq və ya tərk etmək seçimimiz var.
hal 1 - son evi seçsək:
sonra (n-1) ev seçə bilmərik, buna görə f (n) = An + f (n-2)
iş 2 - son evdən çıxsaq:
o zaman (n-1) evə qədər maksimum qazancla qalacağıq, buna görə f (n) = f (n-1)

Əsas hallara baxaq.
n = 0, açıq şəkildə f (0) = A0.
n = 1, sonra f (1) = max (A0, A1).

Beləliklə, formulu aşağıdakı kimi ümumiləşdirə bilərik:
f (n) = max (An + f (n-2), f (n-1))

Bu, sadə rekursiya ilə həyata keçirə biləcəyimiz rekursiv bir düsturdur, lakin burada zaman çətinliyi O (2 ^ n) olacaqdır. Buna görə istifadə edəcəyik dinamik proqramlaşdırma aralıq nəticələrə yaxınlaşın və bir massivdə saxlayın.
Hesabladıqdan sonra massivdə nth (son) indeksdə saxlanan dəyəri qaytaracağıq.

Həyata keçirilməsi

House Robber Leetcode Həlli üçün C ++ Proqramı

#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 Solution üçün Java Proqramı

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 Solution üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n): 1-ci evdən n-ci evə tək bir döngədə təkrarlanırıq, burada n ümumi evlərin sayıdır.

Kosmik Mürəkkəblik 

O (n): ara nəticəni saxlamaq üçün n ölçülü bir sıra istifadə etdik.

Crack Sistemi Dizayn Müsahibələri
Translate »