Leetcod Permütasiyaları

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma ByteDance eBay Facebook google microsoft Kahin
alqoritmlər Geri qayıtma kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 33

Bu leetcode problemində bir əvvəlcədən verdik array fərqli tam ədədlərdən mümkün olan bütün permutasiyaları çap edin.

Nümunələr

Input
arr [] = {1, 2, 3}
Buraxılış
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Input
arr [] = {1, 2, 3, 4}
Buraxılış
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 problem perermutations üçün alqoritm

Bütün permutasiyalar backtracking istifadə edərək yaradıla bilər.

  1. Dizinin l-dən r-ə qədər bütün permütasiyalarını yaratmaq üçün l indeksindəki elementi düzəldin və l + 1-dən r-ə qədər təkrarlayın.
  2. L indeksində başqa bir elementi geri çəkin və düzəldin və l + 1-dən r-ə qədər təkrarlayın.
  3. Bütün permutasiyaları yaratmaq üçün yuxarıdakı addımları təkrarlayın.

Leetcode problemi perermutasiyalarının izahı

Nümunəni nəzərdən keçirək arr [] = {1, 2, 3}

Bir elementi birinci vəziyyətdə düzəldin, 1, ya da 2 və ya 3 seçimimiz var. İkinci səviyyə altındakı görüntü bu vəziyyəti təmsil edir. İkinci səviyyə birinci sütunda 1 birinci mövqedə, ikinci sütunda 2 birinci mövqedə və üçüncü sütunda 3 birinci mövqedə sabitlənir.

Leetcod PermütasiyalarıPin

Bir elementi ilk mövqedə düzəltdikdən sonra, bir elementi ikinci mövqedə düzəldin, ikinci səviyyə və birinci sütunda vəziyyəti nəzərdən keçirin, yəni {1, 2, 3}, 1 birinci mövqedə sabitləndi, buna görə də 2 və ya 2 olan ikinci mövqe üçün 3 seçim var. İkinci vəziyyətin düzəldilməsi üçüncü vəziyyəti avtomatik olaraq düzəldir. Aydınlaşdırmaq üçün yuxarıdakı şəkilə baxın.

Bunu bütün hallar üçün edin və verilən massivin bütün mümkün permutasiyalarını yaradır.

JAVA Kodu

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 ++ kodu

#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 problem perermutations üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi = O (n!) 
burada n - massivdəki elementlərin sayı.

References

Şərh yaz

Translate »