Permutations Leetcode Solution


سطح دشواری متوسط
اغلب در خشت آمازون سیب Atlassian بلومبرگ ByteDance ای بی فیس بوک گارنا نیک گلدمن ساکس گوگل لینک مایکروسافت وحی Salesforce SAP حال بارگذاری آموزش VMware آزمایشگاه های والمارت یاهو
عقب نشینی

مسئله Permutations Leetcode Solution توالی ساده ای از اعداد صحیح را فراهم می کند و از ما می خواهد که یک بردار کامل یا صف از همه جا به جایی های دنباله داده شده. بنابراین ، قبل از شروع به حل مشکل. ما باید با جایگشت ها آشنا شویم. بنابراین ، جایگشت چیزی نیست جز آرایش اعداد صحیح داده شده. بنابراین ، وقتی می گوییم به همه جایگشت های یک دنباله احتیاج داریم. منظور ما این است که ما ملزم به چاپ یا برگرداندن کلیه تنظیمات ممکن از توالی داده شده هستیم. برای درک بهتر چند نمونه را بررسی می کنیم.

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 راه وجود دارد.

رویکرد بازگشت به عقب برای Permutations Leetcode Solution

Permutations Leetcode Solution

مسئله Permutations Leetcode Solution از ما خواست که همه جایگشتهای دنباله داده شده را ایجاد کنیم. به طور کلی ، ما نیاز به ایجاد جایگزینی داریم یا برخی از توالی ها کلید اصلی است. اما در اینجا بازگشت یا بازگشت به عقب کمی مشکل است. یکی از راه ها می توانست انتخاب عنصر از عناصر انتخاب نشده و قرار دادن آن در انتهای پاسخ باشد. با این روش جایگشت ایجاد می شود و به نوعی مطمئن شوید که این جایگزینی ایجاد شده است و نباید تکرار شود. اما به جای انجام این کار ، سعی می کنیم راهی ساده برای انجام کار پیدا کنیم. چه می شود اگر عنصری را انتخاب کنیم و آن را با عنصر فعلی عوض کنیم. سپس یک فراخوان بازگشتی ایجاد کنید تا همه جایگشتهای دنباله یک شاخص بعد از شاخص فعلی ایجاد شود.

هنگامی که ما با ایجاد جایگشت ها یک شاخص جلوتر تمام شد. ما عنصر انتخاب شده را بر می داریم و سپس یک عنصر دیگر را انتخاب می کنیم و روش را تکرار می کنیم. به این ترتیب مطمئن می شویم که هر عنصر بلااستفاده را حداقل یک بار در موقعیت فعلی قرار داده ایم. و از آنجا که ما یک تماس بازگشتی به یک مسئله فرعی کوچکتر برقرار کردیم. زیرمشکل کوچک تر که در حال تولید جایگزینی برای توالی است که دقیقاً بعد از شاخص فعلی شروع می شود. افزودن آن جایگزینی ها به جایگشت فعلی ، مجموعه ای از جایگشت ها را با یک عنصر که در شاخص فعلی تنظیم شده است ، کامل می کند. به این ترتیب ما آرایه را از چپ به راست رد می کنیم و مسئله را به زیرمشکلات کوچکتر تقسیم می کنیم. وقتی به نیاز رسیدیم جایگزینی احتمالی ایجاد کرده و آن را به جواب اضافه می کنیم.

کد برگشت

کد ++ C برای Permutations Leetcode Solution

#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 جایگزینی k n یا جایگزینی جزئی است. به طور رسمی تر ، P (N ، k) = (N!) / ((Nk)!).

پیچیدگی فضا

بر!)، از آنجا که ما باید تمام راه حل های ممکن N را ذخیره کنیم! در اندازه که N اندازه آرایه است.