ځانګړې لاره د لیټکوډ حل  


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه د بلومبرګ ByteDance فیسبوک ګولډمن Sachs د ګوګل ریاضي د Microsoft سينه_پوښ کټتوریک Salesforce Snapchat über VMware د وال مارټ لیبز
الگوريتم پیشه کوډ ورکول متحرک برنامې مرکه د مرکې چمتووالی لیټ کوډ د لیټ کوډ حلونه

ستونزه د انوکړ لارې لیټکوډ حل په ګوته کوي چې تاسو ته دوه بشپړونه درکول کیږي چې د گرډ اندازې نمایندګي کوي. د د بريښنا، د شبکې اوږدوالی او عرض. موږ اړتیا لرو د بریښنا د پورتنۍ کی corner اړخ څخه تر ښي ښي کونج پورې د ځانګړي لارو شمیر ومومو. د خوځښت په لور یو بل خنډ شتون لري ، په هر وخت کې یو څوک کولی شي یوازې ښکته یا سم لور ته حرکت وکړي.

بېلګه  

row: 2, column: 2
2

توضیحي: د دندې بشپړولو لپاره یوازې دوه لارې شتون لري. لومړی یا تاسو سم یا لاندې ته ځئ. که تاسو سم حرکت کړی نو تاسو کولی شئ یوازې لاندې حرکت وکړئ. که تاسو لاندې حرکت کړی وی ، نو تاسو کولی شئ یوازې د ښکته لور لوري ته حرکت وکړئ. نو ، یوازې 2 لارې امکان لري.

ځانګړې لاره د لیټکوډ حلقید

row: 2, column: 3
3

توضیحي: منزل ته د رسیدو لپاره 6 لارې شتون لري. په پام کې ونیسئ که چیرې تاسو سم لور ته تللي یاست ، نو ستونزه پورتنۍ مثال ته راکم شوې او تاسو ښیې ښیې کونج ته د رسیدو لپاره 2 لارې لرئ. که تاسو ښکته وای ، نو تاسو د ښیې ښیې کونج ته رسیدو لپاره یوازینۍ لار لرئ. پدې توګه ، پای ته رسیدو لپاره د لارو ټول شمیر 3 دی.

هم وګوره
د کانټینټینټ لیټکوډ حل له لارې د صف جوړونې چیک کړئ

د غیر معمولي لارو لیټکوډ حل لپاره د بروټ فورس چلند  

ستونزه د انوکړ لارې لیټکوډ حل کولی شي په تکراري ډول حل شي. لکه څنګه چې موږ په دوهم مثال کې وکړ ، چیرې چې موږ ورکړل شوې ستونزه په 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 رامینځته کوو سور او د هر ایالتو پایله زیرمه کړئ. دا به په ډراماتیک ډول د وخت پیچلتیا ته وده ورکړي ځکه چې موږ ورته ستونزې نه حل کوو.

هم وګوره
د ټولو نقطو لیټکوډ حل څخه لږترلږه لیدنه

د ځانګړي لارو لیټکوډ حل لپاره متحرک برنامه کوډ

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 لید لپاره ډیری دی.