Перестановка Leetcode Solution  


Рівень складності Medium
Часто запитують у саман Амазонка Apple Atlassian Bloomberg ByteDance eBay Facebook Garena GoDaddy Goldman Sachs Google LinkedIn Microsoft оракул Salesforce SAP Убер VMware Лабораторії Walmart Yahoo
алгоритми Зворотний трек кодування інтерв'ю інтерв'юпідготовка 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  

Перестановка Leetcode SolutionPin

Проблема Permutations Leetcode Solution попросила нас сформувати всі перестановки заданої послідовності. Як правило, нам потрібно створити перестановку або якась рекурсія послідовності є ключовим фактором. Але тут рекурсія або зворотне відстеження дещо складно. Одним із шляхів міг бути вибір елемента з невідібраних елементів та розміщення його в кінці відповіді. Таким чином генерують перестановку і якось обов’язково пам’ятають, що ця перестановка була створена і не повинна повторюватися. Але замість цього ми намагаємось знайти простий спосіб виконання завдання. Що робити, якщо ми вибираємо елемент і обмінюємо його поточним елементом. Потім зробіть рекурсивний виклик, щоб згенерувати всі перестановки для послідовності один індекс після поточного індексу.

Дивись також
Об’єднайте два відсортовані зв’язані списки

Як тільки ми закінчимо з генерацією перестановок на один індекс вперед. Ми видаляємо вибраний елемент, а потім вибираємо інший елемент і повторюємо процедуру. Таким чином ми переконуємось, що ми розмістили кожен невикористаний елемент хоча б раз у поточному положенні. І оскільки ми зробили рекурсивний виклик меншої підзадачі. Менша підзадача генерує перестановку для послідовності, що починається відразу після поточного індексу. Додавання цих перестановок до поточної перестановки завершує набір перестановок елементом, встановленим у поточному індексі. Таким чином ми продовжуємо обходити масив зліва направо і ділимо проблему на менші підзадачі. Як тільки ми досягнемо потреби, ми створили так можливу перестановку, і ми додаємо її до відповіді.

Код зворотного відстеження  

Код C ++ для рішення перестановок Leetcode

#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)!).

Дивись також
Зробіть два масиви рівними, змінивши рішення підконтрольних лінійних кодів

Складність простору

O (N!), оскільки ми маємо зберігати всі можливі рішення, які є N! за розміром, де N - розмір масиву.