අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ByteDance ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් ගණිතය මයික්රොසොෆ්ට් ඔරකල් ගුණාත්මකභාවය Salesforce Snapchat Uber VMware වෝල්මාර්ට් ලැබ්
අරා ගතික වැඩසටහන්කරණය

අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුමෙහි ගැටළුව පවසන්නේ ඔබට ජාලකයක ප්‍රමාණය නියෝජනය කරන පූර්ණ සංඛ්‍යා දෙකක් ලබා දී ඇති බවයි. ප්‍රමාණය භාවිතා කිරීම ජාලකය, ජාලකයේ දිග සහ පළල. ජාලකයේ ඉහළ වම් කෙළවරේ සිට පහළ දකුණු කෙළවර දක්වා අද්විතීය මාර්ග ගණන සොයා ගැනීමට අපට අවශ්‍යය. චලනය වන දිශාවට එකිනෙකාට බාධාවක් තිබේ, ඕනෑම වේලාවක කෙනෙකුට ගමන් කළ හැක්කේ පහළට හෝ නිවැරදි දිශාවට පමණි.

උදාහරණයක්

row: 2, column: 2
2

පැහැදිලි කිරීම: කාර්යය සම්පූර්ණ කිරීමට ඇත්තේ ක්‍රම දෙකක් පමණි. පළමුව ඔබ දකුණට හෝ පහළට ගමන් කරන්න. ඔබ දකුණට ගියහොත් ඔබට පහළට යා හැකිය. ඔබ පහළට ගමන් කර ඇත්නම්, එවිට ඔබට ගමන් කළ හැක්කේ පහළ දිශාවට පමණි. එබැවින් හැකි වන්නේ ක්‍රම 2 ක් පමණි.

අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුම

row: 2, column: 3
3

පැහැදිලි කිරීම: ගමනාන්තයට ළඟා වීමට ක්‍රම 6 ක් ඇත. ඔබ දකුණට ගියහොත් සලකා බලන්න, එවිට ගැටලුව ඉහත උදාහරණය දක්වා අඩු කර ඇති අතර පහළ දකුණු කෙළවරට ළඟා වීමට ඔබට ක්‍රම 2 ක් ඇත. ඔබ පහළට බැස ඇත්නම්, ඔබට පහළ දකුණු කෙළවරට ළඟා වීමට ඇත්තේ එක් මාර්ගයක් පමණි. මේ අනුව, අවසානය කරා ළඟා විය හැකි මුළු මාර්ග ගණන 3 කි.

අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුම සඳහා තිරිසන් බල ප්‍රවේශය

අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුම ගැටළුව නැවත නැවත විසඳිය හැකිය. අපි දෙවන උදාහරණයේ දී කළාක් මෙන්, දී ඇති ගැටළුව උපප්‍රශ්න 2 කට අඩු කළෙමු. මෙම විසඳුම තුළ අප කරන්නේ කුමක්ද යන්න එකම දෙයයි. වරක්, අපි දකුණට ගියෙමු, එවිට ගැටළුව උපප්‍රශ්නයට අඩු වේ (පේළිය, තීරුව -1). අප පහළ දිශාවට ගමන් කර ඇත්නම්, ගැටළුව (පේළිය -1, තීරුව) දක්වා අඩු වේ. අපට මෙම පුනරාවර්තන විසඳුම පහසුවෙන් කේත කළ හැකිය. නමුත් විසඳුම අතිශයින්ම අකාර්යක්ෂම බැවින් මෙය කාල සීමාව ඉක්මවා යනු ඇත.

තිරිසන් බලවේගය සඳහා කේතය

සී ++ කේතය

#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 ^ max (m, n)), පුනරාවර්තන ක්‍රියාකාරිත්වය හේතුවෙන් on ාතීය කාල සංකීර්ණතාව නිසා.

අභ්‍යවකාශ සංකීර්ණතාව

O (උපරිම (m, n), සම්පාදක තොගය භාවිතා කරන අවකාශය. මෙය පුනරාවර්තන ගසේ උස මත රඳා පවතී.

ගතික ක්‍රමලේඛන ප්‍රවේශය

පුනරාවර්තන විසඳුම යටතේ ඉහත විස්තර කර ඇති ප්රවේශය පහසුවෙන් කටපාඩම් කළ හැකිය. පුනරාවර්තන ශ්‍රිතය පේළි සහ තීරුව යන විචල්‍යයන් දෙකක් මත රඳා පවතී. මේ අනුව අපි 2D DP නිර්මාණය කරමු අරාව සහ එක් එක් රාජ්යයේ ප්රති result ලය ගබඩා කරන්න. අප එකම ගැටළු විසඳන්නේ නැති නිසා මෙය කාල සංකීර්ණතාව නාටකාකාර ලෙස වැඩි දියුණු කරනු ඇත.

අද්විතීය මාර්ග ලීට්කෝඩ් විසඳුම සඳහා ගතික ක්‍රමලේඛන කේතය

සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් * එම්), එහිදී N, M භාවිතා කරනුයේ පේළි ගණන සහ ජාලකයේ තීරු නිරූපණය කිරීමට ය. මුළු N * M තත්වයන් ඇති බැවින්, කාල සංකීර්ණතාව ද O (N * M) වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් * එම්), අවශ්‍ය අවකාශය 2D DP වගුවක් නිර්මාණය කිරීම සඳහා වේ. ඩීපී ප්‍රවේශය සඳහා අවකාශයේ සංකීර්ණතාව බහුපද වේ.