Решение за Leetcode за пермутации  


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Јаболко Атласиан Блумберг ByteDance eBay Facebook Garena GoDaddy Голдман Сакс Google Скопје Мајкрософт Oracle Salesforce САП Uber VMware Лаборатории Walmart Јаху
алгоритми Враќање назад кодирање интервју интервју подготви 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, 1.

Пристап за повлекување на решенијата за леткод за пермутации  

Решение за Leetcode за пермутацииПин

Проблемот Permutations Leetcode Solution не замоли да ги генерираме сите пермутации на дадената низа. Општо земено, од нас се бара да генерираме пермутација или клучот е да се направи некоја рекурзија на низата. Но, овде повторувањето или повлекувањето е малку незгодно. Еден начин можеше да биде избор на елемент од неизбрани елементи и ставање на крајот од одговорот. На овој начин се генерира пермутација и некако погрижете се да запомните дека оваа пермутација е генерирана и не треба да се повторува. Но, наместо да го сториме ова, ние се обидуваме да најдеме едноставен начин за извршување на задачата. Што ако избереме елемент и го замениме со тековниот елемент. Потоа направете рекурзивен повик за да ги генерирате сите пермутации за секвенцата еден индекс по тековниот индекс.

Видете исто така
Спојте две подредени поврзани листи

Откако ќе завршиме со генерирање на пермутации, еден индекс напред. Го отстрануваме одбраниот елемент, а потоа избираме друг елемент и ја повторуваме постапката. На овој начин се осигуруваме дека секој неискористен елемент сме го сместиле барем еднаш во моменталната позиција. И бидејќи направивме рекурзивен повик кон помал подпроблем. Помалиот подпроблем што генерира пермутација за низата започнува веднаш по тековниот индекс. Со додавање на тие пермутации во тековната пермутација се комплетира збир на пермутација со елемент поставен на тековниот индекс. На овој начин продолжуваме да ја минуваме низата од лево надесно и да го делиме проблемот на помали подпроблеми. Откако ќе ја достигнеме потребата, генериравме можна пермутација и ја додаваме на одговорот.

Код за повлекување  

C ++ код за решение за лек код за пермутации

#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]]

Анализа на сложеност  

Временска комплексност

О (Сигма (П (Н, К)), каде што P е k пермутација на n или делумна пермутација. Поформално, P (N, k) = (N!) / ((Nk)!).

Видете исто така
Направете две низи еднакви со обратно решение на под-низите Leetcode решение

Комплексноста на просторот

НА!), бидејќи мора да ги зачуваме сите можни решенија што се N! во големина каде што N е големината на низата.