হাউস ডাকাত লেটকোড সলিউশন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আপেল সিসকো মাইক্রোসফট আকাশবাণী
আলগোরিদিম আইনসংগ্রহ ডায়নামিক প্রোগ্রামিং সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions

সমস্যা বিবৃতি  

এই সমস্যায় একটি রাস্তায় ঘর রয়েছে এবং হাউস ডাকাতদের এই বাড়িগুলি ছিনিয়ে নিতে হবে। তবে সমস্যাটি হ'ল তিনি একের অধিক ঘর ডেকে আনতে পারবেন না যা একে অপরের সাথে সংলগ্ন। প্রতিটি বাড়ির অর্থের পরিমাণের প্রতিনিধিত্বকারী অ-নেতিবাচক পূর্ণসংখ্যার একটি তালিকা প্রদত্ত, আমাদের সর্বাধিক পরিমাণ অর্থ কী পরিমাণ তা পেতে হবে তা খুঁজে বের করতে হবে।

উদাহরণ

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) = সবচেয়ে বড় পরিমাণ যা আপনি প্রথম বাড়ি থেকে নবম তৃতীয় সূচী ঘরে নিয়ে যেতে পারেন।
আইআই = আইথ ইনডেক্স বাড়িতে অর্থের পরিমাণ।

আরো দেখুন
বন্যা ভরাট লেটকোড

প্রতিটি বাড়িতে আমাদের এটি ছিনতাই বা রেখে দেওয়ার পছন্দ থাকে।
কেস 1 - যদি আমরা শেষ বাড়িটি বেছে নিই:
তারপরে, আমরা বাছাই করতে পারি না (এন -1) তম বাড়ি, সুতরাং f (n) = আন + এফ (এন -2)
কেস 2 - যদি আমরা শেষ বাড়ি ছেড়ে যাই:
তারপরে, আমরা (এন -1) তম বাড়ি পর্যন্ত সর্বাধিক মুনাফা নিয়ে থাকব, সুতরাং চ (এন) = চ (এন -1)

আসুন বেস কেসগুলি দেখি।
n = 0, পরিষ্কারভাবে f (0) = A0।
n = 1, তারপরে f (1) = সর্বোচ্চ (A0, A1)।

সুতরাং আমরা নীচের হিসাবে সূত্র সংক্ষিপ্ত করতে পারেন:
f (n) = সর্বাধিক (আন + চ (এন -2), চ (এন -1)

এটি একটি পুনরাবৃত্তির সূত্র যা আমরা সাধারণ পুনরাবৃত্তির মাধ্যমে প্রয়োগ করতে পারি তবে এখানে সময় জটিলতা হবে ও (2 ^ n)। সুতরাং আমরা ব্যবহার করব গতিশীল প্রোগ্রামিং মধ্যবর্তী ফলাফলগুলিকে একটি অ্যারেতে উপস্থিত করুন এবং সংরক্ষণ করুন।
গণনার পরে আমরা অ্যারেতে নবম (শেষ) সূচকে সঞ্চিত মানটি ফিরিয়ে দেব।

বাস্তবায়ন  

হাউস রবার লেটকোড সমাধানের জন্য সি ++ প্রোগ্রাম

#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

হাউস ডাকাত লেটকোড সমাধানের জন্য জাভা প্রোগ্রাম

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

হাউস ডাকাত লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু) : আমরা এক লুপে 1 ম ঘর থেকে নবম ঘরে পুনরাবৃত্তি করছি, যেখানে n মোট বাড়ির সংখ্যা।

স্পেস জটিলতা ity 

চালু) : আমরা মধ্যবর্তী ফলাফল সঞ্চয় করতে আকারের একটি অ্যারের ব্যবহার করেছি।