تباديل حل Leetcode  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل Atlassian بلومبرغ ByteDance يباي Facebook Garena GoDaddy أو جولدمان ساكس جوجل لينكد إن: Microsoft أوراكل ساليسفورسي SAP اوبر في إم وير مختبرات وول مارت ياهو
خوارزميات التراجع الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions

توفر مشكلة 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.

نهج التراجع لحل التباديل Leetcode  

تباديل حل Leetcode

طلبت منا مشكلة التباديل Leetcode Solution إنشاء جميع التباديل في التسلسل المحدد. بشكل عام ، نحن مطالبون بإنشاء تبديل أو بعض التكرار المتسلسل هو المفتاح للذهاب. ولكن هنا يكون التكرار أو التراجع صعبًا بعض الشيء. كان من الممكن أن تكون إحدى الطرق هي انتقاء عنصر من العناصر غير المنتقاة ووضعه في نهاية الإجابة. بهذه الطريقة تولد تقليبًا وتأكد بطريقة ما أن تتذكر أن هذا التقليب قد تم إنشاؤه ولا ينبغي تكراره. لكن بدلاً من القيام بذلك ، نحاول إيجاد طريقة بسيطة لأداء المهمة. ماذا لو اخترنا عنصرًا وقمنا بتبديله بالعنصر الحالي. ثم قم بإجراء مكالمة متكررة لإنشاء جميع التباديل للتسلسل فهرس واحد بعد الفهرس الحالي.

انظر أيضا
دمج قائمتين مرتبطتين تم فرزهما

بمجرد أن ننتهي من إنشاء التباديل ، هناك مؤشر واحد للأمام. نزيل العنصر المختار ، ثم نختار عنصرًا آخر ونكرر الإجراء. بهذه الطريقة نتأكد من أننا قد وضعنا كل عنصر غير مستخدم مرة واحدة على الأقل في الموضع الحالي. وبما أننا قمنا بإجراء مكالمة متكررة إلى مشكلة فرعية أصغر. المشكلة الفرعية الأصغر تُنشئ التقليب للتسلسل الذي يبدأ بعد الفهرس الحالي مباشرةً. إضافة تلك التباديل إلى التقليب الحالي يكمل مجموعة من التقليب مع عنصر معين في الفهرس الحالي. بهذه الطريقة نستمر في اجتياز المصفوفة من اليسار إلى اليمين وتقسيم المشكلة إلى مشاكل فرعية أصغر. بمجرد أن نصل إلى الحاجة ، نكون قد ولّدنا إمكانية التقليب الممكنة ونضيفها إلى الإجابة.

رمز التراجع  

كود C ++ للتباديل 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

كود جافا للتباديل حل Leetcode

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)!).

انظر أيضا
اجعل صفيفتين متساويتين عن طريق عكس حل Leetcode للمصفوفات الفرعية

تعقيد الفضاء

على!)، حيث يتعين علينا تخزين جميع الحلول الممكنة وهي N! في الحجم حيث N هو حجم المصفوفة.