د لیټکوډ حل


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon مڼه Atlassian د بلومبرګ ByteDance ebay لکه فیسبوک Garena GoDaddy ګولډمن Sachs د ګوګل LinkedIn د Microsoft سينه_پوښ Salesforce د تبليغاتو د über VMware د وال مارټ لیبز د ياهو
شاته تګ

ستونزه د بندیز لیټکوډ حل د بشپړ ساده ترتیب چمتو کوي او له موږ څخه غوښتنه کوي چې بشپړ ویکټر بیرته راشي یا سور د ورکړل شوي تسلسل د ټولو حکمونو. نو ، مخکې لدې چې ستونزه حل کړئ. موږ باید په جوازونو پوه شو. نو ، ترتیب ورکول د ورکړل شوي انډیجر ترتیباتو پرته بل څه ندي. نو ، کله چې موږ وایو چې موږ د ترتیب ټولو ترتیباتو ته اړتیا لرو. زموږ مطلب دا دی چې موږ د ورکړل شوي ترتیب ټول ممکنه انتظامات چاپ یا بیرته راوړو ته اړتیا لرو. راځئ چې د لا ښه پوهیدو لپاره یو څو مثالونو ته یوه نظر وکړو.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

توضیحي: ټولې لارې چې تاسو یې په ترتیب سره 1 ، 2 ، 3 لیکلی شئ د محصول په توګه ورکړل شوي. دلته په مجموع کې د 6 ، 1 ، 2 لیکلو لپاره 3 لارې شتون لري.

[0,1]
[[0,1],[1,0]]

توضیحي: د 2 ، 0 لیکلو لپاره یوازې 1 لارې شتون لري.

د لیټکوډ حل حلولو لپاره بیکریک تعقیب

د لیټکوډ حل

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

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

د شاتړ کوډ

د پرمټیوشن لیټکوډ حل لپاره C ++ کوډ

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

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

د پرمټریشن لیټکوډ حل لپاره جاوا کوډ

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

د پیچلتیا تحلیل

د وخت پیچلتیا

O (سگما (P (N ، K)) ، چیرې چې P د n یا جزوی تقلید k حکم دی. نور په رسمي ډول ، P (N، k) = (N!) / ((Nk)!).

د ځای پیچلتیا

O (N!) ، ځکه چې موږ باید ټول ممکنه حلونه ذخیره کړو کوم چې N دي! په اندازه کې چیرې N د صف اندازه ده.