അദ്വിതീയ പാതകൾ ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ബൈറ്റ്ഡാൻസ് ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ മാത്ത് വർക്ക്സ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ ഗുണനിലവാരം Salesforce Snapchat യൂബർ വിഎംവെയർ വാൾമാർട്ട് ലാബുകൾ
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

ഒരു പ്രത്യേക ഗ്രിഡിന്റെ വലുപ്പത്തെ പ്രതിനിധീകരിക്കുന്ന രണ്ട് സംഖ്യകൾ നിങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് അദ്വിതീയ പാതകളുടെ ലീറ്റ്കോഡ് പരിഹാരം പറയുന്നു. ന്റെ വലുപ്പം ഉപയോഗിക്കുന്നു ഗ്രിഡ്, ഗ്രിഡിന്റെ നീളം, വീതി എന്നിവ. ഗ്രിഡിന്റെ മുകളിൽ ഇടത് കോണിൽ നിന്ന് ചുവടെ വലത് കോണിലേക്കുള്ള അദ്വിതീയ പാതകളുടെ എണ്ണം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. ചലനത്തിന്റെ ദിശയിൽ പരസ്പരം പരിമിതികളുണ്ട്, ഏത് സമയത്തും ഒരാൾക്ക് താഴേയ്‌ക്കോ വലത്തേയ്‌ക്കോ മാത്രമേ നീങ്ങാൻ കഴിയൂ.

ഉദാഹരണം

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 ^ പരമാവധി (m, n)), ആവർത്തന പ്രവർത്തനം കാരണം എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണത കാരണം.

ബഹിരാകാശ സങ്കീർണ്ണത

O (പരമാവധി (m, n), കംപൈലർ സ്റ്റാക്ക് ഉപയോഗിക്കുന്ന ഇടം. ഇത് ആവർത്തന വൃക്ഷത്തിന്റെ ഉയരത്തെ ആശ്രയിച്ചിരിക്കുന്നു.

ഡൈനാമിക് പ്രോഗ്രാമിംഗ് സമീപനം

ആവർത്തന പരിഹാരത്തിന് കീഴിൽ മുകളിൽ വിശദീകരിച്ച സമീപനം എളുപ്പത്തിൽ മന .പാഠമാക്കാം. ആവർത്തന പ്രവർത്തനം വരി, നിര എന്നിങ്ങനെ രണ്ട് വേരിയബിളുകളെ ആശ്രയിച്ചിരിക്കുന്നു. അങ്ങനെ ഞങ്ങൾ 2 ഡി ഡിപി സൃഷ്ടിക്കുന്നു ശ്രേണി ഓരോ സംസ്ഥാനത്തിന്റെയും ഫലം സംഭരിക്കുക. ഞങ്ങൾ സമാന പ്രശ്നങ്ങൾ പരിഹരിക്കാത്തതിനാൽ ഇത് സമയ സങ്കീർണ്ണതയെ നാടകീയമായി മെച്ചപ്പെടുത്തും.

അദ്വിതീയ പാതകളുടെ ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള ഡൈനാമിക് പ്രോഗ്രാമിംഗ് കോഡ്

സി ++ കോഡ്

#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), 2 ഡി ഡിപി പട്ടിക സൃഷ്ടിക്കുന്നതിനാണ് ആവശ്യമായ ഇടം. സ്ഥല സങ്കീർണ്ണത ഡിപി സമീപനത്തിനുള്ള പോളിനോമിയലാണ്.