تباديل Leetcode  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل ByteDance يباي فيس بوك جوجل Microsoft أوراكل
خوارزميات التراجع Coding المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions

في هذا التمهيد لمشكلة leetcode قدمنا ​​ملف مجموعة من الأعداد الصحيحة المتميزة ، اطبع جميع التباديل الممكنة.

أمثلة  

إدخال
وصول [] = {1، 2، 3}
الناتج
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

إدخال
وصول [] = {1، 2، 3، 4}
الناتج
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
1 3 2 4
1 3 4 2
2 3 1 4
2 3 4 1
1 4 3 2
1 4 2 3
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
4 2 3 1
4 2 1 3
3 1 2 4
3 1 4 2
4 3 2 1
4 3 1 2
3 4 1 2
3 4 2 1
4 1 3 2
4 1 2 3

خوارزمية لتباديل مشكلة Leetcode  

يمكن إنشاء جميع التباديل باستخدام التراجع.

  1. لتوليد جميع تباديل المصفوفة من الفهرس l إلى r ، قم بإصلاح عنصر في الفهرس l وكرر للفهرس l + 1 إلى r.
  2. التراجع وإصلاح عنصر آخر في الفهرس l وتكرار للفهرس l + 1 إلى r.
  3. كرر الخطوات المذكورة أعلاه لتوليد جميع التباديل.

شرح تباديل مشكلة Leetcode  

ضع في اعتبارك المثال arr [] = {1، 2، 3}

إصلاح عنصر في الموضع الأول ، لدينا ثلاثة خيارات 1 ، أو 2 ، أو 3. الصورة أسفل المستوى الثاني تمثل هذا الموقف. في العمود الأول من المستوى الثاني ، تم إصلاح 1 في الموضع الأول ، وفي العمود الثاني تم إصلاح 2 في الموضع الأول وفي العمود الثالث تم إصلاح 3 في الموضع الأول.

تباديل Leetcodeدبوس

بعد تثبيت عنصر في الموضع الأول ، قم بإصلاح عنصر في الموضع الثاني ، ضع في اعتبارك الحالة في المستوى الثاني والعمود الأول ، أي ، {1 ، 2 ، 3} ، 1 ثابت في الموضع الأول ، لذلك نحن لديك خياران للمركز الثاني إما 2 أو 2. إصلاح المركز الثاني يعمل تلقائيًا على إصلاح المركز الثالث. انظر الصورة أعلاه للتوضيح.

انظر أيضا
مين ستاك

افعل هذا لجميع الحالات وسيولد جميع التباديل الممكنة للمصفوفة المحددة.

كود جافا  

public class LeetcodePermutations {
    // Function to generate all the permutations from l to r
    private static void permute(int[] arr, int l, int r) {
        if (l == r) {
            // Print this permutation
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = l; i <= r; i++) {
            // Fix an element at index l
            swap(arr, l, i);
            // Recur for index l + 1 to r
            permute(arr, l + 1, r);
            // Back track
            swap(arr, l, i);
        }
    }

    // Function to swap element at index x and y of array arr
    private static void swap(int arr[], int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    
    public static void main(String[] args) {
        // Example
        int arr[] = new int[] {1, 2, 3};
        int n = arr.length;
        // Generate permutations from index 0 to n - 1
        permute(arr, 0, n - 1);
    }
}

كود C ++  

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

// Function to swap element at index x and y of array arr
void swap(int *arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

// Function to generate all the permutations from l to r
void permute(int *arr, int l, int r, int n) {
    if (l == r) {
        // Print this permutation
        for (int i = 0; i < n; i++) {
            cout<<arr[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i = l; i <= r; i++) {
        // Fix an element at index l
        swap(arr, l, i);
        // Recur for index l + 1 to r
        permute(arr, l + 1, r, n);
        // Back track
        swap(arr, l, i);
    }
}

int main() {
    // Example
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // Generate permutations from index 0 to n - 1
    permute(arr, 0, n - 1, n);
    return 0;
}
1 2 3                                                                                                                                         
1 3 2                                                                                                                                         
2 1 3                                                                                                                                         
2 3 1                                                                                                                                         
3 2 1                                                                                                                                         
3 1 2

تحليل التعقيد لتباديل مشكلة Leetcode  

تعقيد الوقت = على!) 
حيث n هو عدد العناصر في المصفوفة.

انظر أيضا
الفرز باستخدام دالة تجزئة تافهة

مراجع