اجازت نامہ لیٹکوڈ حل  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون ایپل اٹلی بلومبرگ ByteDance ای بے فیس بک Garena گودادی گولڈمین سیکس گوگل لنکڈ مائیکروسافٹ اوریکل Salesforce SAP Uber VMware والمارٹ لیبز یاہو
یلگوردمز پس منظر کوڈنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔

پریشانیشن لیٹ کوڈ حل میں عدد کا ایک آسان سلسلہ ملتا ہے اور ہم سے ایک مکمل ویکٹر کو واپس کرنے کا مطالبہ کرتا ہے یا صف دیئے گئے تسلسل کے تمام اجازتوں کا۔ تو ، مسئلہ حل کرنے میں جانے سے پہلے۔ ہمیں اجازت ناموں سے واقف ہونا چاہئے۔ لہذا ، اجازت نامے دیے جانے والے اعداد کی ترتیب کے سوا کچھ نہیں ہے۔ لہذا ، جب ہم کہتے ہیں کہ ہمیں ایک تسلسل کے تمام اجازتوں کی ضرورت ہے۔ ہمارا مطلب ہے کہ ہمیں دیئے گئے ترتیب کے تمام ممکنہ انتظامات کو پرنٹ کرنے یا واپس کرنے کی ضرورت ہے۔ آئیے بہتر تفہیم کے لئے کچھ مثالوں پر ایک نظر ڈالیں۔

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 طریقے ہیں۔

لیٹکوڈ حل کی اجازت کے لئے بیک ٹریکنگ اپروچ  

اجازت نامہ لیٹکوڈ حلپن

پرمٹٹیشن لیٹ کوڈ حل نے مسئلہ سے ہمیں دیئے گئے تسلسل کے تمام اجازت پیدا کرنے کو کہا۔ عام طور پر ، ہمیں اجازت پیدا کرنے کی ضرورت ہوتی ہے یا کچھ ترتیب تکرار کرنا کلید ہے۔ لیکن یہاں تکرار یا بیک ٹریکنگ تھوڑی مشکل ہے۔ ایک طریقہ یہ بھی ہوسکتا تھا کہ بغیر کسی عنصر سے عنصرہ چن کر اسے جواب کے آخر میں رکھ دیا جاسکتا ہے۔ اس طرح ایک تقویت پیدا کرتے ہیں اور کسی نہ کسی طرح یہ یاد رکھنا یقینی بنائیں کہ یہ ترتیب پیدا ہوچکی ہے اور اسے دہرایا نہیں جانا چاہئے۔ لیکن ایسا کرنے کی بجائے ، ہم کام کو انجام دینے کا ایک آسان طریقہ تلاش کرنے کی کوشش کرتے ہیں۔ اگر ہم کسی عنصر کو منتخب کریں اور اسے موجودہ عنصر کے ساتھ تبدیل کریں تو کیا ہوگا۔ اس کے بعد موجودہ انڈیکس کے بعد ترتیب ون انڈیکس کے لئے تمام اجازتیں پیدا کرنے کے لئے ایک تکرار کال کریں۔

یہ بھی دیکھتے ہیں
دو طرح کی لنکڈ فہرستیں ضم کریں

ایک بار جب ہم آگے ترتیب دینے کے لئے ایک انڈیکس آگے کر لیں۔ ہم منتخب کردہ عنصر کو ہٹاتے ہیں ، اور پھر دوسرا عنصر چنتے ہیں اور طریقہ کار کو دہرا دیتے ہیں۔ اس طرح ہم یہ یقینی بناتے ہیں کہ ہم ہر غیر استعمال شدہ عنصر کو کم از کم ایک بار موجودہ حالت میں رکھ چکے ہیں۔ اور چونکہ ہم نے ایک چھوٹے سے چھوٹے مسئلے پر تکرار کال کی۔ موجودہ انڈیکس کے بالکل بعد شروع ہونے والی ترتیب کے ل the چھوٹا سب پروبلم پیدا ہو رہا ہے۔ موجودہ ترتیب میں ان اجازتوں کو شامل کرنا موجودہ انڈیکس میں عنصر کے سیٹ کے ساتھ اجازت نامہ کا ایک سیٹ مکمل کرتا ہے۔ اس طرح ہم صف کو بائیں سے دائیں منتقل کرتے رہتے ہیں اور مسئلے کو چھوٹے چھوٹے مسائل میں تقسیم کرتے ہیں۔ ایک بار جب ہم ضرورت تک پہنچیں تو ہم نے ممکنہ تخفیف پیدا کردی اور ہم اسے جواب میں شامل کردیں۔

بیک ٹریکنگ کوڈ  

اجازت نامہ لیٹکوڈ حل کے لئے 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) یا جزوی طور پر اجازت نامہ بھیجنے کے لئے ہے۔ مزید رسمی طور پر ، P (N، k) = (N!) / ((Nk)!)۔

یہ بھی دیکھتے ہیں
سب اری لیٹ کوڈ حل کو تبدیل کرکے دو اری کے برابر بنائیں

خلائی پیچیدگی

O (N!) ، چونکہ ہمیں تمام ممکنہ حل ذخیرہ کرنا ہوں گے جو N ہیں! جس میں N سرنی کا سائز ہے۔