অনন্য পাথ লেটকোড সমাধান  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ByteDance ফেসবুক গোল্ডম্যান শ্যাস গুগল গণিত মাইক্রোসফট আকাশবাণী Qualtrics বিক্রয় বল Snapchat উবার অথবা VMware ওয়ালমার্ট ল্যাব
আলগোরিদিম বিন্যাস আইনসংগ্রহ ডায়নামিক প্রোগ্রামিং সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions

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

উদাহরণ  

row: 2, column: 2
2

ব্যাখ্যা: কাজটি সম্পন্ন করার জন্য কেবল দুটি উপায় সম্ভব are প্রথমে হয় আপনি ডানে বা নীচে চলে যান। আপনি ডান সরানো হলে আপনি কেবল নীচে স্থানান্তর করতে পারেন। আপনি যদি নীচে সরে গিয়েছিলেন তবে আপনি কেবল নীচের দিকে যেতে পারেন। সুতরাং, শুধুমাত্র 2 টি উপায় সম্ভব।

অনন্য পাথ লেটকোড সমাধান

row: 2, column: 3
3

ব্যাখ্যা: গন্তব্যে পৌঁছানোর 6 টি উপায় রয়েছে। আপনি ডানদিকে চলে গিয়েছেন কিনা তা বিবেচনা করুন, তাহলে সমস্যাটি উপরের উদাহরণে কমে গেছে এবং নীচের ডান কোণে পৌঁছানোর আপনার কাছে 2 টি উপায় রয়েছে। যদি আপনি নীচে নামেন, তবে নীচের ডান কোণে পৌঁছানোর আপনার কাছে কেবল একটি একক উপায় রয়েছে। সুতরাং, শেষের দিকে পৌঁছানোর মোট উপায়ের সংখ্যা 3।

ইউনিক পাথ লেটকোড সমাধানের জন্য ব্রুট ফোর্স পদ্ধতির  

সমস্যা ইউনিক পাথস লেটকোড সমাধান পুনরাবৃত্তভাবে সমাধান করা যেতে পারে। ঠিক যেমনটি আমরা দ্বিতীয় উদাহরণটিতে করেছি, যেখানে আমরা প্রদত্ত সমস্যাটিকে 2 টি সাব-প্রবলেমে হ্রাস করেছি। একই সমাধান আমরা এই সমাধানে কি করব। একবার, আমরা ডানদিকে চলে যাই, তারপরে সমস্যাটি হ্রাস পেয়ে সাব-প্রবলেম (সারি, কলাম -১) হয়। আমরা যদি নীচের দিকে চলে যাই তবে সমস্যাটি হ্রাস পেয়েছে (সারি -১, কলাম)। আমরা সহজেই এই পুনরাবৃত্ত সমাধান সমাধান করতে পারেন। তবে এটি সময়ের সীমা অতিক্রম করবে কারণ সমাধানটি অত্যন্ত অদক্ষ।

আরো দেখুন
কনেকেটনেশন লেটকোড সমাধানের মাধ্যমে অ্যারে গঠন পরীক্ষা করুন

ব্রুট ফোর্স পদ্ধতির জন্য কোড

সি ++ কোড

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

int uniquePaths(int m, int n) {
    if(n==1 || m==1)return 1;
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

জাভা কোড

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

class Solution {
    public static int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (2 ^ সর্বোচ্চ (মি, এন)), কারণ পুনরাবৃত্তি ফাংশন কারণে ঘনঘন সময় জটিলতা।

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

ও (সর্বোচ্চ (মি, এন), সংকলক স্ট্যাক দ্বারা ব্যবহৃত স্থান। এটি পুনরাবৃত্ত হওয়া গাছের উচ্চতার উপর নির্ভর করে।

গতিশীল প্রোগ্রামিং পদ্ধতির  

পুনরাবৃত্তাকারী সমাধানের অধীনে উপরে বর্ণিত পদ্ধতিটি সহজে মুখস্ত করা যায়। যেহেতু রিকার্সিভ ফাংশন দুটি ভেরিয়েবলের উপর নির্ভরশীল যা সারি এবং কলাম হয়। এইভাবে আমরা 2D ডিপি তৈরি করি বিন্যাস এবং প্রতিটি রাজ্যের ফলাফল সংরক্ষণ করুন। এটি সময়ের জটিলতা নাটকীয়ভাবে উন্নত করবে কারণ আমরা একই সমস্যার সমাধান করছি না।

ইউনিক পাথ লেটকোড সমাধানের জন্য ডায়নামিক প্রোগ্রামিং কোড

সি ++ কোড

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

vector<vector<int>> dp;
int uniquePathsUtil(int m, int n) {
    if(m == 1 || n == 1) return 1;
    if(dp[m][n] != -1)
        return dp[m][n];
    return dp[m][n] = uniquePathsUtil(m-1, n) + uniquePathsUtil(m, n-1);
}

int uniquePaths(int m, int n) {
    dp.clear();
    dp.assign(m+1, vector<int>(n+1, -1));
    return uniquePathsUtil(m, n);
}

int main(){
    cout<<uniquePaths(2, 2);
}
2

জাভা কোড

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

class Solution {
    private static int uniquePathsUtil(int m, int n, int[][] dp) {
        if(m == 1 || n == 1) return 1;
        if(dp[m][n] != 0)
            return dp[m][n];
        return dp[m][n] = uniquePathsUtil(m-1, n, dp) + uniquePathsUtil(m, n-1, dp);
    }

    private static int uniquePaths(int m, int n) {
        int dp[][] = new int[m+1][n+1];
        return uniquePathsUtil(m, n, dp);
    }
    
    public static void main(String[] args){
    	System.out.print(uniquePaths(2,2));
    }
}
2

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * এম), যেখানে এন, এম সারি সংখ্যা এবং গ্রিডে কলামগুলি উপস্থাপন করতে ব্যবহৃত হয়। যেহেতু মোট এন * এম রাষ্ট্র রয়েছে তাই সময় জটিলতা ও (এন * এম )ও হয়।

আরো দেখুন
সমস্ত পয়েন্ট লেটকোড সলিউশন দেখার জন্য সর্বনিম্ন সময়

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

ও (এন * এম), প্রয়োজনীয় স্থানটি 2D ডিপি টেবিল তৈরির জন্য। স্পেস জটিলতা ডিপি পদ্ধতির জন্য বহুপদী।