უნიკალური ბილიკები Leetcode Solution  


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Amazon Apple Bloomberg ByteDance Facebook Goldman Sachs Google მათემატიკის სამუშაოები microsoft Oracle Qualtrics Salesforce Snapchat Uber VMware Walmart Labs
ალგორითმები Array კოდირება დინამიური პროგრამირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions

პრობლემა უნიკალური ბილიკები Leetcode Solution აღნიშნავს, რომ თქვენ გეძლევათ ორი მთელი რიცხვი, რომლებიც წარმოადგენს ქსელის ზომას. ზომის გამოყენება ქსელის, ბადის სიგრძე და სიგანე. ჩვენ უნდა ვიპოვოთ უნიკალური ბილიკების რაოდენობა ქსელის ზედა მარცხენა კუთხიდან ქვედა მარჯვენა კუთხეში. მოძრაობის მიმართულებით არსებობს ერთმანეთის შეზღუდვა, დროის ნებისმიერ მომენტში, ის შეიძლება გადაადგილდეს მხოლოდ ქვევით ან სწორი მიმართულებით.

მაგალითი  

row: 2, column: 2
2

განმარტება: დავალების შესასრულებლად მხოლოდ ორი გზაა შესაძლებელი. ჯერ ან მარჯვნივ გადახვიდეთ ან ქვემოთ. თუ სწორად გადაადგილდით, მხოლოდ ქვემოთ შეგიძლიათ გადახვიდეთ. თუ ქვევით გადახვედით, მაშინ მხოლოდ ქვემო მიმართულებით შეგიძლიათ გადაადგილება. ასე რომ, მხოლოდ 2 გზაა შესაძლებელი.

უნიკალური ბილიკები Leetcode SolutionPin

row: 2, column: 3
3

განმარტება: დანიშნულების ადგილზე მიღწევის 6 გზა არსებობს. გაითვალისწინეთ, თუ მარჯვნივ გადაადგილდით, მაშინ პრობლემა შემცირდა ზემოთ მოცემულ მაგალითზე და თქვენ გაქვთ მარჯვენა მხარეს ქვედა კუთხეში მისასვლელი 2 გზა. თუ ქვემოთ გექნებოდათ, მაშინ მხოლოდ ერთი გზა გაქვთ ქვედა მარჯვენა კუთხეში მისასვლელად. ამრიგად, ბოლომდე მიღწევის გზების საერთო რაოდენობაა 3.

იხილეთ ასევე
შეამოწმეთ მასივის ფორმირება გაერთიანების Leetcode Solution- ის საშუალებით

უხეში ძალის მიდგომა უნიკალური ბილიკებისთვის Leetcode Solution  

პრობლემა უნიკალური ბილიკები Leetcode Solution შეიძლება გადაწყდეს რეკურსიულად. ისევე, როგორც მეორე მაგალითში, სადაც მოცემული პრობლემა 2 ქვეპროგრამად დავამცირეთ. იგივე არის ის, რასაც ჩვენ გავაკეთებთ ამ გადაწყვეტაში. ერთხელ, ჩვენ მარჯვნივ გადავდივართ, შემდეგ პრობლემა ქვეპრობლემამდე მიდის (მწკრივი, სვეტი -1). თუ ქვემო მიმართულებით გადავინაცვლეთ, პრობლემა შემცირდება (მწკრივი -1, სვეტი). ამ რეკურსიული ამოხსნის კოდირება მარტივად შეგვიძლია. მაგრამ ეს გადააჭარბებს ვადას, რადგან გამოსავალი ძალიან არაეფექტურია.

უხეში ძალის მიდგომის კოდი

C ++ კოდი

#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

სირთულის ანალიზი

დროის სირთულე

O (2 ^ მაქს (მ, ნ)), რეკურსიული ფუნქციის გამო ექსპონენციალური დროის სირთულის გამო.

სივრცის სირთულე

O (მაქსიმალური (მ, ნ), სივრცე, რომელსაც იყენებს შემდგენელი სტეკი. ეს დამოკიდებულია რეკურსიული ხის სიმაღლეზე.

დინამიური პროგრამირების მიდგომა  

მიდგომა, რომელიც ზემოთ იყო ახსნილი რეკურსიული ამოხსნის ქვეშ, ადვილად დაიმახსოვრებს. რადგან რეკურსიული ფუნქცია დამოკიდებულია ორ ცვლადზე, რომლებიც არიან მწკრივი და სვეტი. ამრიგად, ჩვენ ვქმნით 2D DP- ს მასივი და შეინახეთ თითოეული შტატის შედეგი. ეს მკვეთრად გააუმჯობესებს დროის სირთულეს, რადგან ჩვენ არ ვწყვეტთ იგივე პრობლემებს.

იხილეთ ასევე
მინიმალური დრო ყველა წერტილის მონახულებისას Leetcode Solution

დინამიური პროგრამირების კოდი უნიკალური ბილიკების Leetcode ამოხსნისთვის

C ++ კოდი

#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

სირთულის ანალიზი

დროის სირთულე

O (N * M), სადაც N, M გამოიყენება ქსელის მწკრივებისა და სვეტების რაოდენობის გამოსახატავად. რადგან სულ N * M მდგომარეობაა, დროის სირთულე ასევე არის O (N * M).

სივრცის სირთულე

O (N * M), საჭირო სივრცეა 2D DP ცხრილის შესაქმნელად. სივრცის სირთულე მრავალპროფილიანია DP მიდგომისთვის.