Leetcode-ийн тохируулга


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн БайтДанс Ebay Facebook-ийн Google-ийн Microsoft- Oracle-ийн
Буцах

Энэхүү leetcode-ийн асуудалд урьдчилсан тооцоог бид өгсөн болно массив ялгаатай бүхэл тоонуудын бүх боломжит сэлгэлтийг хэвлэ.

жишээ нь

Оролт
arr [] = {1, 2, 3}
гаралтын
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Оролт
arr [] = {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 бодлогын алгоритм

Бүх сэлгэлтийг backtracking ашиглан үүсгэж болно.

  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 гэсэн хоёрдахь байрлалд зориулсан 3 сонголтыг хий. Хоёр дахь байрлалыг засах нь гурав дахь байрлалыг автоматаар засна. Тодруулга авахын тулд дээрх зургийг үзнэ үү.

Бүх тохиолдлуудад үүнийг хийвэл өгөгдсөн массивын бүх боломжит сэлгэлтийг үүсгэх болно.

JAVA код

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-ийн асуудлын суулгацын нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал = O (n!) 
энд n нь массив дахь элементүүдийн тоо юм.

Ашигласан материал