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


Ниво на трудност M
Често задавани в Кирпич Амазонка ябълка Atlassian Bloomberg ByteDance иБей Facebook Garena GoDaddy Goldman Sachs Google LinkedIn Microsoft Оракул Salesforce SAP Uber VMware Walmart Labs Yahoo
връщане назад

Проблемът 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 Solution

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

Проблемът Permutations Leetcode Solution ни помоли да генерираме всички пермутации на дадената последователност. Като цяло от нас се изисква да генерираме пермутация или някаква рекурсия на последователността е ключът към това. Но тук рекурсията или обратното проследяване е малко сложно. Един от начините е можело да бъде избирането на елемент от непознати елементи и поставянето му в края на отговора. По този начин се генерира пермутация и по някакъв начин не забравяйте да запомните, че тази пермутация е генерирана и не трябва да се повтаря. Но вместо да правим това, ние се опитваме да намерим прост начин за изпълнение на задачата. Ами ако изберем елемент и го сменим с текущия елемент. След това направете рекурсивно повикване, за да генерирате всички пермутации за последователността един индекс след текущия индекс.

След като приключим с генерирането на пермутациите с един индекс напред. Премахваме избрания елемент и след това избираме друг елемент и повтаряме процедурата. По този начин се уверяваме, че сме поставили всеки неизползван елемент поне веднъж в текущата позиция. И тъй като направихме рекурсивно повикване към по-малка подпроблема. По-малката подпроблема генерира пермутация за последователността, започваща непосредствено след текущия индекс. Добавянето на тези пермутации към текущата пермутация завършва набор от пермутации с елемент, зададен в текущия индекс. По този начин продължаваме да обхождаме масива отляво надясно и да разделяме проблема на по-малки подпроблеми. След като достигнем нуждата, генерирахме възможна пермутация и я добавяме към отговора.

Код за проследяване

C ++ код за Permutations 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

Java код за пермутации 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)!).

Сложност на пространството

НА!), тъй като трябва да съхраняваме всички възможни решения, които са N! по размер, където N е размерът на масива.